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

Question

问题背景

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

我宁愿只使用 Java 8，没有外部库。

尝试次数

这是我最快的两种方法。第一个包含一堆逻辑，如果剩余元素无法满足阈值，则允许它停止（这总共节省了一点时间，但当然执行额外的逻辑也需要时间）。第二个比较慢。它没有那些优化，实际上确定交集而不是仅仅计算它，并使用流，这对我来说很新。
我有一个整数阈值和 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 并跟踪重复计数（我最初在 .count() .stream().allMatch() 结束，但这足以满足您的特殊情况）。添加每个项目后，我们检查我们是否不能满足阈值，在这种情况下我们抛出异常（可以说不是退出 .forEach() 的最漂亮的方式，但在在这种情况下，它是某种非法状态）。最后，我们 return 重复计数，或者 -1 如果遇到异常。在我的小测试中，将 0.5d 更改为 0.51d 以查看差异。

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

What is the most efficient way to count the intersections between two sets (Java)?

java

performance

intersection

count

set

问题背景

尝试次数