比從端點迭代ArrayList更快嗎？

使用這個Java代碼：比從端點迭代ArrayList更快嗎？

// create the items list 
    List<Item> items = new ArrayList<Item>(); 
    // ... (add some elements into the list so that it is not empty) 

    // iterating ArrayList<Item> from right to left we find the position 
    // based on the `if` condition satisfied for an item property 
    int pos = 0; 
    for (int j = items.size() - 1; j >= 0; j--) { 
     Item item = items.get(j); 
     if (item.property <= 7) { 
      pos = j + 1; break; 
     } 
    } 

    // add new item on the found above position 
    Item it = new Item(); 
    if (pos == items.size()) { 
     items.add(it); 
    } else { 
     items.add(pos, it); 
    }

我wodering如果這一說法Item item = items.get(j);會採取一些額外的時間，因爲所使用的ArrayList的執行。例如，假設我們需要將新項目添加到最後，然後通過在項目列表上調用get()將僅從左側進行迭代，這是多餘的。我期望使用Deque結構而不是ArrayList。

你能推薦什麼，也許我錯了，因爲新的元素也可以在開始時添加，儘管目標是從右側迭代到左側。

來源

2012-07-22 Sophie Sperner

我建議你使用LinkedList實現java.util.Deque在這裏檢查：http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html – 2012-07-23 14:53:27

對於ArrayList，操作get(i)，在（右）端的迭代和添加/刪除是便宜的（基本上是O（1）或分期O（1））。但是，在其他（左）端添加/刪除元素非常昂貴，並且需要每次都複製整個支持陣列。

所以如果你需要添加和刪除兩端，一定要使用ArrayDeque。對於所有操作而言，這基本上與ArrayList一樣便宜，但支持以便宜的方式在兩端添加。

請注意，如果您只想在列表的開始處添加/刪除，而不是在最後，您仍可以使用ArrayList，並且只是「向後」（因此，當您想在開始時添加某些內容時，你只需在最後添加它，當你想從右到左迭代時，實際上是從左到右迭代）。

使用add(Object, int)方法插入元素對於兩個數據結構都是O（n）（插入元素右側的所有元素都需要在數組中移動）。

另一種可能是使用LinkedList（它也實現了Deque）。您只需確保您不使用get(int)或其他任何將索引作爲int傳遞的方法，因爲這是O（n）。但是，添加/刪除/插入操作在列表中的所有位置都是O（1）（只要您已經有一個指向該位置的迭代器）。因此，對於代碼中的循環，請在列表上調用.listIterator()，進行適當的迭代並使用ListIterator.add(Object)方法插入元素。這對你的代碼總體來說是最便宜的解決方案。

編輯

我沒有注意到ArrayDeque不提供在中間插入的元素（雖然它可以，就像ArrayList）的方法。（謝謝A.H.）所以，如果你真的需要所有這些操作（插入開始，中間和結束），請使用LinkedList和ListIterator。

來源

2012-07-22 10:15:17

'ArrayDeque'將不起作用，因爲問題中的代碼插入到中間或末尾。 'ArrayDeque'可以在末尾或開頭插入_only_。 – 2012-07-22 10:24:31

Get ArrayList在恆定時間內運行。證明：javadoc。

大小，isEmpty，get，set，iterator和listIterator操作在恆定時間內運行。

所以不要擔心get的表現。 ArrayList不是一個鏈表。我認爲它是由一個普通的java數組備份的。

來源

2012-07-22 09:59:04

[它實際上由一個數組備份。]（http://www.docjar.com/html/api/java/util/ArrayList.java.html） – 2012-07-22 10:01:50

我擔心每毫秒，性能非常苛刻，所以也許有一些東西最好用來從右邊迭代，因爲我更可能在列表的末尾添加新項目，而不是像開頭那樣。 – 2012-07-22 10:02:34

你試着先嚐試對列表進行排序（在屬性值上使用比較器）。從內存中，它使用二進制排序，所以它應該是相當快的。你必須權衡遍歷列表花費的時間與執行排序所需的時間。 – MadProgrammer 2012-07-22 10:19:25

不，可能不是。你的for循環從右到左迭代，如果可能是最快的實現。

如果您使用LinkedList，那麼答案是肯定的 - 您應該使用listIterator（）向後迭代，因爲LinkedList上的.get（i）很慢。 ArrayList也有listIterator（），但是在使用它和簡單的for循環向後迭代之間可能幾乎沒有什麼不同。

如果你真的關心每一個ms，你應該把這個問題上的所有人都說出來，並且用一小撮鹽在互聯網上閱讀的基準測試，並運行大量的負載測試，並使用VisualVM進行大量分析以通知您系統中真正的性能瓶頸。

來源

2012-07-22 10:41:49 theon

比從端點迭代ArrayList更快嗎？

回答

相關問題