Grojaraščio problema

Antros pamokos namų darbo paskutinis klausimas prašė scenarijaus, kuriame []Item netinka. Štai jis.

Grojaraštis

Vartotojas pele nutempia takelį iš 47 pozicijos į 3. Tada iš 12 į 80. Tada dar kartą. Bibliotekoje 100 000 įrašų.

Su []Item kiekvienas toks perkėlimas pastumia visus tarp jų esančius elementus. Tai O(n), ir tai daroma kiekvieno pelės judesio metu.

Struktūra, kuriai to daryti nereikia, atrodo taip:

  ┌──────┐     ┌──────┐     ┌──────┐
  │ Item │ ←→  │ Item │ ←→  │ Item │
  └──────┘     └──────┘     └──────┘

Kiekvienas mazgas (node) laiko savo įrašą ir dvi rodykles — į kaimyną kairėje ir dešinėje. Elementai atmintyje nebeguli iš eilės. Būtent todėl nieko nereikia stumdyti: kad įterptum mazgą tarp dviejų kitų, pakeiti keturias rodykles ir baigta.

Keturias — nesvarbu, ar sąraše 10, ar 10 000 000 įrašų. Tai O(1).

Ką už tai sumoki

Trys dalykai, ir visi trys svarbūs:

1. Nebėra indeksavimo. lib[47] masyve yra viena daugyba. Susietame sąraše 47-o mazgo nėra kaip apskaičiuoti — reikia nueiti nuo pradžios per 47 mazgus. Indeksavimas iš O(1) tampa O(n).

2. Daugiau atminties. Kiekvienas mazgas prideda dvi rodykles — 16 baitų 64 bitų sistemoje — prie kiekvieno įrašo.

3. Išbarstyta atmintis. Masyvo elementai guli greta, tad procesorius juos skaito paketais. Mazgai išmėtyti po visą atmintį, ir kiekvienas šuolis gali reikšti naują kreipimąsi į atmintį.

Trečioji kaina neatsiranda skaičiuojant Big-O. Ketvirtame žingsnyje ji pasirodys matavime.