黑马程序员技术交流社区

标题: 关于ArrayList和 LinkedList集合的迭代时间问题 [打印本页]
作者: ixiangfeng    时间: 2013-10-19 14:27
标题: 关于ArrayList和 LinkedList集合的迭代时间问题
本帖最后由 ixiangfeng 于 2013-10-19 19:45 编辑

按理来说应该迭代ArrayList集合的时间要比迭代LinkedList集合的时间要大，但为什么下面这段代码测出来的结果好像相反的？请问下是什么原因



  1. import java.util.*;
  2. public class PerformanceTest
  3. {
  4. public static void main(String[] args)
  5. {
  6. //创建一个字符串数组
  7. String[] tst1 = new String[900000];
  8. //动态初始化数组元素
  9. for (int i = 0; i < 900000; i++)
  10. {
  11. tst1[i] = String.valueOf(i);
  12. }
  13. ArrayList al = new ArrayList();
  14. //将所有数组元素加入ArrayList集合中
  15. for (int i = 0; i < 900000 ; i++)
  16. {
  17. al.add(tst1[i]);
  18. }
  19. LinkedList ll = new LinkedList();
  20. //将所有数组元素加入LinkedList集合中
  21. for (int i = 0; i < 900000 ; i++)
  22. {
  23. ll.add(tst1[i]);
  24. }
  25. //迭代访问ArrayList集合的所有元素，并输出迭代时间
  26. long start = System.currentTimeMillis();
  27. for (Iterator it = al.iterator();it.hasNext() ; )
  28. {
  29. it.next();
  30. }
  31. System.out.println("迭代ArrayList集合元素的时间:"
  32. + (System.currentTimeMillis() - start));
  33. //迭代访问LinkedList集合的所有元素，并输出迭代时间
  34. start = System.currentTimeMillis();
  35. for (Iterator it = ll.iterator();it.hasNext() ; )
  36. {
  37. it.next();
  38. }
  39. System.out.println("迭代LinedList集合元素的时间:"
  40. + (System.currentTimeMillis() - start));
  41. }
  42. }

复制代码
结果：
迭代ArrayList集合元素的时间:14
迭代LinedList集合元素的时间:16

作者: ixiangfeng    时间: 2013-10-19 14:32
怎么字体都变了
作者: 周学彬    时间: 2013-10-19 14:43
ArrayList集合采用的是数组数据结构，在内存里面是一段连续的存储空间。LinkedList集合底层采用的是链表数据结构。楼主应该清楚这两种数据结构的特点吧。连续存储空间的遍历非常方便快捷，而链表结构在迭代下一个元素时，需要根据当前元素提供的内存地址去寻找下一个元素，在C语言里面的体现就是指针。所以我觉得效率会低些。

关于程序运行时间，影响的因素还有其他的，这是显而易见的
CPU性能。较老的CPU和较新的CPU迭代遍历时间肯定不同，但是这个对两种集合迭代的比较结果没什么影响。
还有，既然要比较两个集合的运行效率，为什么不把两个程序分开写单独比较呢？


作者: ixiangfeng    时间: 2013-10-19 15:02
周学彬 发表于 2013-10-19 14:43
ArrayList集合采用的是数组数据结构，在内存里面是一段连续的存储空间。LinkedList集合底层采用的是链表数 ...

数组以一块连续内存区来保存所有的数组元素，所以数组在随机访问时性能最好，所有的内部以数组作为底层实现的集合在随机访问时性能最好，例如ArrayList和ArrayDeque；  而内部以链表作为底层实现的集合在执行插入、删除等操作时有很好的性能，进行迭代操作时，以链表作为底层实现的集合（LinkedList）比以数组作为底层实现的集合(ArrayList)性能好.
这个程序只是单纯想测试一下两个集合的迭代性能，在这里你说的CPU性能应该不会对这两个集合的迭代时间有任何影响吧
作者: 周学彬    时间: 2013-10-19 15:11
ixiangfeng 发表于 2013-10-19 15:02
数组以一块连续内存区来保存所有的数组元素，所以数组在随机访问时性能最好，所有的内部以数组作为底层实 ...

数组结构和链表结构的迭代效率只是我的猜测。
你分析的增加删除元素的效率的对比十分正确，两种集合效率差异确实很大。你既然对这两个的内存结构如此清晰，应该不难想到在遍历两种集合时，是怎么样的一种情形吧。
我没有做过测试，但我搜索了一些文章，两种集合的迭代效率差的并不太多。有时候也会出现LinkedList比ArrayList效率高的情形。

我只是说CPU性能会影响所有集合的迭代效率，体现在时间上会有不同。我提到了对比较结果没有影响啊。
作者: 斗胆潇洒    时间: 2013-10-19 15:20
周学彬 发表于 2013-10-19 15:11
数组结构和链表结构的迭代效率只是我的猜测。
你分析的增加删除元素的效率的对比十分正确，两种集合效率 ...

是啊，cpu运行时，可能会影响啊，不信楼主在运行时，让电脑卡一下:lol
作者: ixiangfeng    时间: 2013-10-19 15:27
周学彬 发表于 2013-10-19 15:11
数组结构和链表结构的迭代效率只是我的猜测。
你分析的增加删除元素的效率的对比十分正确，两种集合效率 ...

一百次才几次出现ArrayList迭代时间比LinkedList时间长的，我一直觉得这个结果应该是相反的，但运行出来的结果却和我想的不一样 PS：谢谢你的回答
作者: 月夜之鬼魅    时间: 2013-10-19 16:59
ArrayList 底层是用数组实现的，更擅长遍历搜索查找，因为数组有下标的概念， 可以很方便的跳到指定的位置； 不擅长插入删除操作；
LinkedList 底层是用链表实现的， 链表是一个个节点链起来的， 擅长插入删除等操作（某节点断开去掉或者重新 连接上新的节点，这类操作比较快捷），搜索查询的话只能是一个节点一个节点的来。
你这个实验本来就不成立，做实验基本上只能需要一个变量，其他条件需要一样。你程序执行并不是一直执行的，cup在不停的做着切换，学多线程的时候就会了解到。
作者: 周志龙    时间: 2013-10-19 18:24

如果楼主已经解惑,请将帖子改为提问结束



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2