2

下面的数组经过排序，没有小尺寸（小于 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不是。有趣的是如何更改语句。<<lbif

4

2 回答 2

1

我不认为你可以做很多事情来提高 Java 代码的性能。但是，我会注意到它与 C 版本的功能不同。C 版本将交集放入由调用者预先分配的数组中。Java 版本自己分配数组……然后在完成后重新分配并复制到一个较小的数组。

我想，您可以更改 Java 版本以对输入数组进行两次传递，第一次计算输入数组需要多大......但它是否有帮助或阻碍将取决于输入。

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

但他们提到“可以使用无分支实现来改进这种方法”。一个人会怎么做？使用开关？

不是 Java 开关 ... 或条件表达式，因为它们在翻译为本机代码时都涉及分支。

我认为他指的是这样的东西： 将零、负和正映射到 0、1、2 的无分支代码

FWIW 尝试在 Java 中做这种事情是个坏主意。问题在于，像这样棘手的代码序列的性能取决于硬件架构、指令集、时钟计数等的细节，这些细节因平台而异。Java JIT 编译器的优化器可以很好地优化您的代码......但是如果您包含棘手的序列：

  1. 它们将如何被翻译成本机代码根本不明显或不可预测，并且
  2. 您很可能会发现，这种技巧实际上会抑制 JIT 编译器原本可以做的有用优化。

话虽如此，Java 的某些未来版本可能包括一个超级优化器……按照上面链接的问答中提到的那个……这将能够自动生成无分支序列，这并非不可能。但请记住，执行超级优化非常昂贵。

于 2013-05-09T11:53:29.257 回答
0

也许使用? :运算符：

  (a[i] < b[j]) ? i++ : ((a[i] > b[j]) ? j++ : ....
于 2013-05-09T11:46:56.217 回答