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

Question

Медленнее ли перебирать список в Java следующим образом:

for (int i=0;i<list.size();i++) {
    .. list.get(i)
}

вместо:

for (Object o: list) {
    ... o
}

Answer 1

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

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

Простомои 2 цента

РЕДАКТИРОВАТЬ

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

ДАЙТЕ ДРУГОЕ РЕДАКТИРОВАНИЕ

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

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

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

Answer 5

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

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

 for( Object o: list ) {
 }

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

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

Answer 6

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

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

Answer 7

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

Под этим я подразумеваю небольшую разницу между

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

Против:

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

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

Answer 8

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

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

* работает быстрее, чем этот цикл: *

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

*

Answer 9

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

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