Производительность традиционного цикла for против Iterator/foreach в Java
Имеются ли какие-либо результаты тестирования производительности при сравнении традиционных for loop и Iterator при обходе ArrayList,HashMap и других коллекций?
Или просто почему я должен использовать Iterator для цикла или наоборот?
9 ответов
Предполагая, что это то, что вы имели в виду:
// traditional for loop
for (int i = 0; i < collection.size(); i++) {
T obj = collection.get(i);
// snip
}
// using iterator
Iterator<T> iter = collection.iterator();
while (iter.hasNext()) {
T obj = iter.next();
// snip
}
// using iterator internally (confirm it yourself using javap -c)
for (T obj : collection) {
// snip
}
Итератор быстрее для коллекций без произвольного доступа (например, TreeSet, HashMap, LinkedList). Для массивов и списков массивов различия в производительности должны быть незначительными.
Редактировать: я считаю, что микро-бенчмаркинг является корнем зла, как и ранняя оптимизация. Но опять же, я думаю, что хорошо иметь представление о последствиях таких довольно тривиальных вещей. Поэтому я провел небольшой тест:
- перебирать LinkedList и ArrayList соответственно
- с 100 000 "случайных" строк
- суммируя их длину (просто чтобы избежать того, что компилятор оптимизирует весь цикл)
- используя все 3 стиля цикла (итератор, для каждого, со счетчиком)
Результаты одинаковы для всех, но "для счетчика" с LinkedList. Все остальные пять заняли менее 20 миллисекунд, чтобы перебрать весь список. С помощью list.get(i) на LinkedList 100 000 раз заняло более 2 минут (!) для завершения (60 000 раз медленнее). Вот Это Да!:) Следовательно, лучше использовать итератор (явно или неявно используемый для каждого), особенно если вы не знаете, с каким типом и размером списка вы имеете дело.
Первая причина использовать итератор - очевидная правильность. Если вы используете ручной указатель, могут быть очень безобидные ошибки "один за другим", которые вы можете увидеть, только если посмотрите очень внимательно: вы начали с 1 или с 0? Вы закончили в length - 1? Ты использовал < или же <=? Если вы используете итератор, гораздо легче увидеть, что он действительно выполняет итерацию всего массива. "Скажи, что ты делаешь, делай, что говоришь".
Вторая причина - равномерный доступ к различным структурам данных. Доступ к массиву можно получить с помощью индекса, но лучше всего просмотреть связанный список, запомнив последний доступ к элементу (в противном случае вы получите " Shlemiel the Painter"). Хэш-карта еще сложнее. Предоставляя единый интерфейс из этих и других структур данных (например, вы также можете выполнять обход дерева), вы снова получаете очевидную правильность. Логика обхода должна быть реализована только один раз, и код, использующий ее, может кратко "сказать, что он делает, и делать то, что он говорит".
Производительность похожа в большинстве случаев.
Однако всякий раз, когда код получает список и зацикливается на нем, существует хорошо известный случай:
Итератор намного лучше для всех реализаций List, которые не реализуют RandomAccess (пример: LinkedList).
Причина в том, что для этих списков доступ к элементу по индексу не является операцией с постоянным временем.
Таким образом, вы также можете рассматривать итератор как более надежный (к деталям реализации).
Как всегда, производительность не должна скрывать проблемы читабельности.
Цикл java5 foreach имеет большой успех в этом аспекте:-)
Да, это имеет значение для коллекций, которые не основаны на произвольном доступе, как LinkedList. Связанный список внутренне реализуется узлами, указывающими на следующий (начиная с головного узла).
Метод get(i) в связанном списке начинается с головного узла и перемещается по ссылкам вплоть до i-го узла. Когда вы выполняете итерацию по связанному списку, используя традиционный цикл for, вы каждый раз начинаете снова с головного узла, таким образом, общий переход становится квадратичным по времени.
for( int i = 0; i< list.size(); i++ ) {
list.get(i); //this starts everytime from the head node instead of previous node
}
В то время как цикл for для каждого перебирает итератор, полученный из связанного списка, и вызывает его метод next(). Итератор поддерживает состояния последнего доступа и, таким образом, не запускается каждый раз с головы.
for( Object item: list ) {
//item element is obtained from the iterator's next method.
}
Я не верю этому
for (T obj : collection) {
вычисляет.size() каждый раз через цикл и поэтому быстрее, чем
for (int i = 0; i < collection.size(); i++) {
Одна из причин, по которой я научился придерживаться каждого из них, заключается в том, что он упрощает вложенные циклы, особенно над 2+-мерными циклами. Все i, j и k, которыми вы можете манипулировать, могут очень быстро запутаться.
Используйте JAD или JD-GUI против вашего сгенерированного кода, и вы увидите, что нет никакой разницы. Преимущество новой формы итератора в том, что она выглядит чище в вашей кодовой базе.
Изменить: я вижу из других ответов, что вы на самом деле имели в виду разницу между использованием get (i) и итератор. Я взял первоначальный вопрос, чтобы обозначить разницу между старым и новым способами использования итератора.
Использование get (i) и ведение собственного счетчика, особенно для List занятия не очень хорошая идея по причинам, указанным в принятом ответе.
Одна из лучших причин использовать итератор над синтаксисом i++ состоит в том, что не все структуры данных будут поддерживать произвольный доступ, не говоря уже о том, чтобы он работал хорошо. Вы также должны программировать для интерфейса списка или коллекции, чтобы, если позднее вы решили, что другая структура данных будет более эффективной, вы сможете заменить ее без масштабной операции. В этом случае (в случае кодирования интерфейса) вы не обязательно будете знать детали реализации, и, вероятно, разумнее отнести это к самой структуре данных.
+1 к тому, что сказал sfussenegger. К вашему сведению, используете ли вы явный итератор или неявный (то есть для каждого), это не повлияет на производительность, поскольку они компилируются в один и тот же байт-код.