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