Namų darbas

Ką atiduoti

algo su dc ir stable, praeinantį go test ./..., ir matavimų ataskaitą.

1. Keturios tvarkos, keturi algoritmai

n = 10 000, visos keturios tvarkos, visi keturi algoritmai — šešiolika eilučių:

tvarka	algoritmas	palyginimai	perkėlimai	laikas

Pažymėk kiekvienoje tvarkoje greičiausią. Ar nugalėtojas visur tas pats?

2. Riba, ties kuria O(n log n) atsiperka

Septintoje pamokoje įterpimo rikiavimas beveik tvarkingiems duomenims aplenkė sort.Slice iki maždaug n = 2 000.

Pakartok su savo suliejimo rikiavimu: nuo kokio n jis aplenkia tavo įterpimo rikiavimą? Matuok -order nearly ir -order shuffled atskirai — atsakymai skirsis.

3. Kvadratas grįžta

Patvirtink, kad QuickSortNaive surikiuotiems duomenims yra tiksliai n(n−1)/2:

n	palyginimai	n(n−1)/2	sutampa?
100
1 000
5 000

4. Atminties kaina

Suliejimo rikiavimas reikalauja papildomos vietos, greitasis — ne.

Pamatuok abiejų atminties sunaudojimą 100 000 įrašų (runtime.ReadMemStats, kaip ketvirtoje pamokoje). Nurodyk santykį baitais vienam įrašui.

Kada šis skirtumas nulemtų tavo pasirinkimą?

5. Neišmatuotas rikiavimas tikroje sistemoje

transit greičiausias maršrutų algoritmas (Connection Scan) aplenkia geriausią Dijkstrą maždaug 76 kartus. Visas jo paruošimas — vienas rikiavimas; šaltinyje tai pasakyta tiesiai: „This sort is the algorithm's entire preprocessing step." Rikiuojama 196 412 jungčių pagal išvykimo laiką, o lygiuosius sprendžia reiso numeris — tas pats determinuotas raktas, kaip 6 žingsnyje.

To rikiavimo kainos transit niekada nepamatavo. Nė viename jo matavime jos nėra.

Įvertink ją: 196 412 elementų, O(n log n). Kiek palyginimų? Palygink su tuo, ką Connection Scan sutaupo vienai užklausai (~0,7 ms prieš ~53 ms).

Po kelių užklausų tas rikiavimas atsiperka? Ir ar 76 kartų pagreitėjimas vis dar teisingas skaičius, jei paruošimą įskaitytum?

(Tai ne kritika. Tai klausimas, kurio niekas neuždavė — todėl jis tavo.)