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

I have a tight loop that searches coprimes. A list primeFactors. Its n-th element contains a sorted list of prime decomposition of n. I am checking if c and d are coprimes using checkIfPrimes

我有一个紧密的循环来搜索coprimes。列表primeFactors。它的第n个元素包含n的素数分解的排序列表。我正在检查c和d是否是使用checkIfPrimes的互质

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)) looks promising, but it will alter my reusable primeFactors object.

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

Creating a new object is relatively slow. Is there a way to speed up this step? Can I somehow utilize the fact that lists are sorted? Should I use arrays instead?

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

5 个解决方案

#1

Set operations should be faster than array operations. Just for kicks, consider trying this and compare the performance against the stream performance:

设置操作应该比数组操作更快。只是为了解决问题,请考虑尝试并将性能与流性能进行比较:

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());

Also, consider using List<Set<Integer>> primeFactors instead of List<List<Integer>> primeFactors since I suspect that you don't really have a list of prime factors but actually have a set of prime factors.

另外,考虑使用List > primeFactors而不是List > primeFactors,因为我怀疑你没有真正的素数列表,但实际上有一组素因子。

#2

You could use a Collection with faster lookup - e.g. a Set if you only need the prime factors without repetitions, or a Map if you also need the count of each factor.

您可以使用快速查找的集合 - 例如a如果您只需要素数因子而不需要重复,或者如果您还需要每个因子的计数,则使用Map。

Basically, you want to know whether the intersection of two Sets is empty. Oracle Set tutorial shows a way to calculate the intersecton (similar to what you already mentioned, using retainAll on a copy, but on Sets the operation should be more efficient).

基本上,您想知道两个集合的交集是否为空。 Oracle Set教程显示了一种计算相交的方法(类似于您已经提到的,在副本上使用retainAll,但是在设置上操作应该更有效)。

#3

Since your lists are relatively small, and this operation is executed very often, you should avoid creating any new Lists or Sets, because it might lead to a significant GC pressure.

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

The scan linear algorithm is

扫描线性算法是

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);
        }
    }
}

Also consider using lists of primitive ints instead of boxed integers, e. g. from fastutil library.

还要考虑使用原始整数列表而不是盒装整数,例如: G。来自fastutil库。

#4

Normally you can use a boolean array. Where the index of the array is the number and the value of the boolean returns true when it is a prim otherwise false.

通常你可以使用布尔数组。其中数组的索引是数字,布尔值的值在为prim时返回true,否则为false。

#5

You could do something along the lines of:

你可以做一些事情:

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

Once you measure this performance, you can substitute 'parallelStream()' for 'stream()' above and see what benefits you derive.

一旦你测量了这个性能,就可以用'parallelStream()'代替上面的'stream()',看看你得到了什么好处。

#1