Dalinės tvarkos pakanka

100 000 knygų. Reikia dešimties geriausiai įvertintų.

Spėk prieš skaitydamas toliau

Akivaizdus būdas: surikiuoti pagal Rating ir paimti pirmus dešimt. Devinta pamoka rikiuoja 100 000 įrašų per milisekundes, tad tai nė neatrodo brangu.

Ar galima rasti geriausius dešimt NESURIKIAVUS? Ir jei taip — kiek palyginimų reikėtų mažiausiai?

Užsirašyk skaičių.

Matavimas

$ algo top -in s100k.jsonl -k 10
n = 100000, k = 10

                            comparisons         time       per item
  heap of size k                 100251      1.002ms           1.00
  sort.Slice, take k             841189      6.014ms           8.41

  ratio: 8.4x fewer comparisons
  same k ratings? true

1.00 palyginimo vienam įrašui.

Ne 8.41. Ne log2(100000) = 16.6. Vienas. Krūva peržiūri kiekvieną įrašą lygiai po vieną kartą ir beveik kiekvieną iškart išmeta.

Ir paskutinė eilutė sako, kad atsakymai sutampa: same k ratings? true.

Kodėl vieno pakanka

Krūvoje guli dešimt geriausių iki šiol matytų. Jos mažiausias elementas — silpniausias iš tos dešimties.

Ateina naujas įrašas. Vienas palyginimas su tuo silpniausiu:

• jei jis prastesnis — jis negali priklausyti geriausiam dešimtukui, nes yra prastesnis už dešimt jau turimų. Išmetamas. Vienas palyginimas, viskas;
• jei geresnis — silpniausias išeina, naujas įeina. Tai Pop + Push, apie 2 · log2(10) ≈ 7 palyginimų.

Prie atsitiktinių duomenų antrasis atvejis pasitaiko vis rečiau: kad patektum į dešimtuką iš 100 000, reikia būti geresniam už dešimt geriausių iš jau matytų. Todėl vidurkis ir prilimpa prie vieno.

Rikiavimas atsako į klausimą „kokia visų tvarka?". Tau reikėjo atsakymo į „kurie dešimt geriausi?". Pirmasis klausimas sunkesnis, ir už jį buvai bemoką.

Dalinės tvarkos pakanka

Krūva nerikiuoja. Trečiame žingsnyje testas to net reikalauja.

Ji žino vieną dalyką — savo mažiausią elementą — ir nieko daugiau. Broliai tarp savęs neišrikiuoti, gilesni lygiai jokios tvarkos neturi.

Dešimtoje pamokoje maišos lentelė atsisakė tvarkos visiškai ir už tai gavo O(1). Vienuoliktoje medis tvarką išlaikė pilną ir sumokėjo O(log n). Krūva stovi tarp jų:

struktūra	kiek tvarkos	ką gauna
maišos lentelė (10)	jokios	O(1) tikslaus rakto paieška
krūva (13)	tik mažiausias	O(1) minimumas, O(log n) įdėti ar paimti
BST / AVL (11-12)	pilna	rėžiai, kaimynai, surikiuotas išvedimas

Imk tiek tvarkos, kiek klausimui reikia, ir nė kiek daugiau. Tai visos šios pamokos mintis, o krūva — jos aiškiausias pavyzdys.

Kur riba

Krūva nelaimi visada. Padidink k:

$ for k in 1 10 100 1000 10000 100000; do algo top -in s100k.jsonl -k $k; done

       k      krūva      rikiavimas
       1      99999          841189
      10     100251          841189
     100     105510          841189
    1000     180960          841189
   10000     878748          841189
  100000    3037870          841189

Persivertimas yra tarp k = 1 000 ir k = 10 000, maždaug ties k ≈ n/10. Prie k = n krūva atlieka 3.6 karto daugiau darbo nei rikiavimas.

Taip ir turi būti: O(n log k) yra laimėjimas tik tol, kol log k gerokai mažesnis už log n. Kai k = n, tai tas pats O(n log n) — tik su blogesne konstanta, nes kiekvienas elementas eina per Push ir Pop atskirai.

TestTopKLosesWhenKApproachesN reikalauja, kad taip ir liktų.

Ir laikrodis sutinka

$ go test -run XXX -bench 'TopK' -benchtime=20x -count=5

BenchmarkTopKHeap-32      20     680625 ns/op
BenchmarkTopKHeap-32      20     666920 ns/op
BenchmarkTopKHeap-32      20     700495 ns/op
BenchmarkTopKSort-32      20    6032965 ns/op
BenchmarkTopKSort-32      20    6152325 ns/op
BenchmarkTopKSort-32      20    6041960 ns/op

0.67–0.70 ms prieš 6.03–6.16 ms. 8.9 karto, ir rėžiai net nesiliečia.

Čia skaitiklis ir laikrodis sutaria. Kitame žingsnyje — nesutars.