Производительность Java - списки массивов и массивы для быстрого чтения

Теперь, когда вы упомянули, что ваши массивы на самом деле являются массивами примитивных типов, рассмотрите возможность использования классов collection-of-primitive-type в Библиотека Trove.

@viking сообщает о значительном (десятикратном!) ускорении использования Trove в своем приложении - см. комментарии. Обратной стороной является то, что типы коллекций Trove несовместимы по типам со стандартными API сбора данных Java. Так что Trove (или аналогичные библиотеки) не во всех случаях подойдет.

Попробуйте оба, но измерьте.

Скорее всего, вы могли бы что-то вместе взломать, чтобы внутренний цикл использовал массивы, не меняя так много кода. Я подозреваю, что HotSpot уже встроит вызовы методов, и вы не увидите прироста производительности.

Также попробуйте Java 6 update 14 и используйте -XX: + DoEscapeAnalysis

ArrayLists медленнее, чем Arrays, но большинство людей считает разницу незначительной. В вашем случае это может иметь значение, поскольку вы имеете дело с сотнями тысяч из них.

Кстати, продублируйте: массив или список в Java. Что быстрее?

Я бы согласился с советом Кевина.

Оставайтесь в первую очередь со списками и измеряйте свою производительность, если ваша программа медленно сравнивает ее с версией с массивом. Если это дает ощутимый прирост производительности, переходите к массивам, а если не к спискам, потому что они сделают вашу жизнь намного проще.

Использование ArrayList вместо массива приведет к накладным расходам, но, скорее всего, они будут небольшими. Фактически, полезный бит данных в ArrayList может храниться в регистрах, хотя вы, вероятно, будете использовать больше (например, размер List).

Вы упоминаете в своем редактировании, что используете объекты-оболочки. Это имеет огромное значение. Если вы обычно используете одно и то же значение неоднократно, тогда может быть полезна разумная политика кеширования (Integer.valueOf дает те же результаты для значений от -128 до 128). Для примитивов примитивные массивы обычно выигрывают.

В качестве уточнения вы можете убедиться, что соседние ячейки имеют тенденцию быть смежными в массиве (вы можете сделать лучше, чем строки столбцов с кривая заполнения пространства).

Одна из возможностей - повторно реализовать ArrayList (это не так сложно), но выставить резервный массив через цикл вызовов блокировки / освобождения. Это дает вам удобство при записи, но предоставляет массив для большой серии операций чтения / записи, которые, как вы заранее знаете, не повлияют на размер массива. Если список заблокирован, добавлять / удалять нельзя - просто получить / установить.

Например:

  SomeObj[] directArray = myArrayList.lockArray();
  try{
    // myArrayList.add(), delete() would throw an illegal state exception
    for (int i = 0; i < 50000; i++){
      directArray[i] += 1;
    }
  } finally {
    myArrayList.unlockArray();
  }

Этот подход продолжает инкапсулировать рост массива / и т. Д. Поведение ArrayList.

Java использует двойную косвенную адресацию для своих объектов, чтобы их можно было перемещать в памяти, а ссылки оставались действительными. Это означает, что каждый поиск по ссылке эквивалентен поиску по двум указателям. Эти дополнительные поиски нельзя полностью оптимизировать.

Возможно, даже хуже, производительность вашего кеша будет ужасной. Доступ к значениям в кеше будет во много раз быстрее, чем доступ к значениям в основной памяти. (возможно, 10x). Если у вас есть int [], вы знаете, что значения будут последовательными в памяти и, таким образом, легко загрузятся в кеш. Однако для Integer [] отдельные объекты Integer могут случайным образом появляться в вашей памяти и с большей вероятностью будут промахами в кэше. Также Integer использует 24 байта, что означает, что они с меньшей вероятностью поместятся в ваши кеши, чем 4-байтовые значения.

Если вы обновляете целое число, это часто приводит к созданию нового объекта, размер которого на много порядков превышает обновление значения типа int.

Если вы создаете список один раз и выполняете тысячи операций чтения из него, накладные расходы от ArrayList могут быть достаточно незначительными, чтобы их можно было игнорировать. Если вы создаете тысячи списков, используйте стандартный массив. Создание объекта в цикле быстро становится квадратичным просто из-за всех накладных расходов на создание экземпляров переменных-членов, вызов конструкторов в цепочке наследования и т. Д.

Из-за этого - и чтобы ответить на ваш второй вопрос - придерживайтесь стандартных целых чисел, а не класса Integer. Профилируйте оба, и вы быстро (или, скорее, медленно) поймете, почему.

Если вы не собираетесь делать что-то большее, чем чтение из этой структуры, тогда используйте массив, так как это будет быстрее при чтении по индексу.

Однако подумайте, как вы собираетесь получить данные, и если сортировка, вставка, удаление и т. Д. Вообще беспокоит. Если это так, вы можете рассмотреть другие структуры на основе коллекций.

Примитивы намного (намного) быстрее. Всегда. Даже с JIT-анализом escape и т. Д. Не нужно переносить вещи в java.lang.Integer. Кроме того, пропустите проверку границ массива, которую большинство реализаций ArrayList выполняют с get (int). Большинство JIT могут распознавать простые шаблоны циклов и удалять цикл, но для этого нет особых причин, если вы беспокоитесь о производительности.

Вам не нужно самостоятельно кодировать примитивный доступ - готов поспорить, вы можете перейти к использованию IntArrayList из библиотеки COLT - см. http://acs.lbl.gov/~hoschek/colt/ - «Colt предоставляет набор библиотек с открытым исходным кодом для высокопроизводительных научных и технических вычислений на Java») - в нескольких минут рефакторинга.

Возможны следующие варианты:
1. Использовать массив
2. Использовать ArrayList, который внутренне использует массив

Очевидно, что ArrayList вводит некоторые накладные расходы (посмотрите исходный код ArrayList). В 99% случаев эти накладные расходы можно легко проигнорировать. Однако если вы реализуете чувствительные ко времени алгоритмы и выполняете десятки миллионов операций чтения из списка по индексу, тогда использование голых массивов вместо списков должно привести к заметной экономии времени. ИСПОЛЬЗУЙ ЗДРАВЫЙ СМЫСЛ.

Взгляните сюда: http://robaustin.wikidot.com/how-does-the-performance-of-arraylist-compare-to-array Я бы лично настроил тест, чтобы избежать оптимизации компилятора, например Я бы заменил «j =» на «j + =» с последующим использованием «j» после цикла.

Массив будет быстрее просто потому, что он как минимум пропускает вызов функции (т.е. get (i)).

Если у вас статический размер, то массивы - ваш друг.