Matavimas: kur sąrašas pralaimi ir kur laimi

Štai kas atspausdinta. Tavo skaičiai turi sutapti — -seed 42, n = 100 000.

$ algo playlist -in big.jsonl -from 47 -to 3
move 47 -> 3 in a library of 100000

                             walk/shift pointer writes
slice (shift)                        44              0
Playlist (ours)                      50              4
container/list                       50       (hidden)

Sąrašas pralaimėjo. Ne truputį — pralaimėjo, nors jo perkėlimas tikrai kainavo tik keturias rodykles, kaip ir žadėta.

Priežastis yra walk stulpelyje. Kad pasiektų 47-ą ir 3-ią mazgus, sąrašas nuėjo 50 šuolių. Masyvui eiti niekur nereikėjo — jis iš karto žino, kur yra 47-as elementas, ir jam liko tik pastumti 44 elementus.

O(1) perkėlimas yra tikras. Bet iki jo reikia nueiti O(n) kelią, ir tas kelias brangesnis už patį stūmimą.

Kai skirtumas tampa juokingas

$ algo playlist -in big.jsonl -from 500 -to 499
                             walk/shift pointer writes
slice (shift)                         1              0
Playlist (ours)                     999              4
container/list                      999       (hidden)

Perkelti elementą per vieną poziciją: masyvui — vienas pastūmimas, sąrašui — 999 šuoliai. Tūkstantį kartų daugiau darbo, kad būtų atliktas „efektyvesnis" O(1) veiksmas.

Ir kai sąrašas laimi

Visi skaičiai viršuje daro vieną prielaidą: kad poziciją reikia surasti. Bet grojaraštį tempiantis vartotojas nieko neieško — jis jau laiko tą takelį. Tas pats matavimas be paieškos:

$ algo playlist -in big.jsonl -from 99000 -to 50
                             walk/shift pointer writes
slice (shift)                     98950              0
Playlist (ours)                   99050              4

and if you ALREADY HOLD the node (a drag-and-drop UI does):
slice (shift)                     98950              0
Playlist (ours)                       0              4

98 950 prieš 4. Dvidešimt keturi tūkstančiai kartų. Štai kam susietas sąrašas.

Taisyklė

Susieto sąrašo O(1) yra tikras, bet jis prasideda nuo mazgo, ne nuo pozicijos. Jei poziciją dar reikia surasti, jau sumokėjai O(n) — ir sumokėjai brangiau, negu būtų kainavęs paprastas pastūmimas.

Todėl susietas sąrašas beveik niekada nenaudojamas vienas. Jis naudojamas kartu su indeksu, kuris duoda mazgą iš karto — su maišos lentele (10 pamoka). Tada gauni abu dalykus: O(1) suradimą ir O(1) perkėlimą.

Tai pirmas kartas kurse, kai dvi struktūros dirba kartu, o ne varžosi. Ne paskutinis.