HashSet<T>.removeAll 方法出奇地慢
Jon Skeet最近在他的博客上提出了一个有趣的编程主题:“亲爱的Liza,亲爱的Liza,我的抽象中有一个漏洞”(着重号是后加的):
我有一套 —— 事实上是一套。我想从中删除一些项目...许多项目很可能不存在。实际上,在我们的测试用例中,“删除”集合中的任何项都不会位于原始集合中。这听起来 - 确实如此 - 非常容易编码。毕竟,我们有
Set<T>.removeAll
来帮助我们,对吧?HashSet
我们在命令行上指定“源”集的大小和“删除”集合的大小,并构建它们。源集仅包含非负整数;删除集仅包含负整数。我们使用 来衡量删除所有元素所需的时间,这不是世界上最准确的秒表,但在这种情况下已经绰绰有余,如您所见。代码如下:
System.currentTimeMillis()
import java.util.*; public class Test { public static void main(String[] args) { int sourceSize = Integer.parseInt(args[0]); int removalsSize = Integer.parseInt(args[1]); Set<Integer> source = new HashSet<Integer>(); Collection<Integer> removals = new ArrayList<Integer>(); for (int i = 0; i < sourceSize; i++) { source.add(i); } for (int i = 1; i <= removalsSize; i++) { removals.add(-i); } long start = System.currentTimeMillis(); source.removeAll(removals); long end = System.currentTimeMillis(); System.out.println("Time taken: " + (end - start) + "ms"); } }
让我们从给它一个简单的工作开始:一个包含100个项目的源代码集,以及100个要删除的项目:
c:UsersJonTest>java Test 100 100 Time taken: 1ms
好吧,所以我们没想到它会很慢...显然,我们可以把事情提高一点。要删除的 100 万个项目和 300,000 个项目的来源怎么样?
c:UsersJonTest>java Test 1000000 300000 Time taken: 38ms
嗯。这似乎仍然很快。现在我觉得我有点残忍,要求它做所有那些删除。让我们让它变得更容易一些 - 300,000个源项目和300,000个删除:
c:UsersJonTest>java Test 300000 300000 Time taken: 178131ms
对不起?将近三分钟?哎呀!当然,从较小的集合中删除项目应该比我们在38ms内管理的集合更容易吗?
有人能解释为什么会发生这种情况吗?为什么这种方法这么慢?HashSet<T>.removeAll