獲取列表的公共值計數

Question

我有兩個ArrayList<Long>巨大的大小約5,00,000在每個。我曾嘗試使用for循環使用list.contains(object)，但它需要太多時間。我試圖通過拆分一個列表和比較多個線程，但沒有找到有效的結果。

我需要沒有。兩個列表中相同的元素。

任何優化的方式？

Answer 1

您是否考慮過將您的元素放入HashSet而不是？這會使查找速度更快。這當然只有在你沒有重複的情況下才有效。

如果您有重複項，則可以構造HashMap，該值具有鍵值和計數值。

Answer 2

讓l1成爲第一個列表並且l2第二個列表。在大O表示法中，運行於O(l1*l2)

另一種方法是將一個列表插入到HashSet中，然後對另一個列表中的所有其他元素測試它是否存在於HashSet中。這將給出大致2*l1+l2 -> O(l1+l2)

Answer 3

一般機制將排序這兩個列表，然後迭代排序列表尋找匹配。

Answer 4

當你有很多元素時，一個列表不是一個有效的數據結構，當你搜索一個元素時，你必須使用一個更有效的數據結構。 例如樹或散列圖！

Answer 5

讓我們假設列表1有m個元素，列表2有n個元素，m> n。如果元素不是數字排序的，似乎它們不是，比較步驟的總數 - 即方法的成本 - 因子mxn - n^2/2。在這種情況下，成本因素約爲50000x49999。

保持這兩個列表的順序將是最佳解決方案。如果列表是有序的，這些比較的成本將是因子m。在這種情況下，大約是50000.當兩個列表都通過兩個遊標迭代時，可以實現最佳結果。此方法可用代碼表示如下：

int i=0,j=0; 
int count=0; 
while(i<List1.size() && j<List2.size()) 
{ 
    if(List1[i]==List2[j]) 
    { 
     count++; 
     i++; 
    } 
    else if(List1[i]<List2[j]) 
     i++; 
    else 
     j++; 
} 

如果您有可能一直保留列表，則此方法會有所不同。除此之外，我還認爲這是不可能的拆分和比較。