对于add方法的时间比较：数组列表，链表的ArrayList（有一些值初始化） [英] Time comparison of add method for: ArrayList, LinkedList, ArrayList (initialized with some value)

问题描述

我想更多地了解数据结构以及他们实现（在Java语言）。今天，我写了一个测试来比较（时间比较）ADT列表的不同实现。具体来说，我比较add方法，这里是我的测试：

I wish to know more about data structure and about their implementations (in JAVA language). Today I wrote a test to compare (time comparison) different implementations of the ADT List. Specifically I compared add method, here's my test:

@Test
public void testTime() {
    long i = 10000000;
    long INITIALIZED_VALUE=5000000;
    List<Integer> arrayBasedList = new ArrayList<Integer>();
    List<Integer> linkedBasedList = new LinkedList<Integer>();
    List<Integer> arrayBasedInitialedSizeList = new ArrayList<Integer> (INITIALIZED_VALUE);

    long t1 = System.currentTimeMillis();
    for (int index = 0; index <= i; index++) {
        arrayBasedList.add(index);
    }
    long t1End = System.currentTimeMillis() - t1;

    long t2 = System.currentTimeMillis();

    for (int index = 0; index <= i; index++) {
        linkedBasedList.add(index);
    }
    long t2End = System.currentTimeMillis() - t2;

    long t3 = System.currentTimeMillis();
    for (int index = 0; index <= i; index++) {
        arrayBasedInitialedSizeList.add(index);
    }
    long t3End = System.currentTimeMillis() - t3;

    System.out.println("ArrayBased: " + t1End);
    System.out.println("LinkedList:" + t2End);
    System.out.println("ArrayBasedInitializedSize: " + t3End);

    System.out.println("End");
}

和我得到这个结果：

ArrayBased：5681的LinkedList：12830 ArrayBasedInitializedSize：858

ArrayBased: 5681 LinkedList:12830 ArrayBasedInitializedSize: 858

为什么LinkedList的比ArrayList的执行慢？我想补充的方法，对于LinkedList的实现，比添加方法数组实现更快。

Why LinkedList is slower than ArrayList implementation? I thought that add method, for LinkedList implementation, was faster than add method for Array implementation.

任何人都可以解释我为什么数组比链表更快add方法？

Anyone can explain me why array is faster than linkedlist for the add method?

感谢

阿莱西奥

推荐答案

有两件事情在这里。

首先，您的时间是不可靠的，你有没有回暖每次运行前的code。 Java的优化和，因为它是运行，所以最初几次通过它比后来的运行慢得多编译code。你应该通过运行测试循环几百次，扔掉这些结果了，才做计时。

The first is that your timings are unreliable as you haven't "warmed up" the code before each run. Java optimizes and compiles code as it is run so the first few times through it are much slower than later runs. You should run through your test loops a few hundred times, throw those results away and then do the timings.

要尽管回答这个问题：

的LinkedList 是恒定的时候不管名单有多长，但每增加它做很多工作。它需要创建包装对象，将其插入到列表中，更新的引用，等等。

LinkedList is constant time no matter how long the list is but on each add it has to do a lot more work. It needs to create the wrapper object, insert it into the list, update references, etc.

在另一方面的ArrayList 只设置一个值到数组，然后递增大小计数器。只有当它需要重新分配阵列它然后必须做大量的工作。

On the other hand ArrayList just sets a value into the array and then increments the size counter. Only if it needs to re-allocate the array does it then have to do a lot of work.

做测试在开始添加新对象，结果虽然比较，你会看到事情的青睐链表摆越往后像现在的ArrayList 需要洗牌所有的值每一次。

Do the test adding new objects at the start and compare the results though and you will see things swing more back in the favor of linked lists as now ArrayList needs to shuffle up all the values every time.

也与你的第三个测试说明重新分配阵列的成本，通过事先知道大小ArrayList中变得更加高效。

The cost to reallocate the arrays is also illustrated with your third test, by knowing the size in advance the ArrayList becomes even more efficient.

大O记法讨论算法时是有用的，但你要明白这实际意味着，或者它可以是非常误导的。它谈论的经营秩序，而不是它实际上需要多长时间。 的ArrayList 和的LinkedList 都是O（1）对于大多数追加插入，的ArrayList 插入为O（n），如果它需要重新分配。

Big O notation is helpful when discussing algorithms, but you need to understand what it actually means or it can be very misleading. It's talking about the Order of the operation, not how long it actually takes. ArrayList and LinkedList are both O(1) for most append insertions, ArrayList insertion is O(n) if it needs to reallocate.

所有的O（1）说的是，它仍然需要的时间是相同的，不管有多少对象是在列表中。东西添加到10项列表的末尾，100项目清单，10000项列表，它仍然需要在同一时间。

All O(1) says is that it still takes the same amount of time no matter how many objects are in the list. Add something to the end of a 10 item list, 100 item list, 10000 item list it still takes the same time.

LinkedList的，虽然需要比ArrayList的确实更多的时间 - 尽管他们仍然有相同的O（1）为了

LinkedList though takes more time than ArrayList does - even though they still have the same O(1) order.

在事实上的速度差是这样的，即使你看看添加到列表的开始，其中LinkedList的是O（1）和ArrayList为O（n）ArrayList是仍快于小名单！

In fact the speed difference is such that even if you look at adding to the start of the list where LinkedList is O(1) and ArrayList is O(n) ArrayList is still faster for small lists!

要给予一定的思路（这只是一个例子，不要尝试，并采取精确计时出这个！）然后，如果所用的时间，以增加对LinkedList的为L和一个ArrayList的时间是一个那么总时间做在最后一个附加的L * 1，A * 1。要在一开始补充的是L * 1，A * N

To give some idea (this is just an example, don't try and take exact timings out of this!) then if the time taken to add for a LinkedList is L and the time for an ArrayList is A then the total time to do an add at the end is L*1, A*1. To add at the start is L*1, A*N.

所以，如果L / A＆LT; N，然后它实际上更快地使用，即使只是看O特性，你可能会认为你是最好使用LinkedList的一个ArrayList

So if L/A < N then its actually faster to use an ArrayList even though just looking at the O characteristics you might think you are better using the LinkedList.

（链表也为O（n），如果你需要随机访问读取，它可以是一个很大的因素太）。

(Linked list is also O(n) if you need random access reads, which can be a big factor too).

这篇关于对于add方法的时间比较：数组列表，链表的ArrayList（有一些值初始化）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！