看板 java 關於我們 聯絡資訊
平常使用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://www.ptt.cc/bbs/java/M.1646911636.A.739.html ※ 編輯: prott (59.124.166.120 臺灣), 03/10/2022 19:28:11
yoche2000: https://i.imgur.com/kXJlEUs.jpg 03/10 20:28
yoche2000: 感覺 append 這個動作同時有 maniputate (new entries) 03/10 20:29
yoche2000: 也有 storing 03/10 20:29
yoche2000: https://i.imgur.com/BMgkvSE.jpg 03/10 20:33
yoche2000: 這樣看來應該跟記憶體/storage 有關 03/10 20:33
yoche2000: 畢竟你的n很大 (? 03/10 20:34
yoche2000: 如果這個推論正確那就可能表示 Storage/memory is more 03/10 20:35
yoche2000: time-dominant 在這兩者之間 我猜啦 03/10 20:35
ssccg: 測效能不能用這麼...隨便的程式碼 03/10 20:50
ssccg: ArrayList並不是用一個剛好大小的array,是有額外空間的 03/10 20:53
ssccg: 每次不夠用時會擴張成3/2倍大小,所以重新分配空間的次數隨 03/10 20:54
ssccg: 著n變大是會以指數減少的,省掉分配記憶體空間 03/10 20:59
ssccg: 而LinkedList每次都是要分配新空間,且用的總空間也較大 03/10 20:59
ssccg: 另外LinkedList是快在新增/刪除List「中間」的元素,你用 03/10 21:01
ssccg: ArrayList.add = addLast來比較根本就不對,如上所說實作上 03/10 21:02
ssccg: addLast本來平均就會是ArrayList較快 03/10 21:03
ssccg: 實務上來說已知大概的資料量,且多分配空間浪費的機會不大 03/10 21:06
ssccg: 的話ArrayList都很有優勢,除非真的需要大量insert/remove 03/10 21:09
MonyemLi: edlist/ 03/17 14:19
MonyemLi: 沒大量移除需求,就不用考慮太多了 03/17 14:20
jej: 簡單來說就是請參考大學教的資料結構 03/17 21:27
jej: ArrayList顧名思義就是陣列的演算法做的 03/17 21:27
jej: LinkedList名稱就和資料結構Linked List一樣 03/17 21:27
jej: 年輕時面試一家公司 他們的架構師說LinkedList效能好 03/17 21:27
jej: 就很想吐他 根本就是依照情況 兩種演算法各有自己快的地方 03/17 21:27
jej: 所以九樓說原po的測試不嚴謹 03/17 21:28
jej: 就是沒有站在這兩種演算法的角度測試效能 03/17 21:28
ppc: 推s大 03/20 20:04