java - 改进交集算法

Question

我有一个算法来构建两个排序列表的交集。如果我在性能测试中将其与 java.util.BitSet 进行比较，我的算法很慢。

    public static List<Integer> intersection(List<Integer> list1, List<Integer> list2) {
            int size1 = list1.size(), size2 = list2.size();
            int capacity = size1 < size2 ? size1 : size2;
            List<Integer> intersection = new ArrayList<Integer>(capacity);
            int i1 = 0, i2 = 0;
            while (i1 < size1 && i2 < size2) {
                if (list1.get(i1) < list2.get(i2))
                    i1++;
                else if (list2.get(i2) < list1.get(i1))
                    i2++;
                else {
                    intersection.add(list2.get(i2++));
                    i1++;
                }
            }
            return intersection;
        }

有人看到任何改进吗？

谢谢

Answer 1

函数的输入是否始终为 ArrayList 类型？

• 如果是，从算法上来说，您的方法没有任何问题。我会做两个改变:
  1. 我将参数类型更改为 ArrayList<Integer> list1, ArrayList<Integer> list2 ;
  2. 我只会调用list1.get(i1)和list2.get(i2)一次。这可能会对性能产生任何影响，也可能不会产生任何影响，但从风格上来说，我更喜欢将其排除在外。
• 如果您需要支持任何列表，那么我会用两个迭代器重写该函数，因为调用 get(index)可能会非常昂贵。

最后，在测试性能时，请务必遵循How do I write a correct micro-benchmark in Java?中给出的建议。