Производительность: итерация через список в Java

Ответ 1

Я предполагаю, что вы спрашиваете из чистого любопытства и не будет приводить Кнута (кто-то вероятно, будет).

Я считаю, что как только ваш код будет скомпилирован, это не изменит ситуацию. Он делает, делает разницу до (пример 2 намного читабельнее и кратким), поэтому идите на номер 2 и не заботитесь обо всем остальном.

Только мои 2 цента

ИЗМЕНИТЬ

Обратите внимание, что ваш код в фрагменте кода 1 вычисляет list.size() каждый раз, когда цикл работает, что может сделать его еще медленнее, чем номер 2

ДАЙТЕ ДРУГОЕ ИЗМЕНЕНИЕ

Что-то, что мне пришлось проверять дважды, Джошуа Блох рекомендует использовать циклы for each (см. пункт 46 Эффективная Java). Я считаю, что заканчивается всевозможные дискуссии. Спасибо, Джош!:)

Ответ 2

Не должно быть заметных различий в производительности для обычных списков.

Для связанных списков итератор будет значительно быстрее, особенно для больших списков.

Ответ 3

Создал microbenchmark для вопроса и был удивлен, увидев, что для каждого запуска 2x-3x быстрее, чем индексированный цикл. Единственное объяснение, которое у меня есть, это то, что для каждой версии могут не потребоваться проверки диапазона, которые создаются ArrayList.get(int index).

Для очень маленьких списков (10 элементов) результат был примерно таким же. Для 100 элементов для каждого - в 1,5 раза быстрее, для 10000-100000 элементов - быстрее 2x-3 раза.

Тесты выполняются на случайном наборе данных, и контрольные суммы проверяются в конце, поэтому JIT-chearing очень маловероятно в них.

Ответ 4

В соответствии с тестовыми тестами в While loop, для теста производительности цикла и Iterator - Java и вопроса JavaRanch " использует ArrayList.iterator() быстрее, чем цикл ArrayList in for loop?" Итератор на самом деле немного медленнее.

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

Ответ 5

Нет. Это быстрее (или должно быть быстрее), когда список также реализует: RandomAccess (как это делает ArrayList и LinkedList).

Однако вы всегда должны использовать последнее:

 for( Object o: list ) {
 }

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

Не делая этого, вы рискуете не иметь возможности переключать свою реализацию в более позднем рефакторинге, если это требует ваше приложение (потому что вы будете привязаны к идиоме for( int i = 0 ; i < list.size(); i++ )).

Ответ 6

МОЖНО БЫТЬ РАЗЛИЧНЫМ.

Если реализация List также реализует java.util.RandomAccess(как, например, ArrayList), то она быстрее использует свой метод get() над интерпретатором.

Если он не реализует java.util.RandomAccess(например, LinkedList не делает), то значительно быстрее использовать итератор.

Однако это имеет значение только в том случае, если вы используете списки, содержащие тысячи (возможно, рассеянных) объектов или которые постоянно пересекаются (как если бы они выполняли многочисленные математические данные по объектам List, представляющим числовые векторы.)

Ответ 7

Проверка размера каждой итерации добавляет операции i, но это не оказывает большого влияния на производительность.

Таким образом, я имею в виду, что существует незначительная разница между

int lsize = myList.size();
for(int i=0; i < lsize; i++)
{
   Object o = myList.get(i);
}

Versus:

for(int i=0; i < myList.size(); i++)
{
   Object o = myList.get(i);
}

Но это по существу не имеет значения. Используйте другой вариант из вашего вопроса для удобства чтения, среди других причин.

Ответ 8

Я не выглядел в коде get() всех реализаций List, поэтому, возможно, я напишу немного FUD. То, что я узнал, заключается в том, что использование цикла get(i) in for приведет к повторению итерации по всему списку каждый цикл. Использование Iterator (например, усиленный для цикла) просто переместит итератор в следующий элемент списка без повторения всего списка.

Мое заключение заключается в том, что использование итераторов или расширенного цикла должно быть более эффективным, поскольку использование get() приведет к сложности O(n^2) вместо O(n).

Ответ 9

Признано, что различие между случайным и последовательным  * доступ часто нечеткий. Например, некоторые реализации List  * обеспечивают асимптотически линейное время доступа, если они становятся огромными, но постоянными  * время доступа на практике. Такая реализация списка  * должен реализовывать этот интерфейс. Как правило,  * Реализация списка должна реализовывать этот интерфейс, если,  * для типичных экземпляров класса этот цикл:  *

 *     for (int i=0, n=list.size(); i < n; i++)
 *         list.get(i);
 * 

 *     for (Iterator i=list.iterator(); i.hasNext(); )
 *         i.next();
 *