Stebim, kaip auga talpa
Sukurk stats.go (žr. dešinėje). Jis prideda dvi komandas: algo load ir
algo stats -growth.
stats -growth prideda po vieną įrašą ir spausdina slice antraštę kiekvieną
kartą, kai pasikeičia cap. Kiekviena tokia eilutė yra vienas naujas
masyvas ir vienas pilnas kopijavimas.
Kaip iš tikrųjų auga Go slice
$ algo stats -growth -n 1000
append len cap items copied
1 1 1 0
2 2 2 1
3 3 4 2
5 5 8 4
9 9 18 8
19 19 36 18
37 37 73 36
74 74 146 73
147 147 292 146
293 293 585 292
586 586 1024 585
1000 appends, 11 reallocations, 1165 items copied in total
average copies per append: 1.165
Vadovėlis sako „talpa dvigubėja". Pažiūrėk į skaičius: 1, 2, 4, 8, 18, 36, 73, 146, 292, 585, 1024.
Aštuoniolika, ne šešiolika. Septyniasdešimt trys, ne septyniasdešimt du. Tūkstantis dvidešimt keturi, ne tūkstantis šimtas septyniasdešimt.
Go dvigubina tik pradžioje. Peraugęs kelis šimtus elementų, jis auga maždaug 1,25 karto, o gautą dydį dar suapvalina iki atminties skirstyklės dydžio klasės. Vadovėlio taisyklė yra apytikslė; tikroji elgsena yra ta, kurią ką tik pamatavai.
Kiek iš tikrųjų kainuoja „amortizuota"
Vienas skaičius atsako į viską. Padidink n ir stebėk paskutinę eilutę:
| n | perkėlimai | perkopijuota | vidurkis vienam append |
|---|---|---|---|
| 1 000 | 11 | 1 165 | 1,165 |
| 10 000 | 19 | 35 540 | 3,554 |
| 100 000 | 29 | 456 253 | 4,563 |
| 1 000 000 | 39 | 4 467 696 | 4,468 |
Du dalykai matosi iš karto.
Vidurkis nustoja augti. 100 000 ir 1 000 000 duoda beveik tą patį — apie
4,5 kopijavimo vienam append. Tai ir yra amortizuota O(1): vidurkis yra
pastovus. Jei append būtų tikrai O(n), prie milijono būtum pamatęs apie
500 000, o ne 4,5.
Bet konstanta nėra 1. Ji yra ~4,5, ir tai tiesiogiai išplaukia iš 1,25 augimo koeficiento: kai talpa auga g kartų, vidutiniškai kopijuojama ~1/(g−1) karto, o 1/(1,25−1) = 4.
„Amortizuota O(1)" nereiškia „nemokama". Ji reiškia „pastovi". Konstantą gali pamatuoti — ir ką tik pamatavai.
Perkėlimų skaičius auga logaritmiškai: 11, 19, 29, 39 — po maždaug dešimt kiekvienai n dešimčiai. Tūkstantį kartų daugiau duomenų kainuoja dvidešimt papildomų perkėlimų, ne tūkstantį.