[問題] linked/array list差別

看板java作者 (mcik)時間8月前 (), 8月前編輯推噓2(2027)
留言29則, 5人參與, 8月前最新討論串1/1
平常使用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

03/10 20:28, 8月前 , 1F

03/10 20:29, 8月前 , 2F
感覺 append 這個動作同時有 maniputate (new entries)
03/10 20:29, 2F

03/10 20:29, 8月前 , 3F
也有 storing
03/10 20:29, 3F

03/10 20:33, 8月前 , 4F

03/10 20:33, 8月前 , 5F
這樣看來應該跟記憶體/storage 有關
03/10 20:33, 5F

03/10 20:34, 8月前 , 6F
畢竟你的n很大 (?
03/10 20:34, 6F

03/10 20:35, 8月前 , 7F
如果這個推論正確那就可能表示 Storage/memory is more
03/10 20:35, 7F

03/10 20:35, 8月前 , 8F
time-dominant 在這兩者之間 我猜啦
03/10 20:35, 8F

03/10 20:50, 8月前 , 9F
測效能不能用這麼...隨便的程式碼
03/10 20:50, 9F

03/10 20:53, 8月前 , 10F
ArrayList並不是用一個剛好大小的array,是有額外空間的
03/10 20:53, 10F

03/10 20:54, 8月前 , 11F
每次不夠用時會擴張成3/2倍大小,所以重新分配空間的次數隨
03/10 20:54, 11F

03/10 20:59, 8月前 , 12F
著n變大是會以指數減少的,省掉分配記憶體空間
03/10 20:59, 12F

03/10 20:59, 8月前 , 13F
而LinkedList每次都是要分配新空間,且用的總空間也較大
03/10 20:59, 13F

03/10 21:01, 8月前 , 14F
另外LinkedList是快在新增/刪除List「中間」的元素,你用
03/10 21:01, 14F

03/10 21:02, 8月前 , 15F
ArrayList.add = addLast來比較根本就不對,如上所說實作上
03/10 21:02, 15F

03/10 21:03, 8月前 , 16F
addLast本來平均就會是ArrayList較快
03/10 21:03, 16F

03/10 21:06, 8月前 , 17F
實務上來說已知大概的資料量,且多分配空間浪費的機會不大
03/10 21:06, 17F

03/10 21:09, 8月前 , 18F
的話ArrayList都很有優勢,除非真的需要大量insert/remove
03/10 21:09, 18F

03/17 14:19, 8月前 , 19F

03/17 14:19, 8月前 , 20F
edlist/
03/17 14:19, 20F

03/17 14:20, 8月前 , 21F
沒大量移除需求,就不用考慮太多了
03/17 14:20, 21F

03/17 21:27, 8月前 , 22F
簡單來說就是請參考大學教的資料結構
03/17 21:27, 22F

03/17 21:27, 8月前 , 23F
ArrayList顧名思義就是陣列的演算法做的
03/17 21:27, 23F

03/17 21:27, 8月前 , 24F
LinkedList名稱就和資料結構Linked List一樣
03/17 21:27, 24F

03/17 21:27, 8月前 , 25F
年輕時面試一家公司 他們的架構師說LinkedList效能好
03/17 21:27, 25F

03/17 21:27, 8月前 , 26F
就很想吐他 根本就是依照情況 兩種演算法各有自己快的地方
03/17 21:27, 26F

03/17 21:28, 8月前 , 27F
所以九樓說原po的測試不嚴謹
03/17 21:28, 27F

03/17 21:28, 8月前 , 28F
就是沒有站在這兩種演算法的角度測試效能
03/17 21:28, 28F

03/20 20:04, 8月前 , 29F
推s大
03/20 20:04, 29F
文章代碼(AID): #1YAU2KSv (java)
文章代碼(AID): #1YAU2KSv (java)