为什么索引访问比 Java 中的 link 访问快？

Question

我正在比较 ArrayList 和 LinkedList 中 contains 方法在从 0 到 1000 的数字序列上的性能。

对于这两个列表，我都做了一个 contains(400)。 ArrayList 的性能总是比 LinkedList 高 3 倍。使用JMH进行比较。

ArrayList 花费了 329,642 纳秒

链表耗时 945,881 纳秒

如果两个列表都有 contains 方法的 O(n) 性能，为什么 LinkedList 差 3 倍？

比较class:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5)
public class Comparation {
    @State(Scope.Thread)
    public static class MyState {
        private List<Integer> arrayList = new ArrayList<>();
        private List<Integer> linkedList = new LinkedList<>();
        private int iterations = 1000;

        @Setup(Level.Trial)
        public void setUp() {
            for (int i = 0; i < iterations; i++) {
                arrayList.add(i);
                linkedList.add(i);
            }
        }
    }

    @Benchmark
    public boolean testLinkedListContains(MyState state) {
        return state.linkedList.contains(400);
    }
    @Benchmark
    public boolean testArrayListContains(MyState state) {
        return state.arrayList.contains(400);
    }
}

结果：

Benchmark                           Mode  Cnt    Score    Error  Units
Comparation.testArrayListContains   avgt   20  329,642 ± 20,709  ns/op
Comparation.testLinkedListContains  avgt   20  945,881 ± 43,621  ns/op

Answer 1

很简单：不同的数据结构有不同的性能权衡。

https://dzone.com/articles/arraylist-vs-linkedlist-vs

LinkedList is implemented as a double linked list. Its performance on add and remove is better than Arraylist, but worse on get and set methods.

换句话说，如果您的动机是不断地修改列表，LinkedList 可能是更好的选择。但是为了简单地 create 和 traverse 列表，ArrayList“获胜”。

继续：

As more elements are added to ArrayList, its size is increased dynamically. It's elements can be accessed directly by using the get and set methods, since ArrayList is essentially an array. ...

Vector and ArrayList require space as more elements are added. Vector each time doubles its array size, while ArrayList grow 50% of its size each time. ...

LinkedList, however, also implements Queue interface which adds more methods than ArrayList and Vector, such as offer(), peek(), poll(), etc.
...

Note: The default initial capacity of an ArrayList is pretty small. It is a good habit to construct the ArrayList with a higher initial capacity. This can avoid the resizing cost.

在这种情况下，数组速度更快..但灵活性较差。

Answer 2

在 ArrayList 中，数据由数组支持，数组的元素在内存中连续排列。所以自增迭代器是非常快的 -> 去内存中的下一个地址就可以了。

在LinkedList中，不一定是这样，内存不一定是连续的元素可能随机放在内存中，所以从一个元素到另一个元素会慢一点。

Answer 3

你的问题：如果两个列表的 contains 方法的性能都是 O(n)，为什么 LinkedList 差 3 倍？

这并不违反O(n)复杂度的规则，将O(n)视为描述具有线性时间的算法的事物。与您所相信的相反，这并不意味着这些算法的所有实现都具有相同的速度。这意味着他们花费的时间是他们输入的线性函数，这里 ArrayList 快三倍，但是如果你增加 List 中的元素数量你可以看到 ArrayList 仍然是三个时间更快，并且迭代它们的时间作为 List 中元素数量的线性函数增长。因此，如果您说 Arraylist 需要 2n 来执行该功能，而 LinkedList 需要 10000n 来执行该功能，您可以说它们都在 O(n) 中运行。

这里你正好得出了这个结论 LikedList 差了三倍，这意味着它们具有相同的复杂度 O(n)。

但是，如果通过增加输入的数量，你发现它不再是 3 倍更糟，而是变得更糟 5 倍或 30 倍，并且这个数字根据输入的数量（即 n）增长，它们没有相同的复杂度 O(n).

为什么索引访问比 Java 中的 link 访问快？

Why index accessing is faster than link access in Java?

java

linked-list

arraylist

jmh