0

我有一个算法来构建两个排序列表的交集。如果我在性能测试中将它与 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;
        }

有人看到有什么改善吗？

谢谢

4

2 回答 2

1

您的函数的输入是否总是类型ArrayList？

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

最后，在测试性能时，请务必遵循如何在 Java 中编写正确的微基准测试中给出的建议？

于 2013-03-26T09:57:08.410 回答
0

你应该知道这一点：

List<Integer> intersection = new ArrayList<Integer>(capacity);

分配一个内部数组 size capacity。

假设list1.size() == 5000、list2.size() == 5000、 和intersection(list1, list2).size() == 3，该方法将分配 4997 个无用整数。

尝试使用合理的容量（取决于方法的使用）或将其保留为默认值（即 10）。

（请记住，分配大小数组n（或容量ArrayList数组）的复杂性是。） nO(n)

于 2013-03-26T10:20:33.150 回答