ArrayList Vs LinkedList [英] ArrayList Vs LinkedList
问题描述
我关注了以前的讯息说：
对于LinkedList
For LinkedList
- get is O（n）
- add is O（1）
- remove is O（n）
- 迭代器.remove is O（1）
- get is O(n)
- add is O(1)
- remove is O(n)
- Iterator.remove is O(1)
对于ArrayList
For ArrayList
- get是O（1）
- add是O（1）摊销，但O（n）是最坏情况，因为数组必须调整大小和复制
- remove是O（n）
如果我只是在我的集合中做序列插入说5000000个元素， LinkedList 将outclass ArrayList 。
So by looking at this, I concluded that if I've to do just sequential insert in my collection for say 5000000 elements, LinkedList will outclass ArrayList.
如果我只是从集合中获取元素通过迭代，即不抓住中间的元素，仍然 LinkedList 将outclass`ArrayList。
And if I've to just fetch the elements from collection by iterating i.e. not grabbing the element in middle, still LinkedList will outclass `ArrayList.
现在要验证我上面的两个语句，我写下面的示例程序...但我很惊讶，我的上述语句被证明是错误的。
Now to verify my above two statements, I wrote below sample program… But I'm surprised that my above statements were proven wrong.
ArrayList outclassed Linkedlist 它花费的时间少于 LinkedList 用于添加以及从集合中提取它们。有什么我做错了，或者关于 LinkedList 和 ArrayList 的初始语句不适用于集合size 5000000？
ArrayList outclassed Linkedlist in both the cases. It took less time than LinkedList for adding as well as fetching them from Collection. Is there anything I'm doing wrong, or the initial statements about LinkedList and ArrayList does not hold true for collections of size 5000000?
我提到size，因为如果我将元素数减少到50000， LinkedList 初始语句为真。
I mentioned size, because if I reduce the number of elements to 50000, LinkedList performs better and initial statements hold true.
long nano1 = System.nanoTime();
List<Integer> arr = new ArrayList();
for(int i = 0; i < 5000000; ++i) {
arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );
for(int j : arr) {
;
}
System.out.println( (System.nanoTime() - nano1) );
long nano2 = System.nanoTime();
List<Integer> arrL = new LinkedList();
for(int i = 0; i < 5000000; ++i) {
arrL.add(i);
}
System.out.println( (System.nanoTime() - nano2) );
for(int j : arrL) {
;
}
System.out.println( (System.nanoTime() - nano2) );
推荐答案
请记住big-O复杂性描述渐近行为，不反映实际执行速度。它描述了每个操作的成本如何随着列表的大小而增长，而不是每个操作的速度。例如， add 的以下实现是O（1），但不快：
Remember that big-O complexity describes asymptotic behaviour and may not reflect actual implementation speed. It describes how the cost of each operation grows with the size of the list, not the speed of each operation. For example, the following implementation of add is O(1) but is not fast:
public class MyList extends LinkedList {
public void add(Object o) {
Thread.sleep(10000);
super.add(o);
}
}
$ b $ p我怀疑在你的case ArrayList表现良好，因为它相当积极地增加它的内部缓冲区大小，所以不会有大量的重新分配。当缓冲区不需要调整大小时，ArrayList将有更快的添加。
小心当你做这种剖析。我建议您更改您的性能分析代码，以做一个热身阶段（所以JIT有机会做一些优化，而不会影响你的结果）和平均结果在一些运行。
You also need to be very careful when you do this kind of profiling. I'd suggest you change your profiling code to do a warm-up phase (so the JIT has the opportunity to do some optimization without affecting your results) and average the results over a number of runs.
private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;
public void perfTest() {
// Warmup
for (int i = 0; i < WARMUP; ++i) {
buildArrayList();
}
// Test
long sum = 0;
for (int i = 0; i < TEST; ++i) {
sum += buildArrayList();
}
System.out.println("Average time to build array list: " + (sum / TEST));
}
public long buildArrayList() {
long start = System.nanoTime();
ArrayList a = new ArrayList();
for (int i = 0; i < SIZE; ++i) {
a.add(i);
}
long end = System.nanoTime();
return end - start;
}
... same for buildLinkedList
sum 可能溢出，你最好使用 System.currentTimeMillis（））。
(Note that sum may overflow and you might be better to use System.currentTimeMillis()).
这也可能是编译器优化你的空的 get 循环。确保循环实际上能够确保正确的代码被调用。
It's also possible that the compiler is optimizing away your empty get loops. Make sure the loop actually does something to ensure that the right code is getting called.
这篇关于ArrayList Vs LinkedList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
