Вот я снова начал ходить по собеседованиям и ... узнавать новые вещи из сферы высоких технологий. В общем хочу поделиться. Был такой вопрос, - Почему ещё ArrayList, работает быстрее, чем LinkedList? Поясню вопрос, всем известно, что пройти по списку медленнее, чем прочесть элемент по индексу, попытайтесь объяснить где еще кроются тормоза. Поскольку ответ мне показался спорным, я сразу даю направление в котором следует его искать. Нужно разобрать самый низкий уровень, а именно принципы работы CPU.

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

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

Хотелось бы услышать ответ поподробнее

Интересно. может быть что-то из курса ассемблера? типа доступ к элементу массива e[off] а к следующему элементу памяти в LL e[e[off]]

а поподробнее можно здесь почитать

Ну во первых неплохо бы указывать, что там было до "еще", чтобы не перебирать все варианты  

А по сабжу, если речь идет об простой итерации, то:
- меньше обращений к памяти
- обращения к памяти идут в одной области памяти (значит эффективно работает кеш процессора)

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

Я не уверен но можеть быть так:
LinkedList содержит в памяти ссылки на элементы и возможно для ЦП нужно две операции: прочитать адрес и перейти по адресу, а в ArrayList каждый элемент идёт друг за другом и поэтому достаточно одной операции просто перейти на следующий элемент.
вообщем как-то так, не знаю понял ли меня кто-то и правильно ли я размышляю, очень хотеться услышать правильный ответ.

Я думаю, что вопрос задавался по принципу:

ArrayList основан на массиве и поэтому обращение к элементу [i] будет в один шаг. LinkedList основан на связанном списке, т.е. есть указатель на первый элемент, а остальные прилинкованы. И доступ к элементу [i] будет конечно же медленнее.

С другой стороны - добавление в LinkedList не зависит от количества элементов - хоть 200, зоть 100 тыс. Время добавления не меняется.
А вот в ArrayList (если массив уже почти заполнен) - там будет создаваться новый массив большего размера. А значит в какой-то ситуации добавление может выйти боком.

Дальше думайте, где лучше использовать одну коллекцию, а где - другую. На самом деле достаточно здравый вопрос.

unkis, лично я тебя очень хорошо понял:



Добавлено через 2 минуты и 44 секунды
AntonSaburov, учитывая, что Royan сделал оговорку на ЦПУ, то думаю, тут скорость не в том, чтобы определить массовость операций извлечения / добавления.

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

С позиции CPU ArrayList скорей всего реализован как стек - ESP+индекс - вот тебе и значение(это ИМХО - то есть догадка - ни чего более - не вскрывал), LinkedList же можно нагородить с три короба и соответственно операций там не одна......а если учесть что ОС может сегмент данных выгрузить(!) -  то время поиска может существенно увеличится.


Это сообщение отредактировал(а) Krivoy - 20.5.2008, 12:39

Если речь о скорости обхода - она одинаковая. LinkedList при этом нужно обходить с помощью итератора, а ArrayList как массив через get(index).  Я не знаю, как написать корректный тест (списки в 1млн элементов обходятся за 16мс, а минимальный инкремент моего таймера - 15мс), видимо где-то что-то оптимизируется.

По скорости добавления элементов в список - ArrayList медленнее известно почему.

А по поводу инструкций процессора - они ж разные бывают, большая нагрузка часто на SPARCах и POWERах обрабатывается, а ещё бывают S390 и java-процессоры.

Интересно, чем же объяснили разницу в скорости интервьюверы?

Это сообщение отредактировал(а) FlasH - 20.5.2008, 13:34

Вот из-за таких вопросов я и не люблю интервью   Что-то рассказать, конечно, можно, но это не обязательно понравится интервьюверам.

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