Pratybos

Penkios užduotys.

---

1. Heapsort

Krūvos ištuštinimas duoda didėjimo tvarką — vadinasi, tai rikiavimo algoritmas. Parašyk heapSort(items []Item, c *metrics.Counter) []Item: pastatyk krūvą ir išimk viską į griežinį.

Jis yra O(n log n), gali veikti vietoje ir nereikalauja papildomos atminties. Tai kaip jis atrodo šalia 7–9 pamokų?

n=100000: heapsort 3002497 palyginimų, sort.Slice 813236 (3.69x)

3.69 karto daugiau palyginimų nei sort.Slice. Paaiškink, iš kur jie — suskaičiuok, kiek palyginimų vienam lygiui atlieka Pop, ir palygink su vienu suliejimo žingsniu aštuntoje pamokoje.

Tada atsakyk: heapsort yra O(n log n) ir nereikalauja papildomos atminties, o suliejimo rikiavimas reikalauja. Kodėl vis dėlto niekas jo nenaudoja kaip numatytojo?

---

2. Pastatyk krūvą kitaip

n elementų paversti krūva galima dviem būdais: n kartų iškviesti Push arba sudėti visus į masyvą ir kiekvieną nuleisti žemyn, pradedant nuo n/2 − 1. Antrasis vadinamas heapify.

Vadovėlis sako, kad n Push'ų yra O(n log n), o heapify — O(n). Pamatuok:

atsitiktiniai duomenys
n=  1000: 1000 Push kainavo     2234 palyg. (2.23/elem.); heapify     1867 (1.87/elem.)
n=100000: 100000 Push kainavo 223155 palyg. (2.23/elem.); heapify   187550 (1.88/elem.)

Abu tiesiniai, o heapify laimi tik 16 %. Vadovėlio log n kažkur dingo.

Dabar paduok tvarkingus duomenis:

n=100000: Push didėjant 99999 (1.00/elem.) · Push mažėjant 1468946 (14.69/elem.) · heapify 199978 (2.00/elem.)

Štai jis. Paaiškink visus tris stulpelius: kodėl didėjanti įvestis min-krūvai yra geriausias Push atvejis, kodėl mažėjanti — blogiausias, ir kodėl heapify tai nerūpi.

Tada pasakyk, kurį iš trijų skaičių turi omenyje vadovėlio O(n log n), ir kodėl atsitiktiniai duomenys atsidūrė taip arti geriausio atvejo.

---

3. Max-krūva be antros realizacijos

algo top reikia aukščiausių įvertinimų, o tu pastatei min-krūvą. Max-krūvą gauti galima trimis būdais:

• nukopijuoti heap.go ir apversti visus < į >;
• saugoti -Rating ir neigti išimant;
• laikyti palyginimo funkciją struktūros lauke.

Realizuok vieną. Tada pagrįsk arba paneik kitus du — įskaitant tai, kiek kainuoja trečiasis, atsižvelgiant į šeštą žingsnį. (func laukas nėra sąsaja. Ar tai svarbu? Pamatuok.)

---

4. Pakavimas ar iškvietimai?

Šeštas žingsnis įvardijo du įtariamuosius ir jų neatskyrė. Atskirk.

Parašyk trečią krūvą: vėl container/heap, bet virš []*Item, ne []Item. Rodyklė yra rodyklės formos, tad telpa į sąsajos reikšmę ir nekopijuojama į krūvą — gauni iškvietimus be pakavimo.

BenchmarkHeapMine-32          20   1152790 ns/op    565248 B/op        1 allocs/op
BenchmarkHeapStdlibPtr-32     20   1158620 ns/op     81944 B/op        2 allocs/op
BenchmarkHeapStdlib-32        20   1932750 ns/op   3934116 B/op    20020 allocs/op

Su rodyklėmis container/heap susilygina su ranka rašyta krūva. Visas 1.66 karto skirtumas buvo pakavimas; iškvietimai nekainavo nieko pamatuojamo.

Paaiškink, kodėl iškvietimai pasirodė nemokami — kvietimo vieta monomorfinė, o šaka nuspėjama idealiai. Tada atsakyk į svarbųjį klausimą: ar tai reiškia, kad container/heap vis dėlto tinka? Ką rodyklinė versija tau kainavo, ko reikšminė nekainavo? (Pažiūrėk, kur dabar guli patys Item, ir prisimink, ką vienuolikta pamoka pamatavo apie išbarstytą atmintį.)

---

5. Persivertimas, tiksliai

Penktas žingsnis padėjo top-k persivertimą tarp k = 1 000 ir k = 10 000 prie n = 100 000.

Rask jį tiksliai, dalydamas pusiau. Tada pakartok prie n = 10 000 ir n = 1 000 000.

Ar persivertimas yra pastovus k, pastovus santykis k/n, ar dar kas nors? Suformuluok taisyklę, kada imti krūvą, o kada rikiuoti, ir parodyk matavimą, ant kurio ji stovi.