首先:为了确定两个集合的交集,您必须查看至少其中一个集合的所有条目(以确定它是否在另一个集合中)。没有任何神奇的方法可以告诉你在不到O(min(size(s1), size(s2))的时间内。完结撒花。
接下来要告诉面试官的事情是:“100万条目。你一定在开玩笑。现在是2023年,任何像样的硬件都可以在不到一秒钟内处理两个100万项设置”(当然:这仅适用于便宜比较的对象,例如此处的整数实例。如果oneRecord.equals(anotherRecord)
是超级昂贵的操作,则100万个条目在2023年仍可能是个问题)。
然后简要提到了解决这个问题的各种内置方法以及各种第三方库。但是避免另外两个答案犯的错误:指向计算相交的库根本不是将其作为此问题的“解决方案”出售的内容。
您知道,在编码方面: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上打印出来的20百万结果:
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倍的速度击败了流处理。还要注意:并行流在这里更快。当运行1百万个条目时,顺序流速度更快。
因此,我最初提到“100万条目不是性能问题”。这是一个非常重要的声明,因为它告诉面试官,您不是那些浪费时间微调不存在的性能问题的人之一。
s1.retainAll(s2)
? - user330315SortedSet
,您可以迭代这两个集合,推进一个迭代器或另一个迭代器,直到迭代器指向相等的元素。 - Andy Turner