计算两个集合之间交集的最有效方法是什么(Java)

Question

问题背景

我正在比较两个（一次，实际上是很多）文本文件，我想确定它们的相似程度。为了做到这一点，我从每个文件中创建了小的、重叠的文本组。我现在想从一个文件中确定这些组的数量，这些组也来自另一个文件。

我更喜欢只使用没有外部库的Java 8。

尝试

这是我最快的两种方法。第一个包含一组逻辑，如果其余元素无法达到阈值，则允许它停止（这总共节省了一点时间，但执行额外的逻辑当然也需要时间）。第二个比较慢。它没有这些优化，实际上确定了交集，而不仅仅是计算它，并使用了一个流，这对我来说是全新的。
我有一个integer threshold和dblThreshold（相同的值转换为双精度），它们是必须共享才能感兴趣的较小文件的最小百分比。此外，从我有限的测试来看，似乎为任何一个较大的集合编写所有逻辑都比用反向参数再次调用方法更快。

public int numberShared(Set<String> sOne, Set<String> sTwo) {
    int numFound = 0;
    if (sOne.size() > sTwo.size()) {
        int smallSize = sTwo.size();
        int left = smallSize;
        for (String item: sTwo) {
            if (numFound < threshold && ((double)numFound + left < (dblThreshold) * smallSize)) {
                break;
            }
            if (sOne.contains(item)) {
                numFound++;
            }
            left--;
        }
    } else {
        int smallSize = sOne.size();
        int left = smallSize;
        for (String item: sOne) {
            if (numFound < threshold && ((double)numFound + left < (dblThreshold) * smallSize)) {
                break;
            }
            if (sTwo.contains(item)) {
                numFound++;
            }
            left--;
        }
    }
    return numFound;
}

第二种方法：

public int numberShared(Set<String> sOne, Set<String> sTwo) {
    if (sOne.size() < sTwo.size()) {
        long numFound = sOne.parallelStream()
                            .filter(segment -> sTwo.contains(segment))
                            .collect(Collectors.counting());
        return (int)numFound;
    } else {
        long numFound = sTwo.parallelStream()
                            .filter(segment -> sOne.contains(segment))
                            .collect(Collectors.counting());
        return (int)numFound;
    }
}

任何关于改进这些方法的建议，或解决问题的新颖想法和方法，我们都将不胜感激！

编辑：我刚刚意识到我的阈值检查的第一部分（在某些情况下，它试图消除对第二次双重检查的需要）是不正确的。我会尽快修改的。

Answer 1

如果我理解正确，您已经确定了哪些方法最快，但不确定在使用Java 8流时如何实现阈值检查。这里有一种方法可以做到这一点——尽管请注意，如果没有适当的数据和知道你感兴趣的阈值，我很难做很多测试，所以对这个简化的测试用例持保留态度（并根据需要进行调整）。

public class Sets {
    private static final int NOT_ENOUGH_MATCHES = -1;
    private static final String[] arrayOne = { "1", "2", "4", "9" };
    private static final String[] arrayTwo = { "2", "3", "5", "7", "9" };
    private static final Set<String> setOne = new HashSet<>();
    private static final Set<String> setTwo = new HashSet<>();
    public static void main(String[] ignoredArguments) {
        setOne.addAll(Arrays.asList(arrayOne));
        setTwo.addAll(Arrays.asList(arrayTwo));
        boolean isFirstSmaller = setOne.size() < setTwo.size();
        System.out.println("Number shared: " + (isFirstSmaller ?
                numberShared(setOne, setTwo) : numberShared(setTwo, setOne)));
    }
    private static long numberShared(Set<String> smallerSet, Set<String> largerSet) {
        SimpleBag bag = new SimpleBag(3, 0.5d, largerSet, smallerSet.size());
        try {
            smallerSet.forEach(eachItem -> bag.add(eachItem));
            return bag.duplicateCount;
        } catch (IllegalStateException exception) {
            return NOT_ENOUGH_MATCHES;
        }
    }
    public static class SimpleBag {
        private Map<String, Boolean> items;
        private int threshold;
        private double fraction;
        protected int duplicateCount = 0;
        private int smallerSize;
        private int numberLeft;
        public SimpleBag(int aThreshold, double aFraction, Set<String> someStrings,
                int otherSetSize) {
            threshold = aThreshold;
            fraction = aFraction;
            items = new HashMap<>();
            someStrings.forEach(eachString -> items.put(eachString, false));
            smallerSize = otherSetSize;
            numberLeft = otherSetSize;
        }
        public void add(String aString) {
            Boolean value = items.get(aString);
            boolean alreadyExists = value != null;
            if (alreadyExists) {
                duplicateCount++;
            }
            items.put(aString, alreadyExists);
            numberLeft--;
            if (cannotMeetThreshold()) {
                throw new IllegalStateException("Can't meet threshold; stopping at "
                        + duplicateCount + " duplicates");
            }
        }
        public boolean cannotMeetThreshold() {
            return duplicateCount < threshold
                    && (duplicateCount + numberLeft < fraction * smallerSize);
        }
    }
}

因此，我制作了一个简化的"Bag-like"实现，它从映射为false值的键的较大集合的内容开始（因为我们知道每个值只有一个）。然后，我们对较小的集合进行迭代，将每个项目添加到袋子中，如果它是重复的，则将值切换为true并跟踪重复计数（我最初在.stream().allMatch()的末尾做了一个.count()，但这足以满足您的特殊情况）。添加每个项目后，我们检查是否不能达到阈值，在这种情况下，我们抛出异常（可以说不是退出.forEach()的最漂亮的方式，但在这种情况中，是某种非法状态）。最后，我们返回重复计数，如果遇到异常，则返回-1。在我的小测试中，将0.5d更改为0.51d以查看差异。