我正在检查 org.apache.commons.collections4.ListUtils 类,并注意到代码如下:
public static <e> List<e> intersection(final List<? extends E> list1, final List<? extends E> list2) {
final List<e> result = new ArrayList<>();
List<? extends E> smaller = list1;
List<? extends E> larger = list2;
if (list1.size() > list2.size()) {
smaller = list2;
larger = list1;
}
final HashSet<e> hashSet = new HashSet<>(smaller);
for (final E e : larger) {
if (hashSet.contains(e)) {
result.add(e);
hashSet.remove(e);
}
}
return result;
}
我们知道为什么他们将较小的列表转换为哈希集并循环较大的列表吗?谢谢。
最佳答案
假设较小的列表有 M
个条目,较大的列表有 N
个条目,并且 Set 为您提供基本操作(添加、包含)的恒定时间访问。
如果我使用 Big O 表示法对该算法进行分类,则运行时将为 O(M+N)
和额外的内存消耗 O(M)
。
如果我们用较大的列表切换较小的列表,则有 2 个观察结果:
- 额外的内存使用量将增加到
O(N)
,因此这是不这样做的原因之一。 - 理论上,运行时不会改变,仍然是
O(M+N)
,但实际上,创建一组N
条目将是比迭代更繁重的操作。
如果您想验证这些假设,请尝试 JMH这是一个在 Java 中运行微基准测试的工具。
我使用 M=1000
、N=10000
对此进行了不科学的基准测试。这就是我得到的:
Benchmark (size) Mode Cnt Score Error Units
IntersectBench.larger 10000 avgt 5 190481.075 ± 6488.649 ns/op
IntersectBench.smaller 10000 avgt 5 125997.594 ± 1616.975 ns/op
有趣的值是在 Score
中,这里越小越好。 IntersectBench.smaller
与上面的算法相同,IntersectBench.larger
是交换列表的算法,并且删除了交换列表的优化。正如您所看到的,未优化的版本慢了 50%。
关于java - 为什么代码使用较小的列表实例化哈希集?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57579107/