Java - 哪種集合在性能方面最適合這種情況？

我正在寫一個需要從文件中讀取字符串並將它們存儲在某個數據結構中的類。我應該使用以下幾點：Java - 哪種集合在性能方面最適合這種情況？

該文件將包含多達數百個字符串（它們需要存儲在一個結構中，不能流）。
條目需要按特定順序存儲。
一旦排序，集合將不會被修改（它不一定是不可變的，但我知道它不會被修改）。
我需要多次遍歷集合。
如果在集合中有重複條目，則只能存儲其中的一個。

以下answer（和其他人）說，一個ArrayList是更好，如果我只需要，因爲它讀取速度更快排序一次，但如果我用一個ArrayList那麼我將不得不確保他們手工是唯一的。

來源

2014-07-17 Adam

您可以將它們始終放置在「Set」中，這將不允許重複，然後將它們移動到ArrayList中以供後續使用。 – forgivenson

可以使用TreeSet。它是一個集合，所以它不會存儲重複的條目。它在插入時直接對條目進行排序。基本操作需要log(n)時間。因此，總體時間要求類似於首先插入列表，然後使用排序算法。

來源

2014-07-17 12:42:59 Jack

閱讀怎麼樣？ TreeSet的成本是否更高？ – Adam

對TreeSet的隨機元素的單一訪問將具有O（log n）複雜性 - 這比使用O（1）從ArrayList訪問元素更糟糕。但是，迭代時，整體複雜性應該更好（理想情況下整個迭代過程的O（n））。這假定迭代器實現足夠聰明，不會再爲每一個next（）調用從樹的頂部開始搜索。但是，我沒有在TreeSet JavaDocs中找到關於此事的任何聲明。 – Jack

如果您可以在插入時對元素進行排序，請考慮TreeSet（如果需要，可以使用自定義比較器）。如果沒有，看起來你可能需要兩種結構：

用於初始填充和排序的ArrayList。
之後，一個LinkedHashSet爲了確保奇點，同時保持秩序。

來源

2014-07-17 12:41:20 Ray

與ArrayList相比，LinkedHashSet在迭代集合方面有什麼優勢？ – Adam

你可能想使用LinkedHashSet，這是一個：

Hash table and linked list implementation of the Set interface, with predictable iteration order

...

This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet, without incurring the increased cost associated with TreeSet.

來源

2014-07-17 12:41:39

如果您可以隨時進行排序：將字符串插入到Set（最好是HashSet，我假設），然後將它們泄漏到ArrayList並進行排序。

來源

2014-07-17 12:44:19 Elazar

鑑於TreeSet在插入時對它們進行排序，是不是比排序ArrayList更快？ – Adam

這取決於你是否想要原始排序ciretiria。如果是這樣，你可能是對的。請注意，ArrayList比其他集合具有更好的局部性，因此排序應該更快一些。 – Elazar

我做了TreeSet與ArrayList插入/性能的基準測試。顯然，ArrayList表現更好，但是，擁有一百萬條獨特記錄，完整迭代時間爲279毫秒並不是那麼糟糕。

如果你的情況是微不足道的，我會堅持TreeSet。否則，在將元素插入到ArrayList之前，您將被迫重新輪詢並手動檢查重複項。

import java.util.ArrayList; 
import java.util.Iterator; 
import java.util.TreeSet; 

public class TestTreeSetVsArrayList { 
    public static int ENTRIES = 10000000; 

    public static void main(String[] args) { 
     TreeSet<String> treeSet = new TreeSet<String>(); 
     ArrayList<String> arrayList = new ArrayList<String>(10000); 
     long l = System.currentTimeMillis(); 
     for (int i = 0; i < TestTreeSetVsArrayList.ENTRIES; i++) { 
      treeSet.add("String"+i); 
     } 
     System.out.println("treeset insertion time: "+ (System.currentTimeMillis()-l)); 
     l = System.currentTimeMillis(); 
     for (int i = 0; i < TestTreeSetVsArrayList.ENTRIES; i++) { 
      treeSet.add("String"+i); 
     } 
     System.out.println("arraylist insertion time: "+ (System.currentTimeMillis()-l)); 

     Iterator<String> iter; 
     iter = treeSet.iterator(); 
     l = System.currentTimeMillis(); 
     while(iter.hasNext()) { 
      iter.next(); 
     } 
     System.out.println("treeset iteration time: "+ (System.currentTimeMillis()-l)); 

     iter = arrayList.iterator(); 
     l = System.currentTimeMillis(); 
     while(iter.hasNext()) { 
      iter.next(); 
     } 
     System.out.println("arraylist iteration time: "+ (System.currentTimeMillis()-l)); 

    } 

}

在我的電腦的結果是：

TreeSet的插入時間：11350

ArrayList中插入時間：3583

TreeSet的迭代次數：279

的ArrayList迭代時間：0

來源

2014-07-17 13:31:05

Java - 哪種集合在性能方面最適合這種情況？

回答

相關問題