0

我目前使用 google-or 工具来解决最大流量问题，所以这让我在 java 中创建了一些 int[] 数组以传递给 ortools。现在 ortools 非常快，在这里不是问题，但我对这里的性能替代品持开放态度。

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

4

1 回答 1

4

评论太长了。

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

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;
   }
}

或滥用 an 的最后一个元素int[]来跟踪逻辑length（效率稍高，但非常hacky）。

有各种权衡，例如，您可以通过使用length + (length >> 1)而不是，将增长因子降低到 1.5 2 * length，从较短或较长的数组开始，甚至从空数组开始（就像这样ArrayList做；那么您需要将增长因子调整为出色地）。

于 2017-01-19T07:43:06.133 回答