Java ArrayList 与 LinkedList 的性能，仅与创建/插入和排序有关 [英] Performance on Java ArrayList vs LinkedList, pertaining to only Creation/Insertion and sorting

问题描述

考虑以下代码:

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class testSortingSpeed {
    public static final int TOTAL_NUMBER = 10000000;

    public static void main(String[] args) {
        System.out.println("Creating ArrayList:");
        List<Pair<Integer, Integer>> a = new ArrayList<>();
        long start = System.currentTimeMillis();
        for (int i = 0; i < TOTAL_NUMBER; i++) {
            Pair<Integer, Integer> p = new Pair<>(
                (int ) Math.random() * TOTAL_NUMBER,
                (int ) Math.random() * TOTAL_NUMBER);
            a.add(p);
        }
        long end = System.currentTimeMillis();
        System.out.println("Time Elapsed = " + ((end - start) / 1000.0) + " seconds");
        System.out.println();

        System.out.println("Creating LinkedList:");
        List<Pair<Integer, Integer>> b = new LinkedList<>();
        start = System.currentTimeMillis();
        for (int i = 0; i < TOTAL_NUMBER; i++) {
            Pair<Integer, Integer> p = new Pair<>(
                (int ) Math.random() * TOTAL_NUMBER,
                (int ) Math.random() * TOTAL_NUMBER);
            b.add(p);
        }
        end = System.currentTimeMillis();
        System.out.println("Time Elapsed = " + ((end - start) / 1000.0) + " seconds");
        System.out.println();

        System.out.println("Sorting ArrayList:");
        start = System.currentTimeMillis();
        Collections.sort(a, Pair.LEXICOGRAPHIC_ORDER);
        end = System.currentTimeMillis();
        System.out.println("Time Elapsed = " + ((end - start) / 1000.0) + " seconds");
        System.out.println();

        System.out.println("Sorting LinkedList:");
        start = System.currentTimeMillis();
        Collections.sort(b, Pair.LEXICOGRAPHIC_ORDER);
        end = System.currentTimeMillis();
        System.out.println("Time Elapsed = " + ((end - start) / 1000.0) + " seconds");
        System.out.println();
    }
}

其中 Pair 是自定义定义的数据结构.

where Pair is a custom defined data structure.

Pair<F, S> { F first; S second; }

上述程序的输出:创建数组列表:已用时间 = 0.885 秒

The output of the above program: Creating ArrayList: Time Elapsed = 0.885 seconds

创建链表:已用时间 = 9.617 秒

Creating LinkedList: Time Elapsed = 9.617 seconds

排序ArrayList:已用时间 = 0.128 秒

Sorting ArrayList: Time Elapsed = 0.128 seconds

排序链表:已用时间 = 0.351 秒

Sorting LinkedList: Time Elapsed = 0.351 seconds

有点懵，因为直觉上，LinkedList的创建应该比ArrayList好.

I am a bit baffled, cos intuitively, LinkedList creation should be better than ArrayList.

对于排序，这在意料之中，正如它在 api 中所说:https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html那 Collections.sort将列表转储到 ArrayList，对其进行排序，并将其转换回原始列表类型(不确定)

For sorting, that's kinda expected, as it says in api: https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html that Collections.sort dumps the list to an ArrayList, sort it, and convert it back to original list type (not sure about this)

如果原始列表类型是 ArrayList，我想可能会有优化.

and I guess there is probably optimization if the original list type is ArrayList.

推荐答案

这将是特定于实现的，具体取决于 ArrayList 在您的平台上的增长方式……但在大多数平台上，它每次都会将其大小乘以 1.5 倍已达到容量.

This will be implementation specific, depending on how ArrayList grows on your platform... But on most platforms, it multiplies its size by a factor of 1.5 every time it's capacity is reached.

这是来自 JDK 1.8 的代码:

Here's the code from JDK 1.8:

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

如果您将一千万个对象添加到一个空的 ArrayList 中，该方法将被调用 36 次，该数组的默认初始容量为 10.我已经对grow() 和 Arrays.copyOf() 进行了一些分析，并且它们非常快，即使对于大型阵列也是如此.

This method will be called 36 times if you're adding ten million objects into an empty ArrayList, which has a default initial capacity of 10. I've done some profiling on grow() and Arrays.copyOf(), and they're very fast, even for large arrays.

另一方面，LinkedList 需要为每个添加到其中的元素分配一个新的 Node 对象——一千万次.这就是 LinkedList 在这种情况下较慢的原因.当您需要在列表的开头或中间附近的某处插入或删除元素时，它要快得多.

LinkedList, on the other hand, needs to allocate a new Node object for every element added to it--ten million times. That's why LinkedList is slower in this case. It's much faster when you need to insert or remove elements somewhere near the beginning or middle of the list.

这篇关于Java ArrayList 与 LinkedList 的性能，仅与创建/插入和排序有关的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！