帶有可比較樹列表TreeSet

選項1：創建一個實現Comparable的列表，並在每次添加值時使用collections.sort（List l）對其進行排序。選項2：創建一個TreeSet（它始終保持自己的排序）。帶有可比較樹列表TreeSet

哪一個會更快？我問這個，因爲List給了我我需要的ListIterator選項，因爲它允許我在迭代時添加一個元素。

2011-08-07 aps

我的數據結構將有大約100-200個自定義對象。 – aps

你有多少次更新你的收藏[相對於其他OPS]？此外，TreeSet防止重複，List不 - 您對此問題的策略是什麼？ – amit

對不起，我說了一些不正確的東西。實際上，我的集合將在程序運行時間的最初10％內進行相當頻繁的更新，之後無需再進行排序，因爲對象的數量會變得或多或少保持不變。之後，我將更新對象的屬性。 – aps

最重要的區別：

Criterion  | List with Collections.sort | TreeSet 
----------------+----------------------------+--------- 
cost of adding | O(n log n)     | O(log n) 
equal sort keys | permitted     | eliminated as duplicates 
iteration  | bidirectional, can insert | unidirectional, can not insert

爲了沒有得到一個ConcurrentModificationException迭代時，插入一個元素，你可以這樣做：

for (E e : new ArrayList<E>(collection)) { 
    // some other code 

    collection.add(anotherE); 
}

來源

2011-08-07 06:38:48 meriton

此處使用TreeSet。

添加到TreeSet是一個log(n)操作。添加到列表是常量時間，但排序是n log(n)。

來源

2011-08-07 06:38:38

在TreeSet中插入會自動排序，所以它的log（n）對於treeset vs nlog（n）進行列表排序。 –

Collections.sort使用修改後的合併排序與n日誌（n）排序時間。如果您在每次添加時調用該方法，則可能會以n^2log（n）時間結束。而在TreeSet中的插入保證了log（n）。因此，如果您在每次添加時調用它，它將變爲n.log（n）。所以我會建議使用TreeSet來代替。但TreeSet不允許重複，因此可能會影響您的決定。

如果您使用的是List，那麼您可以使用Collections.sort而不是使用Collections.sort來優化;因爲您知道每次在列表中插入元素時，列表已經排序，因此在此處使用插入排序可以帶來更好的性能，因爲插入排序在這種情況下執行得更好。

來源

2011-08-07 06:41:59

我不需要重複。但是我需要在迭代時將對象添加到集合中。這就是我考慮List的原因。 – aps

帶有可比較樹列表TreeSet

回答

相關問題