У меня есть программа, в которой мне нужно сделать от 100 000 до 1 000 000 чтения с произвольным доступом к объекту, подобному List, за минимальное время (как в миллисекундах) для сотовой автоматы. Я думаю, что алгоритм обновления, который я использую, уже оптимизирован (эффективно отслеживает активные ячейки и т.д.). Списки должны изменить размер, но эта производительность не так важна. Поэтому я задаюсь вопросом, достаточно ли производительности от использования массивов вместо ArrayLists, чтобы иметь значение, когда речь идет о многих чтениях в такие короткие промежутки времени. В настоящее время я использую ArrayLists.
Изменить: Я забыл упомянуть: я просто храню целые числа, поэтому другой фактор использует класс оболочки Integer (в случае ArrayLists) по сравнению с ints (в случае массивов). Кто-нибудь знает, может ли использование ArrayList на самом деле потребовать 3 указателя look ups (один для ArrayList, один для базового массива и один для Integer- > int), где, поскольку для массива потребуется только 1 (адрес массива + смещение к конкретному INT)? Будет ли HotSpot оптимизировать дополнительный поиск? Насколько значительны эти дополнительные взгляды?
Edit2: Кроме того, я забыл упомянуть, что мне также нужно делать записи с произвольным доступом (пишет, а не вставки).
Теперь, когда вы упоминали, что ваши массивы на самом деле являются массивами примитивных типов, рассмотрите классы классов примитивного типа в Trove библиотека.
@viking сообщает о значительном (десятикратном!) ускорении, используя Trove в своем приложении - см. комментарии. Откидной стороной является то, что типы коллекции Trove не совместимы со стандартными API-интерфейсами Java. Таким образом, Trove (или подобные библиотеки) не будет ответом во всех случаях.
Попробуйте обе, но измерьте.
Скорее всего, вы могли бы взломать что-то вместе, чтобы использовать внутренние циклы для использования без изменения всего этого кода. Мое подозрение в том, что HotSpot уже включит вызовы методов, и вы не увидите прироста производительности.
Кроме того, попробуйте обновление для Java 6 14 и используйте -XX: + DoEscapeAnalysis
ArrayLists медленнее, чем массивы, но большинство людей считают, что разница незначительна. В вашем случае это может иметь значение, поскольку вы имеете дело с сотнями тысяч из них.
Кстати, дублируем: Array или List на Java. Что быстрее?
Я бы пошел с Кевином.
Оставайтесь со списками в первую очередь и измерьте свою производительность, если ваша программа должна замедлить сравнение с версией с массивом. Если это даст вам измеримое повышение производительности, пойдите с массивами, если не останетесь со списками, потому что они значительно облегчат вашу жизнь.
При использовании ArrayList вместо массива будут накладные расходы, но он, скорее всего, будет небольшим. Фактически, полезный бит данных в ArrayList может храниться в регистрах, хотя вы, вероятно, будете использовать больше (List size, например).
Вы указываете в своем редактировании, что используете объекты-обертки. Это действительно имеет огромное значение. Если вы обычно используете одно и то же значение несколько раз, разумная политика кэша может быть полезна (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();
}
Этот подход продолжает инкапсулировать рост массива /etc... поведение ArrayList.
Java использует двойную косвенность для своих объектов, поэтому их можно перемещать в памяти и иметь ссылки на нее по-прежнему, это означает, что каждый поиск ссылок эквивалентен двум поисковым запросам. Эти дополнительные поиски не могут быть полностью оптимизированы.
Возможно, еще хуже будет ваша производительность кеша будет ужасной. Доступ к значениям в кеше происходит во много раз быстрее, чем доступ к значениям в основной памяти. (возможно, 10x) Если у вас есть int [], вы знаете, что значения будут последовательно в памяти и, следовательно, легко загружаются в кеш. Тем не менее, для Integer [] отдельные объекты Integer могут отображаться случайным образом в вашей памяти и, скорее всего, будут пропускать кеш. Кроме того, Integer использует 24 байта, что означает, что они гораздо реже вписываются в ваши кеши, чем 4 байтовых значения.
Если вы обновляете Integer, это часто приводит к созданию нового объекта, который на много порядков, чем обновление значения int.
Если вы создаете список один раз и делаете тысячи его чтений, накладные расходы из ArrayList могут быть достаточно слабыми, чтобы их игнорировать. Если вы создаете тысячи списков, перейдите со стандартным массивом. Создание объекта в цикле быстро идет квадратично, просто из-за всех накладных расходов на создание экземпляров переменных-членов, вызов конструкторов в цепочку наследования и т.д.
Из-за этого - и для ответа на второй вопрос - придерживайтесь стандартного ints, а не класса Integer. Профили, и вы быстро (или, скорее, медленно) увидите, почему.
Если вы не будете делать намного больше, чем читаете из этой структуры, то продолжайте и используйте массив, поскольку это будет быстрее, если читать по индексу.
Однако подумайте над тем, как вы собираетесь получать данные там, и если сортировка, вставка, удаление и т.д. являются проблемой. Если это так, вы можете рассмотреть другие структуры, основанные на коллекции.
Примитивы намного (намного) быстрее. Всегда. Даже с JIT-анализом и т.д. Пропустите обматывание вещей в 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)).
Если у вас есть статический размер, то массивы - ваш друг.