爲什麼不是LinkedList.Clear（）O（1）

我假設LinkedList.Clear（）是O（1）在我正在處理的項目上，因爲我使用LinkedList在我的消費者中排空BlockingQueue這需要高吞吐量，之後清除並重用LinkedList。爲什麼不是LinkedList.Clear（）O（1）

事實證明這種假設是錯誤的，因爲（OpenJDK的）代碼做這個：

Entry<E> e = header.next; 
    while (e != header) { 
     Entry<E> next = e.next; 
     e.next = e.previous = null; 
     e.element = null; 
     e = next; 
    }

這是一個有點出人意料，有什麼好的理由LinkedList.Clear不能簡單地「忘記」它的頭.next和header.previous成員？

來源

2011-03-01 Leri

http://www.docjar.com/html/api/java/util/LinkedList.java.html和諧有它O（1） – Bozho 2011-03-01 22:14:53

很好的解釋，你可以在這裏找到：http://stackoverflow.com/questions/575995 /清除IMPL功能於Java類，LinkedList的。回答Jason – smas 2011-03-01 22:49:01

在我看（建立1.7.0-EA-B84）在Eclipse版本的源代碼的上方都有此評論：

// Clearing all of the links between nodes is "unnecessary", but: 
// - helps a generational GC if the discarded nodes inhabit 
// more than one generation 
// - is sure to free memory even if there is a reachable Iterator

這使得它相當清楚他們爲什麼這樣做它，雖然我同意它將O（1）操作變成O（n）有點令人擔憂。

來源

2011-03-01 22:15:20

好的，謝謝 - 這些評論在1.6源代碼中沒有:-) – Leri 2011-03-01 22:24:52

讓我們只希望所有的節點都在RAM中的頁面上，否則...... – 2011-03-02 09:50:01

我看到這個問題的唯一解決方案將用自定義清除方法擴展該類。沒有那麼難做到（你可以偷看原始實現並刪除迭代），但仍然不是我想要做的事情。糟糕的API設計恕我直言。 – Voo 2011-03-05 03:42:39

因爲我似乎無法評論答案（？）：下一個和之前的指針無關緊要。由於沒有任何內部條目可以從任何GC根訪問，因此將收集整個結構。如果java使用了一個refcounting收集器，我們會陷入循環問題。

John Skeet指出正確的答案。

來源

2011-03-01 22:20:15

雖然我不是很深刻的印象，GC優化的原因 - 它顯然事與願違，你的情況 -

清算和再利用LinkedList的

不健全的權利。爲什麼不創建一個全新的LinkedList對象？

來源

2011-03-01 23:03:03 irreputable

部分通過舊列表的某個Entry節點的現有引用將繼續看到舊列表，並且將繼續遍歷它。（這與評論的第二部分有關，與GC無關。） – Oddthinking 2011-03-02 02:11:07

顯然，op沒有對列表進行另外的引用。 – irreputable 2011-03-02 05:35:02

你說得對，在這裏創建一個新的LinkedList只是擺脫了整個問題。最後我切換到一個ArrayList，其中有清楚（）有O（N），我們仍然測量它的執行效果更好，對於我們的具體情況，收集鏈接列表的垃圾僅產生150-200Mb /秒垃圾內部鏈表節點（通常我們不會在乎這些東西，但對於這個特定的應用程序，我們必須） – Leri 2011-03-02 19:02:47

爲什麼不是LinkedList.Clear（）O（1）

回答

相關問題