Высокопроизводительный примитивный массив-строитель в Java

Question

В настоящее время я использую google-инструменты или средства для решения проблемы максимального потока, поэтому мне удалось создать несколько массивов int [] в java для передачи в 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[] для отслеживания логического length (немного более эффективным, но очень Hacky).

Существуют различные компромиссы, например, вы можете уменьшить фактор роста до 1,5 с помощью length + (length >> 1) вместо 2 * length, начните с более короткими или более массивами, или даже с пустым массивом (как ArrayList делает, то вы бы необходимо также адаптировать фактор роста).