找出两个排序列表是否包含相同元素 Java 的有效方法。

Question

我有一个搜索互素数的紧密循环。一个列表 primeFactors。它的第 n 个元素包含 n 的质数分解的排序列表。我正在使用 checkIfPrimes

检查 c 和 d 是否互质

boolean checkIfPrimes(int c, int d, List<List<Integer>> primeFactors) {
    List<Integer>  common = new ArrayList<>(primeFactors.get(d)); //slow
    common.retainAll(primeFactors.get(c));        
    return (common.isEmpty());
}

primeFactors.get(d).retainAll(primeFactors.get(c)) 看起来很有希望，但它会改变我的可重用 primeFactors 对象。

创建新对象相对较慢。有没有办法加快这一步？我能以某种方式利用列表已排序的事实吗？我应该改用数组吗？

Answer 1

通常您可以使用布尔数组。其中数组的索引是布尔值 returns true 的数字和值，否则是 false.

Answer 2

您可以使用 Collection 进行更快的查找 - 例如Set 如果您只需要不重复的质因数，或者 Map 如果您还需要每个因子的计数。

基本上，你想知道两个Set的交集是否为空。 Oracle Set tutorial 显示了一种计算交集的方法（类似于您已经提到的，在副本上使用 retainAll，但在集合上操作应该更有效）。

Answer 3

您可以按照以下方式做一些事情：

List<Integer> commonElements = 
       primeFactors.get(d).stream()
                          .filter(primeFactors.get(c)::contains)
                          .collect(Collectors.toList());

衡量此性能后，您可以用 'parallelStream()' 替换上面的 'stream()'，看看您获得了哪些好处。

Answer 4

集合操作应该比数组操作更快。只是为了好玩，考虑尝试一下并将性能与流性能进行比较：

final Set<Integer> commonSet;
final Set<Integer> cSet = new HashSet<Integer>();
final Set<Integer> dSet = new HashSet<Integer>();

cSet.addAll(primeFactors.get(c));
dSet.addAll(primeFactors.get(d));

commonSet = dSet.retainAll(cSet);

return (commonSet.isEmpty());

此外，考虑使用 List<Set<Integer>> primeFactors 而不是 List<List<Integer>> primeFactors 因为我怀疑你不确实有一个主要因素列表，但实际上有一组主要因素。

Answer 5

由于您的列表相对较小，并且此操作经常执行，因此您应避免创建任何新的列表或集合，因为这可能会导致很大的 GC 压力。

扫描线性算法为

public static boolean emptyIntersection(List<Integer> sortedA, List<Integer> sortedB) {
    if (sortedA.isEmpty() || sortedB.isEmpty())
        return true;
    int sizeA = sortedA.size(), sizeB = sortedB.size();
    int indexA = 0, indexB = 0;
    int elementA = sortedA.get(indexA), elementB = sortedB.get(indexB);
    while (true) {
        if (elementA == elementB) {
            return false;
        } else if (elementA < elementB) {
            indexA++;
            if (indexA == sizeA)
                return true;
            elementA = sortedA.get(indexA);
        } else {
            // elementB < elementA
            indexB++;
            if (indexB == sizeB)
                return true;
            elementB = sortedB.get(indexB);
        }
    }
}

还可以考虑使用原始 int 列表而不是盒装整数，例如。 G。来自 fastutil 图书馆。

找出两个排序列表是否包含相同元素 Java 的有效方法。

Efficient way to find out if two sorted lists contain same element Java.

java

performance

new-operator