在Java中設置vs數組vs vs鏈表的性能

-4

我想要在Java中研究表示集合，數組和鏈表的差異，因此我正在使用的示例是
如果我們需要查看常見兩個數組之間的對象，兩個集合和兩個鏈表，在我們應用for循環和比較的數組中，我們使用interscet或union？但是時間有很大的不同，有什麼想法？在Java中設置vs數組vs vs鏈表的性能

來源

2012-12-07 user1862650

如果問題是關於Java的，爲什麼要標記C++？您是否嘗試過在各種情況下測量各種結構的執行時間以瞭解答案？ – assylias

一些示例代碼呢？ – rmuller

@assylias：我可以想象，操作系統想要將結果與用C++編寫的相同測試進行比較。但是如果是這樣的話，他應該將其納入他的問題。 – Fildor

相交集和相交列表或數組之間存在差異。當你相交兩組時，你需要迭代其中的一組，並查看另一組中是否有對應的成員。設置的檢索時間爲O（1），所以交點爲O（n）。當交叉列表或數組時，交集爲O（n^2），因爲對於一個列表/數組中的每個成員，您需要遍歷整個其他列表/數組

來源

2012-12-07 12:31:11

設置的檢索時間是O（1） - 我不同意。您必須指定您正在使用的_which_集。哈希集？正確。樹設置的？不是一個機會。 –

甚至沒有，我不知道人們在哪裏學習和堅持，哈希提供O（1）查找。這不是真的！除非你有一個完美的散列讀取一個數組，否則你將總是得到一個散列，並且對一個散列桶的被散列元素進行線性搜索！哈希不會轉化爲固定時間！ –

在線性時間內保證交集的唯一方法是對兩個集進行排序並同時迭代兩者，這是線性的，請檢查它是如何在STL set_intersection中完成的。 –

我建議您準備一個測試牀爲microbenchmarking所以你可以看到時間的差異。確保運行至少10次重複，並在測量之外進行熱身。然後計算平均值和標準偏差。如果我沒有記錯，有一個漂亮的谷歌項目提供這個。

首先應該清楚你是漸近複雜性還是大O.如果你想做一組相交，最好的方法是。

SortedSet<String> set1 = new TreeSet<String>(); // and populate 
SortedSet<String> set2 = new TreeSet<String>(); // and populate 
// intersect of two sorted sets can be done in linear time

上述這是O（n），而你提到的其他選擇是爲O（n^2）閱讀糟糕的複雜性和更慢。

來源

2012-12-07 12:31:52

'HashSet'在這裏給出線性時間O（n），'TreeSet' n * logarithmic O（n * log n）。 –

不是真的，它取決於基礎hashCode（）實現的質量，如果碰到很多碰撞，您將以O（n^2）結尾。正確的O（n）方法是使用排序集，即使我不確定retainAll API在這種情況下是否會採用正確的方法。 –

retainAll只在'AbstractCollection'中實現，它循環並移除。你正在尋找的算法沒有在Java SE中實現，但是C++使用'std :: set_intersection'來實現它。同意'HashSet'中最糟糕的複雜性，但我們在這裏討論的是分期複雜性，在平均情況下，插入/查找將比線性時間表現更好。 –

在Java中設置vs數組vs vs鏈表的性能

回答

相關問題