1
我發現對於相當大的數組（超過1000個條目），方法A.removeAll(B)在HashSet上比在ArrayList上快得多。ArrayList vs HashSet中的removeAll（）
您是否瞭解如何實施這些方法以及如何解釋這種差異？
A
回答
6
一組（並因此HashSet以及）包含B至多一個元件，並且自HashSet使用散列這是相當有效的定位和移除元件。因此，總體複雜性應該是O(1)，用於刪除全部（即一個）B。
一個列表可以在任何位置包含任意數量的B，因此全部移除B必須檢查所有元素。總體複雜度爲O(n)，因爲如果它是B，則必須檢查每個元素。
編輯：
如果B代表的集合/陣列，即一組多個元素，你就應該由大小Bm乘以上述的複雜性，所以你會得到O(m)爲HashSet和O(n * m)爲名單。
編輯2：
請注意，如果你有一個排序列表的複雜性可能會降低到O(log(n))或O(log(n) * m)。對於這個工作代碼刪除實際元素將不得不知道列表雖然排序雖然ArrayList不保證排序它不能進行優化。
1
基本上兩者的原因是這些特定實現嘗試爲它們的專有操作實現時間複雜性。
爲ArrayList remove方法的時間複雜度爲O(n - index)source from When to use LinkedList over ArrayList?
雖然HashSet的remove方法提供了恆定的時間複雜度O(1)source from Hashset vs Treeset
相關問題
- 1. ArrayList中的removeAll
- 2. ArrayList中的Hashset或
- 3. HashSet與ArrayList
- 4. 從HashSet獲取ArrayList
- 5. ArrayList to Hashset to SharedPref
- 6. removeAll vs在knockoutjs中用[]清空數組
- 7. ArrayList vs HashSet vs HashMap以及有關數據結構設計的問題
- 8. ArrayList vs HashSet，這對內存性能更好？
- 9. ArrayList removeAll（）返回false。任何替代品？
- 10. Java：ListList的ArrayList，Map的HashMap和Set的HashSet？
- 11. 從HashSet到Arraylist的推土機映射
- 12. LinkedHashSet vs HashSet內存消耗
- 13. Java HashMap vs hashset性能
- 14. Json Multiset vs ArrayList
- 15. 字典vs ArrayList
- 16. 'Set = new HashSet'或'HashSet = new Hashset'？
- 17. 名單VS ArrayList的
- 18. LinkedHashMap vs HashMap！= LinkedList vs ArrayList
- 19. StringBuilder VS StringBuffer OR vector Vs ArrayList
- 20. 從HashSet的移動數據在Java中ArrayList的
- 21. 的Java Commons Collections中的removeAll
- 22. RemoveAll的用途（）
- 23. 使用的removeAll（）
- 24. HashSet的VS TreeSet的VS LinkedHashSet上添加重複值
- 25. 在HashSets的ArrayList中重新創建一個HashSet
- 26. 如何將HashSet轉換爲Java中的ArrayList？
- 27. Mongo嵌入式doc POJO：HashSet vs ArrayList
- 28. Scala vs Java性能（HashSet和bigram代）
- 29. 交換的HashSet TreeSet中和
- 30. ArrayList <> vs ArrayList <Integer>
所以你的意思是，在複雜的'ArrayList'是約0 （n2）？ – Arcyno
@Arcyno你從哪裏得到'O（n2）'（如'O（n * n）'）？如果你的意思是'B'是一個集合或數組，請參閱我的編輯。 – Thomas
沒有「ArrayList中的複雜性」這樣的事情。 'ArrayList'的具體操作具有特定的時間複雜性。 ArrayList * *去除*的時間複雜度通常被認爲是O（N）。 –