有序元素

Question

我開發一個時間關鍵型應用程序和最佳集裝箱正在尋找最好的容器來處理以下類型的元素的集合：

class Element 
{ 
    int weight; 
    Data data; 
}; 

考慮到時間我的應用程序的關鍵步驟，在一個獨特的線程週期性地執行，有以下幾種：

• 的Element具有最低weight從容器中取出，並data被處理;
• 數字n> = 0的新Element，隨機（*）weight，插入到容器中。

容器的一些Element可能具有相同的重量。隨時在容器中的元素總數很高，平均幾乎平穩（幾十萬）。上述提取/加工/插入序列所需的時間必須儘可能低。 （注（*）：新的重量實際上是從數據計算，而是被視爲隨機這裏簡化）

不同STL容器的一些搜索和嘗試後，我結束了使用的std :: multiset的容器，它執行速度比訂購std :: vector快16倍，比訂購std：列表快16倍。但是，我想知道如果我能夠實現更好的性能，考慮到我的應用程序的瓶頸仍然在提取/插入操作中。

請注意，雖然我只嘗試了有序的容器，但在我的要求中沒有提到「有序容器」。我不需要在容器中訂購Element，我只需要儘可能快地執行「提取最低加權元素」/「插入新元素」操作。我不限於STL容器，如果適用，可以進行升級或其他任何實現。

感謝您的幫助。

Answer 1

我不需要在容器中排序元素，我只需要儘可能快地執行「提取最低加權元素」/「插入新元素」操作。

那麼你應該嘗試priority_queue<T>，或在vector<T>使用make_heap/push_heap/pop_heap操作。

由於您正在尋找最小堆，而不是最大堆，因此您需要提供一個自定義比較器，以相反的順序對您的Element對象進行排序。

Answer 2

嘗試任一這些：上述

std::map<int,std::vector<Data>> 

或

std::unordered_map<int,std::vector<Data>> 

的int是重量。

這些都有不同的速度查找，刪除和添加取決於許多不同的因素，如元素是否存在或不存在。 （如果有的話，unordered_map .find更快，否則，地圖。發現是更快）

Answer 3

我認爲，在STL內，懶惰std::vector會給最好的結果。

建議的僞代碼可能看起來像：

• 佈設回新元素在向量
• 結束只有當你想最小的元素，數組進行排序並獲得第一個元素

通過這種方式，您可以獲得延遲的插入時間vector，相對較少的內存分配量和良好的緩存局部性。

Answer 4

考慮不同的候選人以及您的假設如何影響最終選擇是有益的。當您的要求發生變化時，切換容器會變得更加容易。

通常，尺寸N的容器具有其基本ACCES /修改操作大致3複雜類：（攤銷）O(1)，O(log N)和O(N)。

你第一要求（尋找最低權重元素）爲您大致有三種候選人O(1)的複雜性，以及一名候選人與O(N)複雜每件：

1. O(1)爲std::priority_queue<Element, LowestWeightCompare>

2. O(1) for std::multiset<Element, LowestWeightCompare>

3. O(1)爲boost::flat_multiset<Element, LowestWeightCompare>

4. O(N)爲std::unordered_multiset<Element>

你第二個要求（新元素的隨機插入）提供以下複雜每元件每個上述四種選擇的

1. O(log N)爲std::priority_queue

2. O(log N)爲std::multiset

3. O(N)爲boost::flat_multiset

4. 攤銷O(1)爲std::unordered_multiset

其中前三種選擇，boost::multiset應該由另外兩個主導爲大N。在剩下的兩個中，std::priority_queue比std::multiset更好的緩存行爲可能佔上風。但是：措施，措施，措施，但是。

它是模糊的先驗std::unorderd_multiset是否與其他三個競爭力。取決於隨機插入元件的數量n，每批的find(1)-insert(n)總成本將是爲O(N) search + O(n) insertion和std::unordered_multiset爲O(1) search + O(n log N) insertionstd::multiset。再次，測量，測量，測量。

如何強大的是這些因素相對於你的要求？如果您必須在每批中找到k最低重量元素，則故事會發生如下變化。那麼你必須比較find(k)-insert(n)的成本。搜索成本將大致規模爲

1. O(k log N)爲std::priority_queue
2. O(1)爲std::multiset
3. O(1)爲boost::flat_multiset
4. O(k N)爲std::unordered_multiset

注意，一個priority_queue只能有效地訪問頂部元素，而不是它的k頂部元素，實際上並沒有調用pop()，每個調用的複雜度爲O(log N)。如果你希望你的代碼可能會從find(1)-insert(n)批處理模式更改爲find(k)-insert(n)，那麼它可能是一個好主意，選擇std::multiset，或至少文檔什麼樣的接口的改變，將需要。

獎勵：兩全其美的？你也可能要實驗一下與Boost.MultiIndex和使用類似（查看文檔，以獲得語法正確的）

boost::multi_index< 
    Element, 
    indexed_by< 
     ordered_non_unique<member<Element, &Element::weight>, std::less<>>, 
     hashed_non_unique<> 
    > 
> 

上面的代碼將創建一個實現兩個指針結構跟蹤基於節點的容器這兩個按重量排序的Element也允許快速哈希插入。這將允許O(1)查找最低重量Element的同時還能夠n新元素O(n)隨機插入。

對於大型N，它應該規模比四個前面提到的容器好，但同樣，通過指針追成隨機內存可能會破壞在std::priority_queue它的理論優勢誘導適度N，緩存的效果。我有沒有提到措施，措施，措施的口頭禪？