Нет итерация у ArrayList быстрее:



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

Действительно, LinkedList хорош, только если интенсивно изменять не конец списка. 
Очень познавательный тест оказался. Кроме того, ArrayList сделает toArray() на порядок быстрее;
Результаты на 5 млн. элементов в нс:


Это сообщение отредактировал(а) FlasH - 26.5.2008, 17:47

Точно ли только середину? По-моему, хорош когда добавляем данные не в конец списка. К примеру, очередь на ArrayList - сомнительное развлечение. (?)

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


Одинаковая ТОЛЬКО в том случае, если для обхода обоих типов списков использовать итератор. Если ArrayList "как массив через get(index)" обходить, то это будет значительно быстрее, чем LinkedList с итератором.

Прямо так уж и ересь? Дело-то на самом деле не в том, сколько инструкций занимает перейти от одного элемента к другому: одну, две или тысячу, а в том, что если в ArrayList адрес n-го элемента пересчитывается впрямую из индекса (на основании достаточно простой арифметики, то в LinkedList у тебя нет для этого  никакой другой возможности кроме как пройтись по этому списку от самой головы. И хорошо если у тебя этих элементов 10, а ведь может быть и миллион.

Это, собственно, и имел в виду unkis, просто выразился не совсем четко. Но разве до такой степени, чтобы нельзя было понять, о чем идет речь, и объявлять его слова ересью?

Дело не в этом. При обходе итератором нет никаких проходов от головы. В случае с массивом для получения следующего элемента мы выбираем memory[offset+(typesize*index)], а в случае со списком - memory[offset], memory[offset]. 


Да, ведь unkis пытался привязать разницу именно к результатам компиляции.

Это сообщение отредактировал(а) w1nd - 28.5.2008, 01:08

w1nd, а в чем же тут моя ересь?


вижу одно и тоже.   

О чем тут спорить? Доступ к произвольному элементу ArrayList - O(1), с точностью до множителя, до LinkedList - O(n), опять таки с точностью до множителя. Все погрешности и детали уходят в тот самый множитель, нас интересует только порядок роста.

Сорри что застрял с ответом. Дел было невпроворот, в общем, на собеседовании ответ был таков.

Приведу сразу картинку, чтобы было удобнее смотреть, вот возьмем к примеру схематичное изображение нового 4-х ядерного процессора от AMD 

(источник: http://www.hwupgrade.com/articles/print/cpu/10)

Как видно у каждого ядра есть по три кеша. Так вот в случае, когда мы идем по ArrayList мы кешируем индексы в каком-то из трех кэшей (сейчас даже не важно в каком именно) соответственно обход ArrayList'а будет выглядеть вот так (я думаю понятно что я утрирую и делаю описываю все очень схематично):

get(0) -> CPU -> Обновлям кэши из опертивки и возвращаем значение
get(1) -> CPU -> Достаем offset из кэша и возвращаем значение
get(n - 1) -> CPU -> Достаем offset из кэша и возвращаем значение 
get(n) -> CPU -> Обновлям кэши из опертивки и возвращаем значение
и т.д.

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

Под обновлением кеша я имею ввиду передачу какого-либо объема информации через шину, соединяющую кеши.

М-да.. 
Вывод: "Какой же из тебя Java-девелопер, если ты не знаешь новый 4-х ядерного процессор от AMD". Даже не смешно.

Не скажи, знать как работает железо и JVM - нужно, иначе как ты будешь оптимизировать код. Я вообще-то не люблю Спольски, но с данной его статьей полностью согласен.

Добавлено через 3 минуты и 57 секунд
Да и знать особенности работы нового 4-х ядерного процессор от AMD, совсем не нужно. Достаточно базовых знаний о том как устроен и работает процессор.

LSD, Ты знаешь первым делом, когда я услышал этот вопрос, я подумал про эту статью Спольски. Но, во-первых, согласись, статья клево написана и в ней разобран некий классический пример. 

Во-вторых,  когда я отвечал на вопрос (а правильный ответ я не дал), я подумал, поскольку я не "в теме", то даже узнав доводы я усомнюсь в их справедливости, ибо внутренняя архитектура и устройство современных процессоров это настолько сложная задача, что спрашивать, а уж тем более отвечать по этой тематике, даже будучи инженером, но без погружения в проблему просто преступно. Всякие там оптимизации, какие-то внутренние особенности и т.д. Честно говоря, мне показалось что интервьюер оперирует знаниями о 8086 покуда во всех инженерных вузах страны этот процессор преподы знают вдоль и поперек, а потому очень любят про него рассказывать на лекциях (собственно поэтому и многие студенты черпают свои знания о процессорах только с таких лекций), хотя эта интеловская бодяга 30 летний давности по сложности и архитектуре также похожа на современное устройство процессора как дачное ведро на японский унитаз. Именно поэтому меня крайне удивило, что меня спрашивают о том, о чем я могу быть и не в курсе. Разумеется под этим вопросом меня хотели "прощупать" на знание кэшей и того как они могут быть использованы... Хотя, опять же, по-моему, такую вещь как кеш я знаю как и когда мне использовать и умею ее реализовать, но понять что от меня хотят в этом случае (сравнивая ArrayList и LinkedList) я не смог.

По моему - всё это бред.
Правильный ответ на принципе аллокации памяти будет...

ИМХО кэш - это private в процессоре, и его реализация не должна влиять на программу - тем более java...
а если братть процессор с объединённым кешем для ядер?!.. Тот же интел? Да и сколько всяких "процов" существует?!..
А если ещё учитывать тонкости контроллера памяти. И паралельные программы и расположение звёзд и луны...

  Они б ещё к электронам привязывались..

Добавлено через 1 минуту и 47 секунд
По поводу статьи..

Напоминает спор политиков, когда не просто рассматриваются крайние случаи, а берутся за основу. Однобоко. Но интересно.

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