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

Question

我想维护一个有序的 List<Integer>，大小 <= 10^6。每次添加新元素时，我都会调用 Collections.sort() 方法对列表中的新元素进行排序。据我所知，ArrayList 比 LinkedList 表现更好。但是因为我会经常调用 sort() 方法，所以我开始理解 linkedList 在对列表进行排序时会表现得更好，并且比 ArrayList 更好，因为没有在 ArrayList 的情况下移动元素（使用 array 作为基础数据结构）。任何更有效的建议。

Answer 1

在 LinkedList 上调用 sort() 对性能是毁灭性的，因为 List.sort() 的默认实现将 List 转换为数组进行排序。在极少数情况下使用 LinkedList 是有意义的，即使它看起来应该有效。

如果您希望集合始终排序，您确实应该使用像 TreeSet 甚至 PriorityQueue 这样的有序集合。它将提供更清晰的代码（以及更快的排序），因为您不必一直担心自己调用 sort()。

Answer 2

您可以在排序后的列表中使用 Collections#binarySearch 来找到正确的插入点。 ArrayList 可能比 LinkedList 表现更好，尤其是对于大尺寸，但这很容易测试。

我运行各种方法的微观基准：在每次插入后使用排序或使用 binarySearch 在正确的位置插入，ArrayList (AL) 和 LinkedList (LL)。我还添加了 Commons TreeList 和 guava 的 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;
}

bitbucket 上的完整代码。

完整结果

"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

对于 10 万个项目：

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

Answer 3

由于 java 没有内置 multiset，这是适合您情况的完美数据结构，我建议使用 guava 库中的 TreeMultiset。

Multisets 允许重复元素，树 multiset 也将增加保持集合排序的好处。

Answer 4

在 Oracle Java / OpenJDK 7 或更高版本下，两者的渐近性能相似。 Collections.sort 将列表加载到数组中，对数组进行排序，然后通过迭代（使用 ListIterator）将数组加载回列表，替换其元素。

在这两种情况下，这是对大多数排序数组的数组排序（在 OpenJDK 7 及更高版本中是 O(n)，因为它使用 timsort），加上两个列表迭代（O(n) 在这两种情况下 - 尽管我希望 LinkedList 有一个更糟糕的常数项）。所以总的来说，这是一个 O(n) 过程，但 LinkedList.

可能会更慢

如果您要批量插入元素，批量插入总体上是 O(n^2)，这比全部插入并排序要慢，或者遵循 Smac89 的建议使用 TreeMultiset（两者都是 O(n log(n))）。

为了好玩，这里有一个非常糟糕的滥用 TreeSet 的方式来允许它存储重复的元素：

public class AwfulComparator<E extends Comparable<E>> implements Comparator<E> {
    public int compare(E o1, E o2) {
        int compared = o1.compareTo(o2);
        return (compared == 0)?1:compared; // Never compare equal
    }
}

new TreeSet<String>(new AwfulComparator<>());

Answer 5

如果排序是您主要的性能考虑因素，您应该考虑使用旨在保持顺序的数据结构。

使用正常的 Java 基础类您可以使用以下任一方法：

PriorityQueue (in case you want to retain duplicates)
TreeSet (filter duplicates)

无论如何，最简单的方法是对所有版本进行原型设计和运行一些基准测试+分析。

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

Performance of LinkedList vs ArrayList in maintaining an ordered list

java

sorting

linked-list

arraylist