使用什麼排序方法：quicksort，bucket sort，radix，...用於小數據對？ （C++）

Question

我需要優化一些排序vector<pair<int, float >> a的代碼，其中對需要在浮點值上排序。該矢量的長度介於0和5之間。我一直在使用Google搜索並閱讀C++中的排序方法，但無法找到排序微小數據集的任何基準。對於該系統來說，重要的是儘可能快地將其用於實時斑點追蹤系統。

親切的問候， 北河三

Answer 1

第一個,不成熟的優化是所有邪惡的根源。也就是說，首先對您的代碼進行基準測試，並確保排序是實際花費最多時間的排序。如果您的性能關鍵代碼的另一部分佔用了80％的執行時間，那麼您將首先優化性能，從而大幅提升性能。

考慮到你有5個元素，這一點幾乎沒有實際意義。你使用的任何算法（除了bogosort：D）應該有一個幾乎恆定的執行時間，除非你每秒運行算法幾百次或更多。

二，只要你仍然要優化搜索，如果你肯定知道你總是將有5個元素，的最佳方法是通過硬編碼comparations（但可以從數學是證明這種方法是最優的，在最糟糕的情況下提供最少數量的執行操作 - 我們在大學中將此作爲實驗室應用程序）。如果您的元素少於五個，這同樣適用，但如果您的元素超過七個，則該算法會變得難以編寫和執行 - 邏輯錯亂地編寫並遵循，因此您的代碼將難以維護。

讓我知道如果您需要編寫最佳硬編碼算法本身的幫助（儘管我認爲您應該在網上找到實現和理論）。

如果您不總是有五個數字（或出於某種原因想要避免硬編碼比較算法），請使用庫提供的排序。 This page得出結論認爲stl sort在時間上是最優的（不僅是執行操作的數量）。我不知道用於搜索的是什麼實現。

Answer 2

對於你所提到的數據（0-5），使用STL sort方法。 （歷史上以qsort爲基礎）

stable_sort - 如果您想維護重複訂單。 （歷史合併排序）

Answer 3

爲什麼需要優化此代碼的任何特定原因？對於n == 5，幾乎任何排序都可以。即使Bogosort應該有一個合理的運行時間，因爲只有5！ ==數據中可能有120種排列。你有沒有分析你的算法，找出這是否是一個瓶頸？

Answer 4

Insertion sort和Bubble sort適用於小數據對。

另一種選擇是使用幾個if語句對比較邏輯進行硬編碼。
檢查出What is the fastest possible way to sort an array of 7 integers?的一些想法。

Answer 5

關於基準測試，讀取是沒有意義的。您可以閱讀並比較算法的複雜度（Big-O），因爲它僅取決於算法本身，但基準測試依賴於太多因素。

您需要使用您使用的工具在您對應用程序用戶很重要的環境中爲自己做基準測試。

Answer 6

如果你真的確定（即，你有測量），這是一個瓶頸，需要優化，並且STL的任何排序算法都不夠快（而且你已經測量了那也是），那麼也許你知道一些你可以使用的東西？標準的排序算法是通用的，並且對於任何數據集都可以工作（相當好）：不同數量的元素，不同的值範圍等等。如果你真的需要性能，訣竅通常是使用額外的信息來製作更專業的算法。

這裏你說了一件事：有0-5個元素可以排序，正如Nick D在他的回答中所說的，也許這會使得使用硬編碼的if語句而不是典型的循環或遞歸排序算法。

但也許還有更多？例如，是否對可能發生的浮點值有任何限制？

Answer 7

對於最快的5個項目，使用一些有點令人討厭的if組，或者如果您想要的排序只是稍微慢一點，但更少一些頭疼，您可以使用sorting network。使用輸入數量等於5的this site以獲得優化的排序網絡。它甚至顯示了你可以如何做一些並行的部分，雖然對於只有5個輸入看起來有點過分。這將需要9次比較，這是相當不錯的。您也將使用一組if s來實現分類網絡，但是我在開始時提到的那些有點討厭的一組if s之間的區別是，哪一個真正的最優分類網絡是交換次數：排序網絡不會最小化交換次數。

Answer 8

這是一個例程，用於在最佳比較次數中對4個元素進行排序。我將張貼5個元素，但是計算器將帖子限制爲30000個字符。

這是否實際上是最快的取決於您的CPU指令緩存可以承受多少壓力，因此在真正的程序中進行基準測試！

