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

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

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

我的回复:

我将创建一个新的空 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;
}

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

最佳答案

首先:为了确定两个集合的交集，您绝对必须查看两个集合中至少一个集合的所有条目(以确定它是否在另一个集合中)。周围没有魔法可以告诉你，在小于 O(min(size(s1), size(s2)) . 期间。
接下来要告诉面试官:“100 万个条目。你一定是在开玩笑。现在是 2019 年。任何像样的硬件都可以在不到一秒的时间内处理两个 100 万组”。
然后您简要提到有各种内置方法可以解决此问题，以及各种 3rd 方库。但是您避免了其他两个答案所犯的错误:指向计算相交的库是 根本不是 一些您作为该问题的“解决方案”出售的东西。
你看，关于编码:java Set 接口(interface)有一个简单的解决方案: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 万个条目不是性能问题”。这是一个非常重要的声明，因为它告诉面试官你不是那些浪费时间来微观优化不存在的性能问题的人之一。

关于java - 从 2 个集合中找到共同元素的最佳方法是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56488685/