В поисках дальнейшего понимания итераторов в Java

Question

Если я использую цикл for (стандартный цикл for, а не расширенный оператор for), я не вижу, как итератор повышает эффективность при поиске в коллекции. Если у меня есть заявление, такое как:

(Предполагая, что aList является списком универсальных объектов, тип E, nextElement ссылается на следующий элемент в списке)

for (int index = 0; index < aList.size(); index++){
E nextElement = aList.get(index);
// do something with nextElement...
}

и у меня есть метод get, который выглядит примерно так:

Node<E> nodeRef = head;
for (int i = 0; i < index; i++){
    nodeRef = nodeRef.next;
    // possible other code
}

это, по сути, поиск по списку, по одному элементу за раз. Однако, если я использую итератор, не будет ли он выполнять ту же операцию? Я знаю, что итератор должен иметь скорость O (1), но разве не будет O (n), если ему все равно придется искать по всему списку?

Answer 1

Речь идет не только об эффективности, ИМО. Это примерно абстракция . Использование индекса связывает вас с коллекциями, которые могут эффективно извлекать элемент для данного индекса (скажем, он не будет хорошо работать со связанным списком) ... и он не выражает то, что вы ' пытаемся сделать, что итерация по списку.

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

Ваш второй случай все еще записывается с использованием цикла for, который увеличивает index , что не является идиоматическим способом думать об этом - это просто проверка того, достиг ли он конца , Например, это может быть:

for (Node<E> nodeRef = head; nodeRef != null; nodeRef = nodeRef.next)
{
}

Теперь у нас есть правильная абстракция: цикл выражает то, с чего мы начинаем (голова), когда мы останавливаемся (когда больше нет элементов) и как мы переходим от одного элемента к другому (используя поле next) , Это выражает идею более эффективной итерации, чем «У меня есть счетчик, начинающийся с 0, и я собираюсь запрашивать значение у конкретного счетчика на каждой итерации, пока значение счетчика не станет больше некоторого значения, которое происходит». быть длиной списка. "

Мы довольно использовали для последнего способа выражения вещей, но в действительности это не говорит о том, что мы имеем в виду, почти так же, как и итераторский подход.

Answer 2

Итераторы - не для повышения эффективности, а для абстракции в объектно-ориентированном смысле. С точки зрения реализации, итератор делает нечто похожее на то, что вы делаете, просматривая вашу коллекцию по одному элементу за раз, по крайней мере, если коллекция основана на индексах. Предполагается, что при извлечении элемента next он будет иметь значение O (1), а не весь список. Итераторы помогают маскировать то, что находится под коллекцией, это может быть связанный список или набор и т. Д., Но вам не нужно знать.

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

Answer 3

Помните, что это также шаблон проектирования.

"Шаблон итератора позволяет обходить элементы агрегата без раскрытия базовой реализации. Он также ставит задачу обхода на объекте итератора, а не на агрегате, что упрощает интерфейс и реализацию агрегата и возлагает ответственность где это должно быть. " (От: Head First Design Pattern)

Речь идет об инкапсуляции, а также о принципе «единой ответственности».

Ура, Wim

Answer 4

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

while(itr.hasNext()) {
    if(itr.next().equals(somethingBad);
         itr.remove();
}

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

Answer 5

Я думаю, что вопрос, который вы задаете, относится к эффективности итераторов по сравнению с циклом for, использующим явный get для объекта коллекции.

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

• один шаг, чтобы "получить" первый элемент
• два шага, чтобы «достать» второго
• три шага, чтобы получить третий
• ...
• n шагов, чтобы получить последний

всего n(n-1)/2 операций, что составляет O (n ^ 2).

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

Answer 6

Вы используете связанный список здесь. Итерация по этому списку без итератора требует O (n ^ 2) шагов, где n - размер списка. O (n) для итерации по списку и O (n) каждый раз для поиска следующего элемента.

Итератор, с другой стороны, запоминает узел, который он посещал в последний раз, и поэтому ему требуется только O (1) для поиска следующего элемента. Таким образом, в конечном итоге сложность O (n), что быстрее.