作者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/m.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