PTT數位生活區 / java

[問題] linked/array list差別

看板java作者 (mcik)時間2年前 (2022/03/10 19:27), 2年前編輯推噓2(2推 0噓 27→)
留言29則, 5人參與, 2年前最新討論串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, 2年前 , 1F
03/10 20:28, 1F
→
03/10 20:29, 2年前 , 2F
感覺 append 這個動作同時有 maniputate (new entries)
03/10 20:29, 2F
→
03/10 20:29, 2年前 , 3F
也有 storing
03/10 20:29, 3F
→
03/10 20:33, 2年前 , 4F
03/10 20:33, 4F
→
03/10 20:33, 2年前 , 5F
這樣看來應該跟記憶體/storage 有關
03/10 20:33, 5F
→
03/10 20:34, 2年前 , 6F
畢竟你的n很大 (?
03/10 20:34, 6F
→
03/10 20:35, 2年前 , 7F
如果這個推論正確那就可能表示 Storage/memory is more
03/10 20:35, 7F
→
03/10 20:35, 2年前 , 8F
time-dominant 在這兩者之間 我猜啦
03/10 20:35, 8F
→
03/10 20:50, 2年前 , 9F
測效能不能用這麼...隨便的程式碼
03/10 20:50, 9F
→
03/10 20:53, 2年前 , 10F
ArrayList並不是用一個剛好大小的array，是有額外空間的
03/10 20:53, 10F
→
03/10 20:54, 2年前 , 11F
每次不夠用時會擴張成3/2倍大小，所以重新分配空間的次數隨
03/10 20:54, 11F
→
03/10 20:59, 2年前 , 12F
著n變大是會以指數減少的，省掉分配記憶體空間
03/10 20:59, 12F
→
03/10 20:59, 2年前 , 13F
而LinkedList每次都是要分配新空間，且用的總空間也較大
03/10 20:59, 13F
→
03/10 21:01, 2年前 , 14F
另外LinkedList是快在新增/刪除List「中間」的元素，你用
03/10 21:01, 14F
→
03/10 21:02, 2年前 , 15F
ArrayList.add = addLast來比較根本就不對，如上所說實作上
03/10 21:02, 15F
→
03/10 21:03, 2年前 , 16F
addLast本來平均就會是ArrayList較快
03/10 21:03, 16F
→
03/10 21:06, 2年前 , 17F
實務上來說已知大概的資料量，且多分配空間浪費的機會不大
03/10 21:06, 17F
→
03/10 21:09, 2年前 , 18F
的話ArrayList都很有優勢，除非真的需要大量insert/remove
03/10 21:09, 18F
→
03/17 14:19, 2年前 , 19F
03/17 14:19, 19F
→
03/17 14:19, 2年前 , 20F
edlist/
03/17 14:19, 20F
→
03/17 14:20, 2年前 , 21F
沒大量移除需求，就不用考慮太多了
03/17 14:20, 21F
推
03/17 21:27, 2年前 , 22F
簡單來說就是請參考大學教的資料結構
03/17 21:27, 22F
→
03/17 21:27, 2年前 , 23F
ArrayList顧名思義就是陣列的演算法做的
03/17 21:27, 23F
→
03/17 21:27, 2年前 , 24F
LinkedList名稱就和資料結構Linked List一樣
03/17 21:27, 24F
→
03/17 21:27, 2年前 , 25F
年輕時面試一家公司 他們的架構師說LinkedList效能好
03/17 21:27, 25F
→
03/17 21:27, 2年前 , 26F
就很想吐他 根本就是依照情況 兩種演算法各有自己快的地方
03/17 21:27, 26F
→
03/17 21:28, 2年前 , 27F
所以九樓說原po的測試不嚴謹
03/17 21:28, 27F
→
03/17 21:28, 2年前 , 28F
就是沒有站在這兩種演算法的角度測試效能
03/17 21:28, 28F
推
03/20 20:04, 2年前 , 29F
推s大
03/20 20:04, 29F
‣ 更多 prott 的文章
文章代碼(AID): #1YAU2KSv (java)
java 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 prott 的文章
文章代碼(AID): #1YAU2KSv (java)