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

Question

最近我参加了一个面试，被问了一个问题。

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

我的回复:

我将创建一个新的空集合。我给了他下面的解决方案，但他对此并不满意。他说有 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)).Period.

内

接下来要告诉面试官:“100 万个条目。你一定是在开玩笑。现在是 2019 年。任何像样的硬件都可以在不到一秒的时间内处理两个 100 万个条目”。 (当然:这只适用于比较便宜的对象，就像这里的 Integer 实例。如果 oneRecord.equals(anotherRecord) 是一个 super 昂贵的操作，那么 1百万条目在 2022 年可能仍然是个问题)。

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

你看，关于编码: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 毫秒。这是 2000 万美元在我的 Mac Book Pro 上打印出来的:

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 万个条目不是性能问题”。这是一个非常重要的声明，因为它告诉面试官您不是那种浪费时间微优化不存在的性能问题的人。