Мы предпочитаем смежные области памяти. Причина становится очевидной, если мы посмотрим на аппаратном уровне.
CPU напрямую не взаимодействует с RAM , это происходит через CPU caches (часто делится на уровни, такие как L1, L2, L3 и т.д. с L1, являющимся самым маленьким и самым быстрым). Всякий раз, когда CPU хочет получить какие-либо данные, он отправляет запрос на L1, если не найден, L1 делегирует запрос на L2 и так далее (до жесткого диска), как показано на рисунке ниже:
Теперь, когда данные не найдены ни в одном кеше, мы называем это пропуском кеша. Чтобы уменьшить пропадание кеша, когда CPU хочет получить доступ к данным по адресу x в RAM , он будет получать не только данные по адресу x, но и окрестности адреса x (см. Рисунок ниже). Поскольку мы предполагаем, что «если на конкретную ячейку памяти ссылаются в определенное время, то вполне вероятно, что на ближайшую ячейку памяти будут ссылаться в ближайшем будущем (или локальная ссылка ).
Доступ к элементам массива обеспечивает последовательный доступ к данным и, таким образом, минимальное количество кеш-пропусков . Теперь вы можете визуализировать, почему массивы намного быстрее, чем структуры данных, такие как связанные списки, с точки зрения случайного / последовательного доступа к данным. То же самое относится и к другим структурам данных.