用C++排序數據結構的最快方法

我有一個數據結構，它由三個表示座標的int值和一個表示座標值的double組成。我想將它們存儲在一起，並按價值分類。值不是唯一的。現在，我將它們放在struct中，並使用lambda對它們進行排序，如下面的代碼所示。由於這是一個關鍵性能代碼，我正在尋找一種實現最快排序的實現。該列表將包含10^6到10^7個元素。用C++排序數據結構的最快方法

什麼是最優雅的方式來解決這個問題？我並非試圖使用std::sort，但我主要詢問是否將數據存儲在struct中是最佳解決方案，還是有更好的替代方案？

#include <vector> 
#include <algorithm> 
#include <iostream> 

struct Data 
{ 
    int i; 
    int j; 
    int k; 
    double d; 
}; 

int main() 
{ 
    std::vector<Data> v; 

    v.push_back({1,2,3,0.6}); 
    v.push_back({1,2,3,0.2}); 
    v.push_back({1,2,3,0.5}); 
    v.push_back({1,2,3,0.1}); 
    v.push_back({1,2,3,0.4}); 

    std::sort(v.begin(), v.end(), [](const Data& a, const Data& b) 
      { return a.d < b.d; }); 

    for (auto d : v) 
     std::cout << d.i << ", " << d.j << ", " 
        << d.k << ", " << d.d << std::endl; 

    return 0; 
}

來源

2016-06-06 Chiel

這將有助於瞭解我的問題出了什麼問題。 – Chiel

「最快的排序方式」幾乎是太寬泛的定義。它依賴於太多的東西：編譯器和選項，目標系統體系結構，要排序的元素數量，元素排序前的排列方式。您很可能必須使用實際數據 – vu1p3n0x

和99％的時間自己實施一些算法並運行性能測試，答案是「您可以編寫和調試這幾百行文件，而且它平均只有一半比'std :: sort'快％「。只需使用'std :: sort'。 –

重複的問題，Fastest way to search and sort vectors是比我能給的更好的答案。

總結，
你需要一個更好的樣本集，5個條目不會告訴你什麼。你不能擊敗std :: sort。特別是對你來說，浮點比較將是痛苦的一點。

來源

2016-06-06 19:12:07

我確實想使用排序，我主要懷疑'struct'是否是正確的數據類型，或者我是否應該使用'std :: pair'作爲實例。 – Chiel

排序它們的最快方法是不必對它們排序。

以一些稍慢的插入爲代價，您可以將整個容器分類存儲，並且只能插入正確的位置。 A std::set可以幫助你，或者你可以推出自己的。

編輯：一個std::multiset將提供相同的優勢，如果你需要允許比較相同的值。

來源

2016-06-06 19:12:48 Taywee

我不知道那個。謝謝 – Chiel

我想指出它也取決於使用。如果您通常會在使用之前填充您的結構並進行一次排序，那麼這可能會比填充和排序效率低。如果您將通過代碼定期排序，這可能會更快。 – Taywee

用C++排序數據結構的最快方法

回答

相關問題