比较两个非常大的列表的最佳方法

我有两个非常大的列表。说几百万个元素。这两个列表已经以相同的方式排序。现在我需要检查两个列表是否相等。这样做的最好方法是什么？现在我的想法是使用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

比较两个非常大的列表的最佳方法

回答

相关问题