[問題] linked/array list差別

看板java作者 (mcik)時間3月前 (), 3月前編輯推噓0(0018)
留言18則, 2人參與, 3月前最新討論串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, 3月前 , 1F

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

03/10 21:09, 3月前 , 18F
的話ArrayList都很有優勢,除非真的需要大量insert/remove
03/10 21:09, 18F
文章代碼(AID): #1YAU2KSv (java)
文章代碼(AID): #1YAU2KSv (java)