Jon Skeet最近在他的博客上提出了一个有趣的编程主题:"There's a hole in my abstraction, dear Liza, dear Liza"(重点补充):
事实上,我有一套 - 一个
HashSet
。我想从中删除一些项目...许多项目可能根本不存在。实际上,在我们的测试用例中,“removals”集合中的所有项目都不在原始集合中。这听起来 - 实际上 - 非常容易编码。毕竟,我们有Set<T>.removeAll
来帮助我们,对吧?我们在命令行中指定“source”集的大小和“removals”集合的大小,并构建它们。源集仅包含非负整数;删除集仅包含负整数。我们测量使用
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"); } }
不是世界上最精确的秒表,但在这种情况下绰绰有余,正如您所看到的。这是代码:c:UsersJonTest>java Test 100 100 Time taken: 1ms
让我们从一个简单的工作开始:一个包含100个项目的源集,以及100个要删除的源:
c:UsersJonTest>java Test 1000000 300000 Time taken: 38ms
好吧,所以我们没想到它会变慢......显然我们可以提高一点。如何删除一百万件物品和300,000件物品?
c:UsersJonTest>java Test 300000 300000 Time taken: 178131ms
嗯。这看起来仍然很快。现在我觉得我有点残忍,要求它去除所有这些。让我们更轻松一点 - 300,000个源项目和300,000个删除:
HashSet<T>.removeAll
劳驾?差不多三分钟?哎呀!当然,从一个较小的集合中删除项目应该比我们在38ms内管理的项目更容易?
有人可以解释为什么会这样吗?为什么javadoc方法如此之慢?
这种行为(有些)记录在source.removeAll(removals);
中:
此实现通过在每个集合上调用size方法来确定哪个是此集合和指定集合中较小的集合。如果此set具有较少的元素,则实现迭代该集合,依次检查迭代器返回的每个元素以查看它是否包含在指定的集合中。如果包含它,则使用迭代器的remove方法从该集合中删除它。如果指定的集合具有较少的元素,则实现迭代指定的集合,使用此set的remove方法从该集合中移除迭代器返回的每个元素。
当你打电话给removals
时,这在实践中意味着什么:
source
集合的大小比remove
小,那么HashSet
的removals
方法被称为快速。source
集合的大小等于或大于removals.contains
,则调用Collection<Integer> removals = new HashSet<Integer>();
,这对于ArrayList来说很慢。快速解决:
an open bug
请注意,removeAll
与您描述的非常相似。底线似乎是它可能是一个糟糕的选择但不能改变,因为它在javadoc中有记录。
作为参考,这是public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
的代码(在Java 8中 - 尚未检查其他版本):
qazxswpoi