作者prott (mcik)
看板java
标题[问题] linked/array list差别
时间Thu Mar 10 19:27:14 2022
平常使用Array List都是来存放东西
今天看到Linked List
简单了解实用上的效率差异
Linked List 新增/删除
Array List 取资料用
-----------------------------------------------------
所以做了以下测试，想测试新增的时间
public static void main(String[] args) {
LinkedList<Integer> Linked = new LinkedList<Integer>();
ArrayList<Integer> Array = new ArrayList<Integer>();
long time1, time2, time3;
time1 = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
Linked.addFirst(i);
}
time2 = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
Array.add(i);
}
time3 = System.currentTimeMillis();
System.out.println("Linked()花了：" + (time2 - time1));
System.out.println("Array()花了：" + (time3 - time2));
}
(1)
照理来说应该是Linked比较快吧?
但为什麽当回圈数量越大到某个数量时，Linked时间会爆大量
反而Array比较快
(2)
另外发现上述测验一起执行与分开执行，效率也会有影响请问是因为记忆体的缘故吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 59.124.166.120 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/java/M.1646911636.A.739.html
※ 编辑: prott (59.124.166.120 台湾), 03/10/2022 19:28:11
2F：→ yoche2000: 感觉 append 这个动作同时有 maniputate (new entries) 03/10 20:29
3F：→ yoche2000: 也有 storing 03/10 20:29
5F：→ yoche2000: 这样看来应该跟记忆体/storage 有关 03/10 20:33
6F：→ yoche2000: 毕竟你的n很大 (? 03/10 20:34
7F：→ yoche2000: 如果这个推论正确那就可能表示 Storage/memory is more 03/10 20:35
8F：→ yoche2000: time-dominant 在这两者之间 我猜啦 03/10 20:35
9F：→ ssccg: 测效能不能用这麽...随便的程式码 03/10 20:50
10F：→ ssccg: ArrayList并不是用一个刚好大小的array，是有额外空间的 03/10 20:53
11F：→ ssccg: 每次不够用时会扩张成3/2倍大小，所以重新分配空间的次数随 03/10 20:54
12F：→ ssccg: 着n变大是会以指数减少的，省掉分配记忆体空间 03/10 20:59
13F：→ ssccg: 而LinkedList每次都是要分配新空间，且用的总空间也较大 03/10 20:59
14F：→ ssccg: 另外LinkedList是快在新增/删除List「中间」的元素，你用 03/10 21:01
15F：→ ssccg: ArrayList.add = addLast来比较根本就不对，如上所说实作上 03/10 21:02
16F：→ ssccg: addLast本来平均就会是ArrayList较快 03/10 21:03
17F：→ ssccg: 实务上来说已知大概的资料量，且多分配空间浪费的机会不大 03/10 21:06
18F：→ ssccg: 的话ArrayList都很有优势，除非真的需要大量insert/remove 03/10 21:09
20F：→ MonyemLi: edlist/ 03/17 14:19
21F：→ MonyemLi: 没大量移除需求，就不用考虑太多了 03/17 14:20
22F：推 jej: 简单来说就是请参考大学教的资料结构 03/17 21:27
23F：→ jej: ArrayList顾名思义就是阵列的演算法做的 03/17 21:27
24F：→ jej: LinkedList名称就和资料结构Linked List一样 03/17 21:27
25F：→ jej: 年轻时面试一家公司 他们的架构师说LinkedList效能好 03/17 21:27
26F：→ jej: 就很想吐他 根本就是依照情况 两种演算法各有自己快的地方 03/17 21:27
27F：→ jej: 所以九楼说原po的测试不严谨 03/17 21:28
28F：→ jej: 就是没有站在这两种演算法的角度测试效能 03/17 21:28
29F：推 ppc: 推s大 03/20 20:04