性能上的Java的ArrayList VS LinkedList的，属于只有创建/插入和排序 [英] Performance on Java ArrayList vs LinkedList, pertaining to only Creation/Insertion and sorting

问题描述

考虑以下code：

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();
    }
}

在这里对是一个自定义定义的数据结构。

where Pair is a custom defined data structure.

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

以上程序的输出：
创建的ArrayList：
已用时间=0.885秒

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

创建的LinkedList：
已用时间=9.617秒

Creating LinkedList: Time Elapsed = 9.617 seconds

排序的ArrayList：
已用时间=0.128秒

Sorting ArrayList: Time Elapsed = 0.128 seconds

LinkedList的排序：
已用时间=0.351秒

Sorting LinkedList: Time Elapsed = 0.351 seconds

我有点莫名其妙，COS直观，LinkedList的创作应该比ArrayList的更好。

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

有关排序，这还挺期待的，因为它在阿比说：
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 code：

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);
}

这个方法将被调用36次，如果你添十亿个对象到一个空的ArrayList中，其中有10我已经做了上生长（）和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, 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 VS LinkedList的，属于只有创建/插入和排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！