从 2 个集合中找到共同元素的最佳方法是什么？

Question

最近我有一个面试，我被问到一个问题。

我有 2 套，每套大约有 100 万条记录。我必须在 2 个集合中找到公共元素。

我的回复：

我将创建一个新的空 Set。我给了他以下解决方案，但他对此并不满意。他说有 100 万条记录，所以解决方案不会很好。

public Set<Integer> commonElements(Set<Integer> s1, Set<Integer> s2) {
    Set<Integer> res = new HashSet<>();
     for (Integer temp : s1) {
        if(s2.contains(temp)) {
            res.add(temp);
        }
     }
     return res;
}

那么解决这个问题的更好方法是什么？

Answer 1

首先：为了确定两个集合的交集，您绝对必须查看两个集合中至少一个集合的所有条目（以确定它是否在另一个集合中）。周围没有任何魔法可以告诉你，在小于O(min(size(s1), size(s2))。周期。

接下来要告诉面试官：“100 万个条目。你一定是在开玩笑。现在是 2019 年。任何像样的硬件都可以在不到一秒的时间内处理两个 100 万组”。

然后您简要提到有各种内置方法可以解决此问题，以及各种 3rd 方库。但是您可以避免其他两个答案所犯的错误：指向计算相交的库根本不是您作为该问题的“解决方案”出售的东西。

你看，关于编码：java Set 接口有一个简单的解决方案：s1.retainAll(s2)计算两个集合的连接，因为它从 s1 中删除所有不在 s2 中的元素。

显然，您必须在采访中提到这将修改 s1。

如果要求不修改 s1 或 s2，您的解决方案是一种可行的方法，并且对于运行时成本没有任何办法。如果一切顺利，您可以调用size()两个集合并迭代条目较少的集合。

或者，你可以做

Set<String> result = new HashSet<>(s1);
return result.retain(s2);

但最后，您必须迭代一个集合，并为每个元素确定它是否在第二个集合中。

但是，当然，对此类问题的真正答案总是始终向面试官表明您能够将问题分解为不同的方面。您概述了基本约束，概述了不同的解决方案并讨论了它们的优缺点。以我为例，我希望你能坐下来写一个这样的程序：

public class Numbers {    
    private final static int numberOfEntries = 20_000_000;
    private final static int maxRandom = numberOfEntries;

    private Set<Integer> s1;
    private Set<Integer> s2;

    @Before
    public void setUp() throws Exception {
        Random random = new Random(42);
        s1 = fillWithRandomEntries(random, numberOfEntries);
        s2 = fillWithRandomEntries(random, numberOfEntries);
    }

    private static Set<Integer> fillWithRandomEntries(Random random, int entries) {
        Set<Integer> rv = new HashSet<>();
        for (int i = 0; i < entries; i++) {
            rv.add(random.nextInt(maxRandom));
        }
        return rv;
    }

    @Test
    public void classic() {
        long start = System.currentTimeMillis();
        HashSet<Integer> intersection = new HashSet<>();
          s1.forEach((i) -> {
           if (s2.contains(i))
             intersection.add(i);
        });
        long end = System.currentTimeMillis();
        System.out.println("foreach duration: " + (end-start) + " ms");
        System.out.println("intersection.size() = " + intersection.size());
    }


    @Test
    public void retainAll() {
        long start = System.currentTimeMillis();
        s1.retainAll(s2);
        long end = System.currentTimeMillis();
        System.out.println("Retain all duration: " + (end-start) + " ms");
        System.out.println("intersection.size() = " + s1.size());
    }

    @Test
    public void streams() {
        long start = System.currentTimeMillis();
        Set<Integer> intersection = s1.stream().filter(i -> s2.contains(i)).collect(Collectors.toSet());
        long end = System.currentTimeMillis();
        System.out.println("streaming: " + (end-start) + " ms");
        System.out.println("intersection.size() = " + intersection.size());
    }

    @Test
    public void parallelStreams() {
        long start = System.currentTimeMillis();
        Set<Integer> intersection = s1.parallelStream().filter(i -> s2.contains(i)).collect(Collectors.toSet());
        long end = System.currentTimeMillis();
        System.out.println("parallel streaming: " + (end-start) + " ms");
        System.out.println("intersection.size() = " + intersection.size());
    }
}

这里的第一个观察结果：我决定运行2000 万个条目。我从 200 万开始，但所有三个测试的运行时间都远低于 500 毫秒。这是我的 Mac Book Pro 上 2000 万的打印结果：

foreach duration: 9304 ms
intersection.size() = 7990888 
streaming: 9356 ms
intersection.size() = 7990888
Retain all duration: 685 ms
intersection.size() = 7990888
parallel streaming: 6998 ms
intersection.size() = 7990888

正如预期的那样：所有相交具有相同的大小（因为我播种了随机数生成器以获得可比较的结果）。

令人惊讶的是：就地修改 s1 ... 是迄今为止最便宜的选择。它比流式传输快 10倍。另外请注意：这里的并行流式传输速度更快。当运行 100 万个条目时，顺序流速度更快。

因此，我最初提到要提到“100 万个条目不是性能问题”。这是一个非常重要的声明，因为它告诉面试官你不是那些浪费时间来微观优化不存在的性能问题的人之一。