Почему итерация по списку может быть быстрее, чем его индексация?

Читая документацию Java для списка ADT, говорится:

Интерфейс List предоставляет четыре метода позиционного (индексированного) доступа к элементам списка. Списки (например, массивы Java) отсчитываются от нуля. Обратите внимание, что эти операции могут выполняться во времени, пропорциональном значению индекса для некоторых реализаций (например, класса LinkedList). Таким образом, итерация по элементам в списке обычно предпочтительнее индексирования по нему, если вызывающий не знает реализации.

Что именно это значит? Я не понимаю сделанного вывода.

В связанном списке каждый элемент имеет указатель на следующий элемент:

head -> item1 -> item2 -> item3 -> etc.

Чтобы получить доступ item3, вы можете ясно видеть, что вам нужно пройти от головы через каждый узел, пока не достигнете item3, поскольку вы не можете прыгать напрямую.

Таким образом, если я хочу напечатать значение каждого элемента, если я напишу это:

for(int i = 0; i < 4; i++) {
    System.out.println(list.get(i));
}

происходит вот что:

head -> print head
head -> item1 -> print item1
head -> item1 -> item2 -> print item2
head -> item1 -> item2 -> item3 print item3

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

Если бы я сделал это:

for(String s: list) {
    System.out.println(s);
}

тогда происходит следующее:

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc.

все за один обход, то есть O(N).

Теперь, переходя к другой реализации из Listкоторых ArrayList, что одна опирается на простой массив. В этом случае оба вышеуказанных обхода эквивалентны, поскольку массив является непрерывным, поэтому он допускает случайные переходы к произвольным позициям.

Здесь подразумевается ответ:

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

Связанный список не имеет собственного индекса; для вызова .get(x)потребуется реализация списка, чтобы найти первую запись и вызвать .next()x-1 раз (для O (n) или линейного доступа по времени), где список с поддержкой массива может просто индексировать вbackingarray[x] в O (1) или с постоянным временем.

Если вы посмотрите на JavaDoc дляLinkedList , вы увидите комментарий

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

тогда как JavaDoc forArrayList имеет соответствующий

Реализация интерфейса List с изменяемым размером массива. Реализует все необязательные операции со списком и разрешает все элементы, включая null. Помимо реализации интерфейса List, этот класс предоставляет методы для управления размером массива, который используется внутри для хранения списка. (Этот класс примерно эквивалентен Vector, за исключением того, что он не синхронизирован.)

size, isEmpty, get, set, iterator, И listIteratorоперации выполняются в постоянная время. Операция добавления выполняется за амортизированное постоянное время, то есть добавление n элементов требует времени O (n). Все остальные операции выполняются в линейное время (грубо говоря). Постоянный коэффициент низкий по сравнению с коэффициентом LinkedListреализации.

Связанный с этим вопрос под названием «Резюме Big-O для Java Collections Framework» есть ответ, указывающий на этот ресурс, «Java Collections JDK6», который может оказаться полезным.

Хотя принятый ответ, безусловно, правильный, могу ли я указать на незначительный недостаток. Цитата Тюдора:

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

Это не совсем так. Правда в том, что

С ArrayList рукописный счетный цикл примерно в 3 раза быстрее

Источник: Designing for Performance, Google's Android doc.

Обратите внимание, что рукописный цикл относится к индексированной итерации. Я подозреваю, что это из-за итератора, который используется с расширенными циклами for. Это дает незначительную производительность в виде штрафа в структуре, поддерживаемой непрерывным массивом. Я также подозреваю, что это может быть верно для класса Vector.

Мое правило: по возможности используйте расширенный цикл for, а если вы действительно заботитесь о производительности, используйте индексированную итерацию только для ArrayLists или Vectors. В большинстве случаев вы можете даже проигнорировать это - компилятор может оптимизировать это в фоновом режиме.

Я просто хочу указать, что в контексте разработки под Android оба обхода ArrayLists не обязательно эквивалентны . Просто пища для размышлений.

Итерация по списку со смещением для поиска, например i, аналогична алгоритму художника Шлемиэля .

Шлемиэль устраивается уличным художником, рисуя пунктирные линии посередине дороги. В первый день он выносит на дорогу баллончик с краской и заканчивает 300 ярдов дороги. "Это очень хорошо!" говорит его босс, "ты быстрый работник!" и платит ему копейку.

На следующий день Шлемиэль успевает пройти всего 150 ярдов. «Ну, это не так хорошо, как вчера, но вы все равно быстро работает. 150 ярдов - это прилично», - и платит ему копейку.

На следующий день Шлемиэль красит 30 ярдов дороги. "Всего 30!" кричит его босс. «Это недопустимо! В первый день ты сделал в десять раз больше работы! Что происходит?»

«Я ничего не могу с собой поделать», - говорит Шлемиэль. "С каждым днем ​​я все дальше и дальше отдаляюсь от банки с краской!"

Источник .

Эта небольшая история может помочь понять, что происходит внутри и почему это так неэффективно.

Чтобы найти i-й элемент LinkedList реализация перебирает все элементы вплоть до i-го.

Так

for(int i = 0; i < list.length ; i++ ) {
    Object something = list.get(i); //Slow for LinkedList
}