內存和時間有效的方式來排序隨機傳入的數據

我需要排序來自不同的隨機值列表（可重複的值）的數據到內存和時間有效的方式的唯一值列表（有數百個列表每個記錄可以有多達數千個記錄）。現在，我有2種方法內存和時間有效的方式來排序隨機傳入的數據

方法1-排序的數據來自於：

public List<ClassB> ListSorter1(List<ClassA> listA){ 
    List<ClassB> data = new ArrayList<>(); 
    for (ClassA a : listA) { 
     int idx = Collections.binarySearch(data, a.getValue()); 
     if (idx < 0) { 
      int ip = -(idx + 1); 
      data.add(ip, a.getValue()); 
     } 
    } 
}

方法2 - 讓所有的唯一數據，然後排序：

public List<ClassB> ListSorter2 (List<ClassA> listA){ 
    List<ClassB> data = new ArrayList<>(); 
    for (ClassA a : listA) { 
     if (!data.contains(a.getValue())) { 
      data.add(a.getValue()); 
     } 
    } 
    Collections.sort(data); 
}

我的問題當<ClassB>是簡單數據（整數）時，方法2的性能更好（比方法1快大約20％，內存使用大致相同），但只要我更改爲更復雜的類，排序列表所需的時間天空，比方法1多10倍（仍然是關於方法1）相同的內存使用情況），都使用相同的比較器功能。

爲什麼這種性能差異？
有沒有更有效的方法來做到這一點？

來源

2016-03-04 turrutia

看起來你可以只維護複雜java.util.TreeSet中 –

這不是完全清楚你所說的「一個更復雜的類是什麼意思「這裏......但是你可能想記錄每種情況下有多少個比較器調用。 –

將這些值添加到SortedSet中，這樣會更高效和更簡單。 –

首先奇怪的是方法1比方法2慢了20％，但我認爲它是在一個非常小的集合上測試的。

原因在方法2大經濟放緩的原因有兩個：

當你迭代data沒有排序，所以
contains方法要經過整個列表，以便找到元素 - 這是O（n）。 contains具有O（n）的複雜度，如果數據被排序，則它不計米，因爲它遍歷整個集合。因此，對於方法二是爲O（n^2）複雜

對於方法1，要管理有序列表，並且使用的是binarySearch這是O（LN（N））。所以，方法1具有的O（N * LN（N））

來源

2016-03-04 14:55:07 user987339

謝謝，我會繼續調查代碼 – turrutia

的可能改進，只要我得到足夠的代表，就可以做到這一點 – turrutia

內存和時間有效的方式來排序隨機傳入的數據

回答

相關問題