隊列實現基準

我開始開發一系列圖像處理算法，其中一些算法密集使用隊列。你們是否知道這些數據結構的良好基準？隊列實現基準

爲了縮小範圍，我用C居多，但我可以用C++，STL和任何庫。我已經得到的數據結構庫的幾個點擊，如GLib和C-Generic-Library和STL的過程中的容器。另外，如果你們中的任何一個開發/知道比這些更快的隊列，請告知:)

此外，隊列將有很多入隊和出隊操作，所以最好有一個聰明的方式來管理內存。

2010-09-17 korbes

這實際上取決於你打算如何使用隊列。他們是否是FIFOs，dqueues，優先級隊列，還是根本不排序？有多個線程？把東西放入隊列和/或將它們取出的爭用？ – nategoose 2010-09-17 23:35:32

@nategoose：我主要關注FIFO，在單線程上運行。我不明白你的意思是「把東西放在隊列中和/或將它們取出來？」 – korbes 2010-09-19 22:56:56

隊列需要被多個線程使用時，爭用只是一個問題。如果許多線程可以將事物放入隊列中並將其從隊列中取出，那麼任何簡單的實現都需要一個類型的互斥體，每個線程在插入或從隊列中提取之前都需要獲取該類型的互斥體。有幾種方法可以實現更復雜的隊列，雖然它們在單線程應用程序中執行得更糟，但通常對於多線程來說效果更好。 – nategoose 2010-09-19 23:18:07

對於單線程應用程序，你經常可以避開具有所有通過簡單處理下一個項目，因爲它涉及到使用任何類型的隊列，但也有很多應用中，這是不是這種情況（排隊數據例如輸出）。

而不需要鎖定隊列（沒有其他線程操心）一個簡單的循環緩衝區將是很難被擊敗的性能。如果由於某種原因，隊列需要在創建後增長，這有點困難，但是您不應該很難找到循環緩衝區隊列實現（或者自己構建）。如果在信號處理程序（或中斷服務程序）中完成插入或提取操作，那麼實際上您可能需要保護讀取和/或寫入位置索引，但如果您瞭解了目標，則可以確定這不是案件（如果有疑問保護，雖然）。通過暫時阻止信號或中斷將保護隊列中的東西保護起來。（如果你需要調整隊列的大小，你真的需要阻止這個）

如果你在隊列中的任何東西都必須動態分配，那麼你可能需要粘貼一個指針，到一個列表節點。一個單鏈表，其中列表主控者持有指向頭部和最後一個節點的指針就足夠了。從頭部提取並在尾部插入。在這裏保護插入和提取不受競爭條件的影響非常大，您只需要擔心列表長度非常短的情況。如果你真的有一個單線程的應用程序，那麼你根本不必擔心它。

我沒有任何實際的基準，並不能對任何庫實現任何建議，但是這兩種方法都是O（1）兩個插入和提取。首先是更多的緩存（和內存尋呼機）友好，除非你的隊列大小比它需要的大得多。第二種方法緩存友好性較低，因爲隊列中的每個成員都可以位於RAM的不同區域。

希望這有助於你評估或創建自己的隊列。

來源

2010-09-19 23:37:57 nategoose

隊列實現基準

回答

相關問題