В классическом руководстве по разработке алгоритмов Стивена Скиенны говорится, что связанный список быстрее, чем динамический массив с точки зрения создания. Является ли это причиной того, что куча работает быстрее? Может ли кто-нибудь объяснить это с точки зрения операционных систем?
Более быстрое время доступа, стек или куча?
comment
Означает ли создание создание исходного пустого списка/массива или означает создание нового элемента в списке/массиве?
- person maxywb schedule 27.08.2013
Ответы (1)
И список ссылок, и динамический массив хранятся в куче. Вставка в динамический массив может привести к увеличению массива, тогда как со списком ссылок это будет добавление в конец. Даже если вставка находится в середине списка ссылок, потребуется время на поиск, а затем всего одна операция для добавления указателя на предыдущий узел. Список ссылок не потребует корректировки на соседние места памяти.
По сравнению со связанными списками динамические массивы имеют более быструю индексацию (постоянное время по сравнению с линейным временем) и, как правило, более быструю итерацию из-за улучшенной локальности ссылки; однако динамические массивы требуют линейного времени для вставки или удаления в произвольном месте, так как все последующие элементы должны быть перемещены, в то время как связанные списки могут делать это за постоянное время. Этот недостаток смягчается буфером промежутков и варианты многоуровневого вектора обсуждаются ниже в разделе «Варианты». Кроме того, в сильно фрагментированной области памяти может быть дорого или невозможно найти непрерывное пространство для большого динамического массива, тогда как связанные списки не требуют непрерывного хранения всей структуры данных.
person
Habib
schedule
27.08.2013
