java - Java 中的高性能原始数组生成器

Question

我目前使用 google-or 工具来解决最大流量问题，因此这让我在 java 中创建了一些 int[] 数组以传递给 ortools。现在 ortools 非常快，这不是问题，但我愿意接受注重性能的替代方案。

问题主要在于构建数组，这花费了大部分时间以及返回结果时的 GC，我认为这可能是 JNI 开销，对此我无能为力。原始数组接近 5 - 7 百万个点标记，它们足够大，要求它们是整数，短的不是一个选择。我有什么选择或技巧吗？或者有人对如何最有效地构建这些有任何见解吗？内存在这里并不是真正的问题，我有足够的内存，并且在大多数情况下，我愿意接受任何绝对前沿性能的解决方案，即使它需要不同的数据表示形式，但这仍然必须能够插入 Ortools (除非您有一个想法来替换它)但我欢迎任何关于如何从中构建最快的阵列的建议。请注意，我事先不知道数组的长度，我不进行更新、删除，只进行追加。我很高兴提供更多细节。感谢您的任何建议。

Answer 1

评论太长。

如果与解决问题相比，构建问题表示需要花费大量时间，那么您就做错了。我猜你正在使用类似的东西

int[] appendTo(int[] array, int element) {
    int[] result = Arrays.copyOf(array, array.length + 1);
    result[result.length - 1] = element;
    return result;
}

其复杂度为二次方。该解决方案类似于 ArrayList 的做法:按某个固定因子增长并忽略尾随数组元素。这可能不是您最终需要的，但是一次收缩所有数组(就在将它们传递到库之前)是很便宜的。

你可以使用类似的类

class MyIntArray {
   private int length;
   private int[] data = new data[4];

   // This does the final shrinking.
   public int[] toArray() {
       return Arrays.copyOf(array, length);
   }

   public MyIntArray append(int element) {
       if (array.length == length) {
           array = Arrays.copyOf(array, 2 * length);
       }
       array[length++] = element;
   }
}

或者误用int[]的最后一个元素来跟踪逻辑长度(效率稍高，但非常hacky)。

有多种权衡，例如，您可以使用 length + (length >> 1) 而不是 2 * length 将增长因子降低到 1.5，从较短或较长的数组开始，甚至从一个空数组开始(就像 ArrayList 那样；然后您还需要调整增长因子)。