内存和时间有效的方式来排序随机传入的数据

我需要排序来自不同的随机值列表（可重复的值）的数据到内存和时间有效的方式的唯一值列表（有数百个列表每个记录可以有多达数千个记录）。现在，我有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

内存和时间有效的方式来排序随机传入的数据

回答

相关问题