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

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

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

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

ArrayList медленнее, чем 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-байтовые значения.

Если вы обновите Integer,

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

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

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

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

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

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

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

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