LinkedList 与 ArrayList 在维护有序列表方面的性能

2022-09-03 18:25:14

我想保持大小有序<= 10 ^ 6。每次添加新元素时,我都会调用方法来对列表中的新元素进行排序。据我所知,性能比.但是,由于我将经常调用方法,因此我已经了解到,在对列表进行排序时,它将表现得更好,并且将是一个更好的选择,因为没有元素的移动,例如(用作底层数据结构)。任何会更有效的建议。List<Integer>Collections.sort()ArrayListLinkedListsort()linkedListArrayListArrayListarray


答案 1

您可以在排序列表中使用以查找正确的插入点。ArrayList可能比LinkedList表现得更好,特别是对于较大的尺寸,但这很容易测试。Collections#binarySearch

我运行了各种方法的微基准测试:在每次插入后使用排序,或者使用二进制搜索插入正确的位置,同时使用ArrayList(AL)和LinkedList(LL)。我还添加了Commons TreeList和番石榴的TreeMultiset。

结论

  • 测试者中最好的算法是使用TreeMultiset,但严格来说它不是一个列表 - 下一个最好的选择是使用ArrayList + binarySearch。
  • ArrayList在所有情况下都比LinkedList表现得更好,后者花了几分钟时间才完成100,000个元素(ArrayList花了不到一秒钟的时间)。

最佳表现者守则,供参考:

@Benchmark public ArrayList<Integer> binarySearchAL() {
  ArrayList<Integer> list = new ArrayList<> ();

  Random r = new Random();
  for (int i = 0; i < n; i++) {
    int num = r.nextInt();
    int index = Collections.binarySearch(list, num);
    if (index >= 0) list.add(index, num);
    else list.add(-index - 1, num);
    current = list.get(0); //O(1), to make sure the sort is not optimised away
  }
  return list;
}

比特桶上的完整代码。

完整结果

“Benchmark”列包含所测试方法的名称(baseLine只是填充列表而不对其进行排序,其他方法具有显式名称:AL=ArrayList,LL=LinkedList,TL=Commons TreeList,treeMultiSet=guava),(n)是列表的大小,Score是以毫秒为单位所花费的时间。

Benchmark                            (n)  Mode  Samples     Score     Error  Units
c.a.p.SO28164665.baseLine            100  avgt       10     0.002 ±   0.000  ms/op
c.a.p.SO28164665.baseLine           1000  avgt       10     0.017 ±   0.001  ms/op
c.a.p.SO28164665.baseLine           5000  avgt       10     0.086 ±   0.002  ms/op
c.a.p.SO28164665.baseLine          10000  avgt       10     0.175 ±   0.007  ms/op
c.a.p.SO28164665.binarySearchAL      100  avgt       10     0.014 ±   0.001  ms/op
c.a.p.SO28164665.binarySearchAL     1000  avgt       10     0.226 ±   0.006  ms/op
c.a.p.SO28164665.binarySearchAL     5000  avgt       10     2.413 ±   0.125  ms/op
c.a.p.SO28164665.binarySearchAL    10000  avgt       10     8.478 ±   0.523  ms/op
c.a.p.SO28164665.binarySearchLL      100  avgt       10     0.031 ±   0.000  ms/op
c.a.p.SO28164665.binarySearchLL     1000  avgt       10     3.876 ±   0.100  ms/op
c.a.p.SO28164665.binarySearchLL     5000  avgt       10   263.717 ±   6.852  ms/op
c.a.p.SO28164665.binarySearchLL    10000  avgt       10   843.436 ±  33.265  ms/op
c.a.p.SO28164665.sortAL              100  avgt       10     0.051 ±   0.002  ms/op
c.a.p.SO28164665.sortAL             1000  avgt       10     3.381 ±   0.189  ms/op
c.a.p.SO28164665.sortAL             5000  avgt       10   118.882 ±  22.030  ms/op
c.a.p.SO28164665.sortAL            10000  avgt       10   511.668 ± 171.453  ms/op
c.a.p.SO28164665.sortLL              100  avgt       10     0.082 ±   0.002  ms/op
c.a.p.SO28164665.sortLL             1000  avgt       10    13.045 ±   0.460  ms/op
c.a.p.SO28164665.sortLL             5000  avgt       10   642.593 ± 188.044  ms/op
c.a.p.SO28164665.sortLL            10000  avgt       10  1182.698 ± 159.468  ms/op
c.a.p.SO28164665.binarySearchTL      100  avgt       10    0.056 ±  0.002  ms/op
c.a.p.SO28164665.binarySearchTL     1000  avgt       10    1.083 ±  0.052  ms/op
c.a.p.SO28164665.binarySearchTL     5000  avgt       10    8.246 ±  0.329  ms/op
c.a.p.SO28164665.binarySearchTL    10000  avgt       10  735.192 ± 56.071  ms/op
c.a.p.SO28164665.treeMultiSet        100  avgt       10    0.021 ±  0.001  ms/op
c.a.p.SO28164665.treeMultiSet       1000  avgt       10    0.288 ±  0.008  ms/op
c.a.p.SO28164665.treeMultiSet       5000  avgt       10    1.809 ±  0.061  ms/op
c.a.p.SO28164665.treeMultiSet      10000  avgt       10    4.283 ±  0.214  ms/op

对于 100k 个项目:

c.a.p.SO28164665.binarySearchAL    100000  avgt        6  890.585 ± 68.730  ms/op
c.a.p.SO28164665.treeMultiSet      100000  avgt        6  105.273 ±  9.309  ms/op

答案 2

由于java没有内置的多集,这是适合您情况的完美数据结构,我建议使用番石榴库中找到的TreeMultiset

多集允许重复的元素,树多集还将增加保持集合排序的好处。


推荐