bmaxa
Legenda
- Poruka
- 70.815
Sortiranje linked lista je bolje in place nego kad se prespajaju node, nakon sto je lista alocirana tako da u memoriji jedan nod sledi drugi u redosledu liste. Recimo kod mene in-place qsort je 5 puta brzi od merge sorta koji prespaja node
Naravno razlika je manja ako sam nod sadrzi pokazivac na neki drugi podatak.
Takodje traversiranje kroz btree je 10 puta brze nego traversiranje kroz binarno stablo. To je zato sto je cache memorija 10 puta brza od RAM-a i onda se nevidjeno vide efekti gde god je pristup podacima sekvencijalan i gde se moze raditi read ahead.
I na kraju traversiranje linked liste nakon sorta koji prespaja node je daleko sporije nego traversiranje nakon in-place sorta, upravo zbog toga.
Naravno razlika je manja ako sam nod sadrzi pokazivac na neki drugi podatak.
Takodje traversiranje kroz btree je 10 puta brze nego traversiranje kroz binarno stablo. To je zato sto je cache memorija 10 puta brza od RAM-a i onda se nevidjeno vide efekti gde god je pristup podacima sekvencijalan i gde se moze raditi read ahead.
I na kraju traversiranje linked liste nakon sorta koji prespaja node je daleko sporije nego traversiranje nakon in-place sorta, upravo zbog toga.