Kaip iš tikrųjų veikia slice

Pirmoje pamokoje bibliotekai naudojai []Item ir apie tai negalvojai. Dabar pagalvok, nes visos vėlesnės struktūros bus lyginamos su šituo.

Ką iš tikrųjų laiko slice kintamasis

Go slice nėra masyvas. Tai trijų laukų antraštė, kuri rodo į masyvą:

Laukas	Ką reiškia
rodyklė	kur atmintyje prasideda tikrasis masyvas
len	kiek elementų naudojama dabar
cap	kiek telpa neperkeliant masyvo

64 bitų sistemoje ta antraštė yra 24 baitai — trys po aštuonis. Įsidėmėk šį skaičių; trečiame žingsnyje jis pasirodys tikroje sistemoje.

Kas kiek kainuoja

Veiksmas	Kaina	Kodėl
lib[i]	O(1)	adresas = pradžia + i × dydis. Vienas daugybos veiksmas.
append kai len < cap	O(1)	įrašo į jau turimą vietą
append kai len == cap	O(n)	naujas masyvas + viskas perkopijuojama
įterpti / ištrinti viduryje	O(n)	visi tolesni elementai pasislenka

Dvi eilutės čia nemalonios, ir abi bus svarbios:

Įterpimas į vidurį yra O(n). Ne todėl, kad paieška lėta — vietą jau žinai — o todėl, kad masyve elementai guli iš eilės, ir vietos naujam viduryje nėra, kol nepastumsi visų kitų. Trečioji pamoka statys struktūrą, kuriai to daryti nereikia.

append kartais kainuoja O(n). Bet ne dažnai. Kiek dažnai — ne spėsi, o pamatuosi.

Amortizuota O(1)

Sakoma, kad append yra „amortizuota O(1)": vidutiniškai pastovus laikas, nors kai kurie iškvietimai brangūs.

Žodis „amortizuota" reiškia vidurkį per daug veiksmų, o ne „paprastai greita". Ir jis reiškia, kad vidurkis yra pastovus — ne kad jis mažas. Antrame žingsnyje pamatysi, koks jis iš tikrųjų.