2年前 (2022-06-20)  Java系列 |   抢沙发  637 
文章评分 1 次,平均分 5.0
[收起] 文章目录

我有一个集合,实际上是一个HashSet。我想从中删除一些item…其中许多item可能不存在。事实上,在我们的测试用例中,“removals”集合中的所有项都不在原始集合中。这听起来——实际上也是——非常容易编码。毕竟,我们已经准备好了。removeAll来帮助我们,对吗?

让我们把它变成一个小测试。我们在命令行上指定“source”set的大小和“removals”集合的大小,并构建它们。source set合只包含非负整数;删除集仅包含负整数。我们使用系统测量删除所有元素所需的时间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个items的source set,以及要删除的100个items:

c:UsersJonTest>java Test 100 100
Time taken: 1ms

好吧,所以我们没想到会很慢……很明显,我们可以把速度提高一点。一百万件items和300000件items的来源如何?

c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms

嗯,看起来还是挺快的。现在我觉得我有点残忍,要求它做所有这些移除。让我们让它变得更简单一些–300000个source items和300000个删除:

c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms

快三分钟了?哎呀!当然,从一个较小的集合中删除items应该比我们在38ms内管理的集合更容易?嗯,最终这一切都是有道理的。HashSet扩展了AbstractSet,它在removeAll方法的文档中包含此代码段:

https://docs.oracle.com/javase/6/docs/api/java/util/AbstractSet.html#removeAll(java.util.Collection)

此实现通过调用每个集合上的size方法来确定此集合和指定集合中的较小者。如果此集合的元素较少,则实现将迭代此集合,依次检查迭代器返回的每个元素,以查看它是否包含在指定的集合中。如果它是这样包含的,则使用迭代器的remove方法将其从该集中移除。如果指定集合的元素较少,那么实现将迭代指定集合,使用该集合的remove方法从该集合中删除迭代器返回的每个元素。

从表面上看,这听起来很合理——遍历较小的集合,检查较大集合中是否存在。然而,这就是抽象存在漏洞的地方。仅仅因为我们可以要求一个item出现在一个大的集合中,并不意味着它会很快出现。在我们的例子中,集合的大小是相同的,但是检查哈希集中是否存在项是O(1),而在ArrayList中检查是O(N)…而每个集合的迭代成本是相同的。基本上,通过选择遍历HashSet并检查ArrayList中是否存在,我们得到了一个O(M*N)解决方案,而不是O(N)解决方案。removeAll方法基于在这种情况下无效的假设进行“优化”。

那么如何解决?

有两种简单的方法可以解决这个问题。首先,只需更改要从中删除的集合的类型。只需将ArrayList<Integer>更改为HashSet<Integer>,我们就可以回到34ms的范围。我们甚至不需要更改声明的删除类型。

第二种方法是更改我们使用的API:如果我们知道要迭代删除并在源代码中执行查找,那么很容易做到:

for (Integer value : removals)
{
    source.remove(value);
}

事实上,在我的机器上,它的性能略优于removeAll–它不需要在每次迭代时检查remove的返回值,removeAll这样做是为了返回是否删除了任何项。以上运行时间约为28ms。(我已经用相当大的数据集对其进行了测试,它确实比双哈希集方法更快。)

然而,这两种方法都需要在源代码中添加注释,以解释为什么我们没有使用最明显的代码(列表和删除)。我不能抱怨这里的文档——它确切地说明了它将做什么。在你遇到这样的问题之前,你根本不需要担心它。

那么,实现应该做什么呢?可以说,它真的需要知道它所处理的每一个集合中什么是便宜的。在决定策略之前探索性能特征的想法对于清理我们喜欢在Java集合之类的框架中考虑的抽象是完全不可取的……但在这种情况下,这可能是一个好主意。

 

除特别注明外,本站所有文章均为老K的Java博客原创,转载请注明出处来自https://javakk.com/2679.html

关于

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册