Teorija

72.7 karto darbo, 16.9 karto laiko

Pirmame žingsnyje užsirašei du skaičius: kiek kartų daugiau darbo ir kiek kartų ilgiau.

$ algo frontier
nodes 1000, edges 742, 561 reachable destinations from 0

                                   queue work         time
  binary heap (lesson 13)             5567392         32ms
  linear min-scan                   404796000        546ms

  identical cost on 561 of 561 destinations
  work ratio  72.7x
  time ratio  16.9x

Pirmiausia — eilutė, be kurios visa lentelė nieko nereikštų:

identical cost on 561 of 561 destinations.

Eilės pakeitimas nekeičia atsakymo. Keičiasi tik tai, kiek laiko jo laukiama. Todėl du likę skaičiai apskritai palyginami.

Ir jie nesutampa

darbo santykis   72.7x
laiko santykis   16.9x

Skaitiklis sako, kad tiesinė versija atlieka 72.7 karto daugiau darbo. Laikrodis sako, kad ji trunka 16.9 karto ilgiau.

Skirtumas — daugiau nei keturis kartus.

Kodėl skaitiklis pervertina

Tiesinės peržiūros darbas yra for v := 0; v < n; v++ per gretimą masyvą. Procesorius tokį ciklą mėgsta: adresai nuspėjami, duomenys traukiami paketais, šaka visada ta pati. Vienas žingsnis ten yra pigus.

Krūvos darbas yra kilimas ir leidimasis šokinėjant po 2i+1 ir (i−1)/2 — adresai peršoka, kiekvienas palyginimas gali laukti atminties, o šaka nenuspėjama. Vienas žingsnis ten brangesnis.

Skaitiklis abu vadina „vienu". Jie nėra vienas.

Šeštas kartas — ir pirmas šia kryptimi

Ši riba kurse jau pažįstama, bet iki šiol ji visada veikė ta pačia puse:

pamoka	ką pasakė skaitiklis	ką pasakė laikrodis
4	nulis (atmintis nematoma)	krūva augo
6	persikirtimas ties n ≈ 3	ties n ≈ 6 — prietaisas pakeitė matavimą
11	identiška: 5000.5 abiem	4.5 karto skirtumas
12	AVL pigesnis 23 %	AVL 1.65 karto brangesnis
13	identiška abiem krūvoms	1.66 karto skirtumas
15	72.7 karto	16.9 karto

Ketvirtu, vienuoliktu ir trylikta kartais skaitiklis nuvertino skirtumą. Dvyliktą kartą jis apsiriko ženklu.

Čia jis pervertina — pirmą kartą kurse. Ir tai ne todėl, kad jis blogesnis, o todėl, kad matuojamas dydis kitas.

Skaitiklis matuoja, kiek operacijų atliekama. Laikrodis matuoja, kiek kainuoja jas atlikti. Kai operacijos nevienodos, du skaičiai išsiskiria — ir abu teisingi.

`transit` tą patį mato didesniu masteliu

Mūsų matavimas (docs/reference/transit-benchmarks.md), trys užklausos:

užklausa	tiesinės eilės darbas	krūvos darbas	darbo santykis	laiko santykis
cross-city	92 200 762	370 053	249×	16.0×
slow-naive	95 179 989	370 009	257×	18.9×
worst-case	988 259 147	3 047 930	324×	16.4×

Darbo santykis ten yra 15–20 kartų didesnis už laiko santykį. Mūsų — 4.3 karto. Ta pati kryptis, tas pats mechanizmas, skirtingas mastelis.

Ir atkreipk dėmesį į laiko stulpelį: 16.0, 18.9, 16.4. Mūsų — 16.9. Skirtingas grafas, skirtingi duomenys, skirtinga programa, tas pats skaičius.

Tai ir yra tikrasis Dijkstros eilės pagerinimo dydis: maždaug 16–19 kartų.

Ką iš to pasiimti

Ne „skaitikliu nepasitikėk". Pirma pamoka jį pasirinko teisingai ir dėl teisingos priežasties — jis nepriklauso nuo mašinos, o laikrodis priklauso.

Bet po penkiolikos pamokų atsakymas tikslesnis: