提高Collections.Sort

Question

我在ArrayList中分揀百萬串（每串50個字符）與

final Comparator comparator= new Comparator<String>() { 

    public int compare(String s1, String s2) { 

    if (s2 == null || s1 == null) 
     return 0; 
    return s1.compareTo(s2); 
    } 
}; 

Collections.Sort(list,comparator); 

的平均時間是這樣的：1300毫秒

我怎樣才能加快步伐？

Answer 1

你沒有指定你使用的排序算法比其他排序算法更快（快速/合併與泡泡） 另外如果您在多核/多處理器機器上運行，您可以將排序分爲多個線程（再次完全取決於排序算法，但here's示例）

Answer 2

您可以對前兩個字符使用基數排序。如果你的前兩個字符是獨特的，你可以使用類似的東西。

List<String> strings = 
Map<Integer, List<String>> radixSort = 
for(String s: strings) { 
    int key = (s.charAt(0) << 16) + s.charAt(1); 
    List<String> list = radixSort.get(key); 
    if(list == null) radixSort.put(key, list = new ArrayList<String>()); 
    list.add(s); 
} 
strings.clear(); 
for(List<String> list: new TreeMap<Integer, List<String>>(radixSort).values()) { 
    Collections.sort(list); 
    strings.addAll(list); 
} 

Answer 3

如果您使用的是Java 6或下面你可以切換到Java 7，Java 7中得到加速，他們改變了排序算法TimSort執行在某些情況下更好（特別是它works well with partially sorted input） 。 Java 6及以下版本used MergeSort。

---

但是讓我們假設你使用的是Java 6.我試過三個版本：

Collections.sort（）：重複你所提供的比較器的運行我的機器上大約需要3.0秒 （包括讀取1,000,000個隨機生成的小寫ascii字符串的輸入）。

基數排序：建議其他答案Radix sort。我嘗試下面的代碼（假定的字符串均相同的長度，並且只有小寫ASCII）：

String [] A = list.toArray(new String[0]); 

for(int i = stringLength - 1; i >=0; i--) { 
    int[] buckets = new int[26]; 
    int[] starts = new int[26]; 
    for (int k = 0 ; k < A.length;k++) { 
    buckets[A[k].charAt(i) - 'a']++; 
    } 
    for(int k = 1; k < buckets.length;k++) { 
    starts[k] = buckets[k -1] + starts[k-1]; 
    } 
    String [] temp = new String[A.length]; 
    for(int k = 0; k < A.length; k++) { 
    temp[starts[A[k].charAt(i) - 'a']] = A[k]; 
    starts[A[k].charAt(i) - 'a']++; 
    }  
    A = temp; 
} 

大約需要29.0秒到我的機器上完成。我不認爲這是爲這個問題實現基數排序的最好方式 - 例如，如果您進行了最重要的數字排序，那麼您可以儘早終止唯一的前綴。而且在使用原地排序方面也會有一些好處（有一個關於此的好消息 - 「The troubles with radix sort are in implementation, not in conception」）。我想寫一個更好的基於基數的解決方案來做到這一點 - 如果我有時間，我會更新我的答案。

存儲分類排序：我還實施了Peter Lawrey的bucket sort解決方案的稍微修改版本。下面的代碼：

Map<Integer, List<String>> buckets = new TreeMap<Integer,List<String>>(); 
for(String s : l) { 
    int key = s.charAt(0) * 256 + s.charAt(1); 
    List<String> list = buckets.get(key); 
    if(list == null) buckets.put(key, list = new ArrayList<String>()); 
    list.add(s); 
} 
l.clear(); 
for(List<String> list: buckets.values()) { 
    Collections.sort(list); 
    l.addAll(list); 
} 

大約需要2.5秒完成我的機器上。我相信這個勝利來自於分區。

---

所以，如果切換到Java 7的TimSort不幫你，那麼我建議分區中的數據（使用類似bucket sort）。如果你需要更好的性能，那麼你也可以多線程處理分區。