爲什麼.NET中隊列的底層實現使用數組？

我正在閱讀C＃簡而言之，本書提到了Queue數據結構的底層實現使用了根據需要調整大小的數組。這個調整大小當然會有成本，所以我想知道使用它的理由是什麼，說雙鏈表是什麼？鑑於我們只關心第一個和最後一個元素，並且雙鏈表比數組更有效地調整大小，爲什麼要使用數組？一個數組會佔用較少的內存，但這是唯一的基本原理嗎？爲什麼.NET中隊列的底層實現使用數組？

編輯：對不起，才意識到這是這幾乎是完全相同的副本： Why are Stack<T> and Queue<T> implemented with an array? （他們的問題，甚至來自同一本書來了）。無論如何感謝您的答案！

來源

2013-08-21 GBleaney

你可以嘗試正確地實現這兩個，看看哪個實現更容易證明的辦法正常工作，給自己回答這個問題... –

@AlexeiLevenkov或者只是比較性能... – Servy

@Servy - 不錯的選擇。請注意，比較性能可能並不容易 - 合理的實現將具有相同的O（1）操作時間，並且需要知道很多GC以正確測量該部分的性能成本... –

將數組作爲循環緩衝區使用，對於可以假定爲具有最大大小的隊列來說更好。數組的增長是使它更加昂貴的部分，所以如果您假設隊列大小不會持續擴展，或者在創建隊列時提供了有效最大值，那麼使用數組僅適用於雙向鏈接列表。循環緩衝器的一個很好的說明（即甚至提到具體的隊列）存在於the all-knowing Wikipedia：

循環緩衝使一個很好的實施策略對於具有固定最大大小的隊列。如果隊列採用最大尺寸，那麼循環緩衝區是一個完全理想的實現;所有隊列操作都是恆定時間。但是，擴展循環緩衝區需要移位內存，這相對昂貴。爲了任意擴展隊列，可以使用鏈接列表方法。

總之，因爲大多數使用情況將不涉及任意擴大隊列，因爲，對於那些關注性能，最大可以從一開始，用作使用了環形緩衝器的背襯陣列來提供。

來源

2013-08-21 19:53:00

恕我直言，雙鏈表在概念上是美麗的。但理論上它需要爲每個節點分配一個隔離的內存塊，這非常昂貴。我相信任何雙鏈表的嚴重實現應該實際上使用預先分配的內存塊，根據需要按部分擴大/縮小。這就是爲什麼數組實際上是實現隊列的理想後端。

來源

2013-08-21 20:00:01 nim

這不僅是昂貴的常量分配，而且由於結構中的對象並不相鄰，所以會丟失內存局部性。這使得迭代一個數組（或者一個數組支持的'Stack' *比'LinkedList'快得多*不會發生在同一時間填充它的所有對象。兩者都具有相同的大O因子，但 – Servy

有些同意但是對於隊列，你不需要迭代 - 你只需要push和pop :-) – nim

在C＃中'隊列'執行'IEnumerable '因此實際上可以迭代。同時進行大量添加或刪除操作也很常見，這仍然受益於內存局部性。 – Servy

出於同樣的原因的一些其他的數據結構，如堆棧，哈希表，鄰接表等被使用數組代替鏈表實施：

隨着事實上的標準調整大小的策略，指數級增長，即使您從空數組開始並插入幾百萬個項目，您也只需要二十幾個調整大小操作。前幾個大小調整操作將只複製幾個字節。
隊列特別是很少增長沒有界限，所以你可以主要避免調整大小。
這不僅僅是更緊湊一些，常見值類型的參考類型的雙向鏈接列表（int）整體比等效數組大三倍，甚至沒有考慮每個對象的分配開銷。如果我們誠實並考慮到這些，我們必須添加一個或兩個單詞的每個節點的標題，所以它更像是4倍或5倍大。這使得該陣列可能存在的任何超量分配都變得越來越小。
由於連續性，數組使得各種緩存的使用效率大大提高。這實際上影響您可以在隊列上執行的任何操作，除非詢問其大小，包括調整大小。
所有這些列表節點將不得不分配和垃圾收集。雖然代GC應該使分配相當便宜，並且應該輕鬆地選取僅在隊列中花費很少時間的節點，但仍然是很多不必要的工作，並且如果隊列很大或很少使用，則許多節點在小GC之前存活從隊列的尾部彈出，所以就是這樣。

來源

2013-08-21 20:03:07 delnan

爲什麼.NET中隊列的底層實現使用數組？

回答

相關問題