/// Generated sort function for 4 arguments. 
template <class T> 
void DirectSort(T& a0, T& a1, T& a2, T& a3) { 
    if (a0 < a1) { 
     if (a0 < a2) { 
      if (a0 < a3) { 
       if (a1 < a2) { 
        if (a1 < a3) { 
         if (a3 < a2) { 
          { 
           T tmp(a2); 
           a2 = a3; 
           a3 = tmp; 
          } 
         } 
        } 
        else { // a1 >= a3 
         { 
          T tmp(a1); 
          a1 = a3; 
          a3 = a2; 
          a2 = tmp; 
         } 
         // a2 >= a3 
        } 
       } 
       else { // a1 >= a2 
        if (a1 < a3) { 
         { 
          T tmp(a1); 
          a1 = a2; 
          a2 = tmp; 
         } 
         // a2 < a3 
        } 
        else { // a1 >= a3 
         if (a2 < a3) { 
          { 
           T tmp(a1); 
           a1 = a2; 
           a2 = a3; 
           a3 = tmp; 
          } 
         } 
         else { // a2 >= a3 
          { 
           T tmp(a1); 
           a1 = a3; 
           a3 = tmp; 
          } 
         } 
        } 
       } 
      } 
      else { // a0 >= a3 
       if (a1 < a2) { 
        { 
         T tmp(a0); 
         a0 = a3; 
         a3 = a2; 
         a2 = a1; 
         a1 = tmp; 
        } 
        // a1 >= a3 
        // a2 >= a3 
       } 
       else { // a1 >= a2 
        { 
         T tmp(a0); 
         a0 = a3; 
         a3 = a1; 
         a1 = tmp; 
        } 
        // a1 >= a3 
        // a2 >= a3 
       } 
      } 
     } 
     else { // a0 >= a2 
      if (a0 < a3) { 
       // a1 >= a2 
       if (a1 < a3) { 
        { 
         T tmp(a0); 
         a0 = a2; 
         a2 = a1; 
         a1 = tmp; 
        } 
        // a2 < a3 
       } 
       else { // a1 >= a3 
        { 
         T tmp(a0); 
         a0 = a2; 
         a2 = a3; 
         a3 = a1; 
         a1 = tmp; 
        } 
        // a2 < a3 
       } 
      } 
      else { // a0 >= a3 
       // a1 >= a2 
       // a1 >= a3 
       if (a2 < a3) { 
        { 
         T tmp(a0); 
         a0 = a2; 
         a2 = tmp; 
        } 
        { 
         T tmp(a1); 
         a1 = a3; 
         a3 = tmp; 
        } 
       } 
       else { // a2 >= a3 
        { 
         T tmp(a0); 
         a0 = a3; 
         a3 = a1; 
         a1 = a2; 
         a2 = tmp; 
        } 
       } 
      } 
     } 
    } 
    else { // a0 >= a1 
     if (a0 < a2) { 
      if (a0 < a3) { 
       { 
        T tmp(a0); 
        a0 = a1; 
        a1 = tmp; 
       } 
       // a1 < a2 
       // a1 < a3 
       if (a3 < a2) { 
        { 
         T tmp(a2); 
         a2 = a3; 
         a3 = tmp; 
        } 
       } 
      } 
      else { // a0 >= a3 
       // a1 < a2 
       if (a1 < a3) { 
        { 
         T tmp(a0); 
         a0 = a1; 
         a1 = a3; 
         a3 = a2; 
         a2 = tmp; 
        } 
        // a2 >= a3 
       } 
       else { // a1 >= a3 
        { 
         T tmp(a0); 
         a0 = a3; 
         a3 = a2; 
         a2 = tmp; 
        } 
        // a2 >= a3 
       } 
      } 
     } 
     else { // a0 >= a2 
      if (a0 < a3) { 
       if (a1 < a2) { 
        { 
         T tmp(a0); 
         a0 = a1; 
         a1 = a2; 
         a2 = tmp; 
        } 
        // a1 < a3 
        // a2 < a3 
       } 
       else { // a1 >= a2 
        { 
         T tmp(a0); 
         a0 = a2; 
         a2 = tmp; 
        } 
        // a1 < a3 
        // a2 < a3 
       } 
      } 
      else { // a0 >= a3 
       if (a1 < a2) { 
        if (a1 < a3) { 
         if (a2 < a3) { 
          { 
           T tmp(a0); 
           a0 = a1; 
           a1 = a2; 
           a2 = a3; 
           a3 = tmp; 
          } 
         } 
         else { // a2 >= a3 
          { 
           T tmp(a0); 
           a0 = a1; 
           a1 = a3; 
           a3 = tmp; 
          } 
         } 
        } 
        else { // a1 >= a3 
         { 
          T tmp(a0); 
          a0 = a3; 
          a3 = tmp; 
         } 
         // a2 >= a3 
        } 
       } 
       else { // a1 >= a2 
        if (a1 < a3) { 
         { 
          T tmp(a0); 
          a0 = a2; 
          a2 = a3; 
          a3 = tmp; 
         } 
         // a2 < a3 
        } 
        else { // a1 >= a3 
         if (a2 < a3) { 
          { 
           T tmp(a0); 
           a0 = a2; 
           a2 = a1; 
           a1 = a3; 
           a3 = tmp; 
          } 
         } 
         else { // a2 >= a3 
          { 
           T tmp(a0); 
           a0 = a3; 
           a3 = tmp; 
          } 
          { 
           T tmp(a1); 
           a1 = a2; 
           a2 = tmp; 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
} // DirectSort - 4 arguments.