如何在Java中加速数组交集？

Question

以下数组是没有重复元素的（仅包含唯一正整数），规模较小（小于5000），交集（见下文）被调用了很多次，因此任何微观优化都很重要。这篇文章很好地描述了如何加速下面的C代码。

int i = 0, j = 0, c = 0, la = a.length, lb = b.length;
intersection = new int[Math.min(la, lb)];
while (i < la && j < lb) {
    if (a[i] < b[j]) i++;
    else if (a[i] > b[j]) j++;
    else {
        intersection[c] = a[i];
        i++; j++; c++;
    }
}
int[] intersectionZip = new int[c];
System.arraycopy(intersection, 0, intersectionZip, 0, c);

在Java中，我想调用那些低级指令是不可能的。但他们提到“可以使用无分支实现来改进此方法”。如何做到这一点？使用switch吗？或者用整数操作符替换a[i] < b[j]、a[i] > b[j]或a[i] == b[i]比较？

二分查找法（复杂度为O(la log(lb))）不适用于此情况，因为la并不是<<于lb。有趣的是如何改变if语句。

- Sophie Sperner

Answer 1

我认为你无法做太多来提高那个 Java 代码的性能。然而，我需要指出的是它并不像 C 版本那样做相同的事情。C 版本将交集放入了由调用者预先分配的数组中。Java 版本会自己分配数组...然后在完成时重新分配和复制到较小的数组中。

我猜你可以改变 Java 版本，使其在输入数组上进行两次遍历，第一次遍历计算出输入数组需要多大...但是否有帮助还要取决于输入。

可能还有其他特殊情况可以进行优化；例如，如果一个数组中有很长的连续数字范围，而另一个数组中没有这个范围中的任何内容，你可能可以“乐观地”尝试跳过多个数字；即通过比1更大的数字增加i或j。

---

但是他们提到“可以使用无分支实现来改进这种方法”。如何做到这一点？使用switch语句吗？

不是Java的switch语句...或条件表达式，因为它们都涉及到在转换为本地代码时分支。

我认为他指的是像这样的东西：将零、负数和正数映射到0、1、2的无分支代码 顺便说一下，在Java中尝试做这种事情是一个坏主意。问题在于，这种棘手的代码序列的性能取决于硬件架构、指令集、时钟计数等细节，这些细节因平台而异。Java JIT编译器的优化器可以很好地优化您的代码......但如果您包含棘手的序列：

1. 不明显或不可预测它们将如何被翻译成本地代码，并且 2. 您可能会发现，这种棘手性实际上会抑制JIT编译器可能本来可以执行的有用优化。

话虽如此，未来的Java版本可能会包含一个超级优化器......类似于上面链接的Q&A中提到的那个......能够自动生成无分支序列。但请记住，超级优化非常昂贵。

- Stephen C

Answer 2

或许可以使用? :运算符：

  (a[i] < b[j]) ? i++ : ((a[i] > b[j]) ? j++ : ....

- hamid

---

三元运算符与if-else语句非常相似。 - Steve Benett