Какой из них быстрее и почему? 1. Массив 2. Список ссылок. Если мы просто хотим перебрать цикл for и напечатать его
Какой из них быстрее и почему? 1. Массив 2. Список ссылок. Если мы просто хотим повторить цикл for и распечатать его без учета кеша процессора.
Решение
Часть «печать» будет одинаковой независимо от того, где хранится объект.
Единственной частью, которая будет отличаться, является «переход к следующему элементу».
Для массива это включает в себя увеличение указателя — возможно, самая быстрая операция ЦП.
Для связанного списка это включает в себя загрузку значения из памяти — действительно быстрая операция, но не была быстрой, как приращение.
Тогда есть другие проблемы. Массив будет смежным и займет меньше общего пространства, чем связанный список, что означает лучшее использование кэша.
Но имейте в виду, что оба они невероятно быстрые, но массив будет немного быстрее.
Другие решения
Разница незначительна. Это будет зависеть от того, как именно вы пишете цикл, и от оптимизации в компиляторе. Если вы напечатаете его на экране в графическом интерфейсе, это само по себе будет иметь больше накладных расходов, чем оба вместе взятых.
Массив быстрее, чем связанный список. Главным образом потому, что массив последовательно хранит все элементы. Основной связанный список не гарантирует последующий доступ.
Без учета кеша процессора это довольно странное предположение, потому что в основном кеш дает основную производительность при использовании массива над связанным списком.
Связанный список имеет указатели, которые связывают элементы друг с другом, в то время как массив не имеет этой переоцененной структуры. Вы перебираете массив, но не перебираете связанный список напрямую.
Вы не должны сравнивать их математически с точки зрения обозначения Big O, потому что это дает ту же производительность («Дьяволы в деталях»).
Массивы всегда будут быстрее по сравнению с LinkedList. Массивы сохраняют данные непосредственно в ячейке памяти. Linkedlist создаст узлы, добавит данные к узлам и затем сохранит их. Опять же, при итерации связанного списка будут использоваться указатели для перехода к следующему элементу и печати, тогда как в массивах вы предоставляете только местоположение, которое будет от 0 до размера массива. ..
Предполагая, что ваш запрос только о последовательном доступе.
Массивы будут быстрее в любой момент времени для последовательного доступа, основная причина в том, что более новый процессор оптимизирован для этого.
Если мы проигнорируем оптимизацию процессора, даже после этого доступ к массиву будет быстрее. Давайте рассмотрим шаги для обеих операций, которые помогут понять причину.
Доступ к массиву:
int a[10];
int *ptr = a;
Доступ к следующему элементу все о выполнении
*(ptr++);
Вовлеченные операции
1. Чтение значения ptr
2. Увеличить текущее значение на 1
3. Доступ к новому адресу
Связанный список:
Node {
int data;
Node* next;
};
Доступ к следующим данным будет
(*(node->next))->data;
- чтение значения узла
- перейти к таблице адресов, чтобы добраться до члена
- читать значение следующего
- доступ к значению в следующем
Надеюсь, что это поможет вам понять, почему доступ к массиву будет быстрее. также при добавлении оптимизации процессора для массива 1 & 2 будет оптимизирован еще дальше. Сказав, что в реальном приложении вы почувствуете незначительную разницу
detector