Ką penkiolika pamokų sudėjo
Penkiolika pamokų. Vienas skaitiklis, viena biblioteka, dvylika struktūrų. Verta surinkti, kas iš to lieka.
Rikiuota įvestis, ketvirtą kartą
-sorted vėliavėlę pasidarei pirmoje pamokoje ir nuo tada ji tris kartus buvo
bėda:
| pamoka | ką padarė rikiuota įvestis |
|---|---|
| 7 | įterpimo rikiavimui — geriausias atvejis |
| 8 | quicksort'ui — blogiausias, O(n²) |
| 11 | BST — katastrofa: aukštis n, tas pats 5000.5 kaip tiesinei paieškai |
| 15 | CSA — visa jos veikimo sąlyga |
Ketvirtą kartą tvarka nėra nei geriausias, nei blogiausias atvejis. Ji yra tai, dėl ko algoritmas apskritai egzistuoja: CSA nedaro nieko, ko nedarytų paprastas ciklas, ir laimi 76 kartus vien todėl, kad duomenys jau sudėti laiko tvarka.
Ta pati savybė, keturi skirtingi vaidmenys. Duomenys nėra geri ar blogi — jie tinka arba netinka tam, ką su jais darai.
Ko skaitiklis nemato — šešios progos
Penktame žingsnyje surinkta lentelė. Taisyklė, kurią ji duoda, viena:
Skaitiklis matuoja, kiek operacijų. Laikrodis — kiek jos kainuoja. Sudėtingumui užtenka pirmojo; sprendimui reikia abiejų.
Pirma pamoka pasirinko skaitiklį ne dėl to, kad jis geresnis, o dėl to, kad
O(n²) neturi vieneto milisekundėmis. Tai tebėra teisinga. Bet keturioliktoje
pamokoje matei, kad tas pats palyginimų skaičius gali kainuoti 4.5 karto
skirtingai, o čia — kad 72.7 karto daugiau darbo gali reikšti 16.9 karto ilgesnį
laiką.
Kada abstrakcija nemokama
Trys matavimai, viena taisyklė (13 pamoka):
Abstrakcija nemokama, kai kompiliatorius gali ją permatyti. Ji brangi, kai priverčia pakuoti duomenis operacijai, kuri per maža, kad tą kainą paslėptų.
sort.Search laimėjo. container/list sulygino. container/heap pralaimėjo
1.66 karto — ir šioje pamokoje transit tą patį parodo Dijkstroje: 1.37 karto.
Keturi nepriklausomi matavimai, viena priežastis.
Trys struktūros, vienas klausimas
Dešimta–dvyliktos pamokos:
| ką nusipirko | kuo sumokėjo | |
|---|---|---|
| maišos lentelė | O(1) tikslaus rakto paieškai | visa tvarka |
| BST | tvarką ir visas jos operacijas | garantiją |
| AVL | garantiją atgal | konstantą — 1.65× lėtesnis įterpimas |
Ir penkiolikta prideda ketvirtą eilutę, kitos rūšies:
| ką pakeitė | ką laimėjo | |
|---|---|---|
| CSA | klausimą | 76× — ir nebeliko struktūros |
Paskutinis dalykas
Trys pakopos, viena po kitos, tuo pačiu uždaviniu:
- tiesinė peržiūra → krūva: ~16–19 kartų;
- krūva → A*: pralaimėjimas, nes euristika matė 4.1 % kainos;
- Dijkstra → CSA: dar 76 kartai, ir prioritetinė eilė dingo visai.
Prioritetinės eilės tobulinimas nupirko ~20 kartų. Uždavinio struktūros supratimas nupirko dar 76 ir ištrynė eilę.
Bendras algoritmas yra tai, ko griebiesi, kai nežinai savo uždavinio formos. Kai ją sužinai, dažnai gali padaryti geriau.
Dijkstra teisinga bet kuriam svoriniam grafui su neneigiamomis briaunomis — todėl ji ir yra pirmas atsakymas. CSA teisinga tik tvarkaraščiams, kur klausimas „kada anksčiausiai atvyksiu" — ir todėl ji 76 kartus greitesnė.
Nė vienas iš šitų dviejų faktų nėra kompromisas. Jie yra ta pati mintis iš dviejų pusių.
Ką iš tikrųjų turi
Nuo šiol žinai dvylika struktūrų ir kokia dvidešimt algoritmų. Bet kursas buvo ne apie juos.
Kiekvienoje pamokoje kelias buvo tas pats:
- užduok konkretų klausimą apie savo duomenis;
- pamatuok, ką kiekvienas variantas už jį ima — palyginimais ir laikrodžiu, nes jie sako skirtingus dalykus;
- įvardyk, ko variantas NEGALI, ne tik ką daro lėtai;
- paklausk, ar blogiausias atvejis nemalonus, ar nepriimtinas;
- ir patikrink prielaidą, kuria remiasi visa konstrukcija — nes vieną kartą ji buvo baitai vietoj runų, kitą — neneigiamos briaunos, trečią — įterpimo tvarka.
Struktūros pasikeis. Šitas penketas — ne.