Хорошо. Уже ответили, но я все же постараюсь изложить свою точку зрения.ArrayList быстрее в итерации, чем LinkedList.Причина та же, потому что arrayList поддерживается массивом.Давайте попробуем понять, почему итерация массива происходит быстрее, чем linkedList.
Для этого есть 2 фактора
- Массив хранится как
contiguous memory locations (Вы можете сказать тогда
что?) - Системный кеш гораздо быстрее, чем доступ к памяти
Но вы можете спросить, как Cache подходит здесь.Хорошо, проверьте здесь , CPU пытается использовать рычаги кэшей, сохраняя данные в кэше.Используется Локальная привязка . Теперь есть 2 метода:
Ссылка Локальная привязка
Временная локальность Если в какой-то момент ссылка на конкретную ячейку памяти указана, то, скорее всего, в ближайшем будущем эта ссылка будет снова указана.Существует временная близость между соседними ссылками на одну и ту же ячейку памяти.В этом случае принято прилагать усилия для сохранения копии указанных данных в специальном хранилище памяти, к которому можно получить доступ быстрее.Временная локализация - это особый случай пространственной локализации, а именно, когда предполагаемое местоположение идентично текущему местоположению.
Пространственное местоположение Если на конкретное место хранения ссылаются в определенное время, то оноВероятно, в ближайшем будущем будут указаны ссылки на близлежащие области памяти.В этом случае принято пытаться угадать размер и форму области вокруг текущей ссылки, для которой стоит подготовить более быстрый доступ.
Так что, если к одному местоположению массива обращаются одновременноон также загрузит смежные области памяти в кеш.Но ждать это не загрузит все.Это зависит от CACHE_LINES .Хорошо CACHE_LINES определяет, сколько бит может быть загружено в кэш за один раз.
Поэтому перед погружением давайте напомним, что мы знаем
- Массив равен
contiguous memory locations - Когда к одной ячейке памяти массива обращаются рядом, также загружается в память
- Сколько мест памяти массива загружается в память, определяется
CACHE-LINES емкость
SO, когда процессор пытаетсячтобы получить доступ к ячейке памяти, проверьте, находится ли эта память в кеше.Если он присутствует, он совпадает с другим cache miss.
Так что из того, что мы знаем в случае массива, будет меньше cache_miss по сравнению с random memory locations как в linked list.Таким образом, имеет смысл
и, наконец, отсюда Array_data_structure из Википедии он говорит
В массиве с размером элемента k и на машине с размером строки кэшаиз B байтов, итерация по массиву из n элементов требует минимального количества нехватки кеша (nk / B), потому что его элементы занимают смежные области памяти.Это примерно в B / k раз лучше, чем количество пропущенных кешей, необходимых для доступа к n элементам в случайных местах памяти.Как следствие, последовательная итерация по массиву на практике заметно быстрее, чем итерация по многим другим структурам данных, свойство, называемое locality of refrence
Я полагаю, это отвечает на ваш вопрос.