比較兩個非常大的列表的最佳方法

我有兩個非常大的列表。說幾百萬個元素。這兩個列表已經以相同的方式排序。現在我需要檢查兩個列表是否相等。這樣做的最好方法是什麼？現在我的想法是使用Assert.assertEquals比較行與行。比較兩個非常大的列表的最佳方法

for(int i=0;i<Math.max(list1.size(),list2.size()),i++){ 

Assert.assertEquals(list1.get(i),list2.get(i)); 
}

不幸的是，如果列表中有數百萬個對象，我擔心此解決方案的性能。此外，如果列表不相等，那麼我需要知道差異在哪裏。

有沒有更好，更快，更自信的解決方案來做到這一點？

來源

2017-08-19 EdXX

它是ArrayList還是LinkedList？ –

@RajuSharma ArrayList – EdXX

最後，如果列表相同，則是O（n）操作。所以，我會去的簡單方法，只需使用：

Assert.assertEquals(list1, list2);

這將依賴於List::equals的名單比較 - 我懷疑你能比這更有效的，除非你有關於列表內容的具體信息。

如果列表不相等，您應該會得到一個顯示差異的異常。

來源

2017-08-19 11:45:01 assylias

*如果列表不同，你應該得到一個異常，顯示差異。*聰明聰明:) – nullpointer

在衆多答案中，一個真正意義上的（imho）。 – GhostCat

缺少一件事......你可能想提一下使assert正常工作所需的先決條件。也許不是OP所需要的，但對於未來的讀者。 – GhostCat

更簡單的方法來做到這一點可轉動的列表的大小，你無論如何使用：

if(list1.size() > list2.size()) { 
    list1.removeAll(list2); 
    // print the list1 (discrepancies) 
    Assert.fail("Lists are not equal"); 
} else if 
...// same for list2.size() > list1.size() 
} else { 
    list1.removeAll(list2); 
    if(!list1.isEmpty()) { 
     // print the discrepancies 
     Assert.fail("Lists are not equal"); 
    } 
}

來源

2017-08-19 11:26:01 nullpointer

他主要是問性能。你的代碼在封面上做了很多事情。不知道這是多麼有幫助。 – GhostCat

你應該將它們存儲在二叉樹。與列表相比，搜索速度非常快。

來源

2017-08-19 11:28:06 user3808887

廢話。他在問如何有效比較兩個大名單。把它們變成樹木根本沒有幫助。 – GhostCat

的表現將主要取決於收集類和方法你會用演出呢。

至於你提到你的代碼，它是迭代和使用獲取列表的方法相比，我們需要知道哪個集合類，它實現列表具有更好的性能得到方法..

for(int i=0;i<Math.max(list1.size(),list2.size()),i++){ 
    Assert.assertEquals(list1.get(i),list2.get(i)); 
}

如果您使用的是列表已實施LinkedList get方法，則提取單個對象的執行順序爲O（n/4）平均值爲。

如果您正在使用列表實施ArrayList的 GET方法則表現爲了獲取一個對象將是O（1）。

因此，我們可以說基於您的代碼的比較將更快爲ArrayList。

來源

2017-08-19 11:40:29

* ArrayList獲取方法，那麼性能順序將是O（1）。*總體？ – nullpointer

@nullpointer是的，實現ArrayList的List的get方法比實現LinkedList的List有更好的性能 –

不是在這裏討論比較，而是即使我們做了一個「O（1）」，總體順序也不會是'O（1）在'ArrayList'上獲取''。 – nullpointer

這很簡單：當你想確保兩個列表相同時 - 你必須將它們按元素進行比較。當然，只有當兩個列表的大小相等時，您纔會這樣做。

因此，你總是處理O（n）。

而Java ArrayLists作爲數據結構已經是不錯的選擇。

唯一潛在的優化：通過使用多個線程比較子列表，可以更快地解決此問題。所以parallelStream（）可能是你的朋友。

或者 - 當列表包含int，double ...原始值時 - 那麼您可以考慮使用普通舊數組而不是基於集合的列表。

來源

2017-08-19 11:56:03 GhostCat

比較兩個非常大的列表的最佳方法

回答

相關問題