funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

Vstříc řazení v lineárním čase

7. 2. 2017 — k47

Obecné řazení v li­ne­ár­ním čase je meta, které není možné do­sáh­nout1 . Ve vý­sledné slo­ži­tosti se vždycky vy­skytne log(n) faktor. Může být mas­ko­vaný za něco jiného, ale vždycky tam bude. Třeba takový LSD radix sort má slo­ži­tost O(kn), kde k je právě log(n) v pře­vleku.

Ale to, že ne­mů­žeme vyhrát na te­o­re­tické frontě, není dů­le­žité. Záleží jenom na tom, jestli můžeme vyhrát prak­ticky. Al­go­rit­mus nemusí být O(n), stačí jen když se bude tvářit jako O(n) pro všechny vstupy, které mu můžu re­a­lis­ticky před­ho­dit. Do­konce ani O(n) čas není dů­le­žitý, záleží jen na rych­losti.

O tom je tenhle článek: Ne­sna­žím se vyhrát, jen pro­hrá­vat co nejméně.


Jeden způsob velice rych­lého řazení je least sig­ni­fi­can digit (LSD) radix sort. Pro vstupní pole li­bo­volné délky je cena na prvek v pod­statě plochá (pro 4B hod­noty se po­hy­buje na úrovni 15ns/prvek). Jeho ne­vý­hoda spo­čívá v tom, že nej­lépe fun­guje jen pro krátké bitové stringy kon­stantní délky jako jsou 4B inty nebo 8B longy. Pra­cuje tedy na ome­ze­ném roz­sahu hodnot (232 nebo 264) na­místo ne­ko­nečné mno­žiny obec­ných ře­tězců. Pro ty jsou jiné al­go­ritmy: most sig­ni­fi­cat digit (MSD) radix sort nebo burst sort. Ty můžou být rych­lejší než kla­sické quick/merge/heap sorty, ale pořád jsou po­ma­lejší než velice kom­paktní LSD radix sort.

V ide­ál­ním světě by mělo být možné využít LSD radix sortu jako dílčí kom­po­nenty k řazení dlou­hých stringů. Dlou­hou dobu jsem pře­mýš­lel jak to udělat co nej­lépe, pro­tože nej­jed­no­dušší řešení – řazení LSD radix sortem podle pre­fixů stringů – ne­fun­guje zas tak dobře.

V pseu­do­kódu, který se podobá Scale, to může vy­pa­dat nějak takhle:

val strings: Array[String] = ???

val packed = new Array[Long](strings.length)

for (i <- 0 until strings.length) {
  val s = strings(i)

  // zabalit 4B prefix a 4B index do jednoho 8B longu
  packed(i) = prefixOfString(s).toLong << 32 | i
}

// samotné řazení
val sorted = RadixSort(packed, sortBytes = 4 until 8)

sorted
  .groupBy(p => p >> 32) // rozlámat výstup na bloky se stejným prefixem
  .map { case (prefix, ps) =>
    ps.map(p => p & 0xffffffff) // extrahovat index
      .map(i => strings(i))     // převést na vstupní stringy
      .sorted                   // výsledné skupiny seřadit jiným algoritmem
  }.flatten

Pro­blém tohoto pří­stupu je malá in­for­mační hod­nota pre­fixů. Pokud bych takto řadil Ja­vov­ské stringy ob­sa­hu­jící pře­de­vším znaky [a-zA-Z0-9], bylo by to ne­slavné, pro­tože Java string je v jádru pole dvou­baj­to­vých charů.

String "k47" je tvořen bajty 0 6B 0 34 0 37. Liché bajty ne­při­náší žádnou in­for­maci a ty sudé v tomto pří­padě ob­sa­hují jednu z 62 mož­ných hodnot. Jeden char tedy má jen něco málo pod 6 bitů in­for­mace.

Ve sku­teč­nosti je to ještě horší. Ně­které znaky jsou čas­tější než jiné a tedy při­náší ještě méně in­for­mace. 4 bajty pre­fixu můžou mít hodně pod 12 bitů in­for­mace, které můžou v nej­lep­ším pří­padě dis­kri­mi­no­vat mezi 4096 růz­nými pre­fixy. To není nic moc.5

Ra­di­x­sor­to­vání podle pre­fixu ne­fun­guje tak dobře jak by mělo na­vzdory tomu, že 4B int dokáže dis­kri­mi­no­vat mezi více jak 4 mi­li­ar­dami hodnot. Tohle mi ně­ja­kou dobu leželo na mysli. Po­tře­bo­val bych funkci, která mapuje vstupní string na 4B int, který ob­sa­huje víc in­for­mace než 4B prefix a tedy lépe roz­dělí vstupní data.

Kdy­bych měl funkci, která pře­trans­for­muje string na jeho po­řa­dové číslo, mám vy­hráno. Kdyby ta funkce běžela v O(1), měl bych řazení v O(n). To ale není možné, pro­tože taková funkce by zá­le­žela na všech n vstup­ních hod­no­tách.

Místo toho mi stačí funkce, která kom­pri­muje prefix, tedy vy­u­žije ma­xi­mum mož­ných in­for­mace z del­šího pre­fixu a zkom­pri­muje je do 4B nebo 8B čísla, které pak po­u­žiji k řazení rych­lým LSD radix sortem. Je po­třeba jen aby funkce ne­změ­nila vzá­jemné pořadí prvků. Může na­ma­po­vat ně­ko­lik růz­ných na jeden prefix, to je po­vo­lené a ne­vy­hnu­telné, ale nesmí změnit jejich vzá­jemné pořadí. Tedy na­pří­klad:

f(s) = Σ 1 / (s_i-96)^i

f("")       = 0.0
f("a")      = 0.0384
f("aa")     = 0.0399
f("aaaa")   = 0.03999
f("b")      = 0.0769
f("ggggga") = 0.2796
f("gggggz") = 0.2796 // kolize
f("z")      = 0.961

a = b  => f(a) = f(b)
a < b  => f(a) <= f(b)

Tuhle funkci můžu zkon­stru­o­vat ručně, pokud něco vím o řa­ze­ných datech2 nebo ji můžu vy­tvo­řit sta­tis­ticky ze vzorku vstup­ních stringů (před­po­klá­dám, že jed­not­livé bajty jsou na sobě ne­zá­vislé).6 Ty nej­čas­tější po­sky­tují mi­ni­mum in­for­mace a po­tře­buji tedy víc dal­ších bajtů, abych dostal dost in­for­mace pro přesné ma­po­vání. Ty nejméně časté po­sky­tují víc in­for­mace a samy o sobě vedou k re­la­tivně přesné dis­kri­mi­naci.7

Spo­čí­tám re­la­tivní frek­vence jed­not­li­vých bajtů, ty vy­u­žiji, abych pře­vedl každý string na pozici na in­ter­valu 0.0 – 1.0 a tu pak pře­vedu na plný in­ter­val longu` (jen se bojím, že se v tomto kroku můžou vy­skyt­nout chyby za­o­krouh­lo­vání, které poruší po­ža­da­vek na za­cho­vání pořadí).

Ukázka ma­po­vání se čtyřmi mož­nými hod­no­tami – a je velice časté, bc jsou méně časté a d je ra­ritní:

Když mám tuhle funkci, apli­kuji ji na každý řazený prvek (v ukázce pseu­do­kódu to na­hradí volání prefixOfString), se­sta­vím pole dvojic (prefix, index) za­ba­lené do longů, se­řa­dím radix sortem a pak roz­se­kám remízy jiným řa­dí­cím al­go­rit­mem3 .

A to je všechno. Nic víc v tom není. Po­u­ží­vám starý známý radix sort, změním jen data na kte­rých ho pouš­tím.

Dál se dá apli­ko­vat jen pár triků. Na­pří­klad můžu využít co nej­více bitů v longu do kte­rého je za­kó­do­ván pár (prefix, index). Index má ome­zené roz­mezí a na jeho re­pre­zen­taci je třeba méně místa než plných 32 bitů. Na­pří­klad pro 1 milion indexů stačí 20 bitů.

Místo

|*******|*******|*******|*******|*******|*******|*******|*******|
[ prefix 32 bitů                |                 index 32 bitů ]

pak můžu použít

|*******|*******|*******|*******|*******|*******|*******|*******|
[ prefix 44 bitů                            |     index 20 bitů ]

Ve stej­ných 8 baj­tech do­stanu delší prefix, který bude lépe dis­kri­mi­no­vat. Radix sort sice udělá víc prů­chodů (v mém pří­padě řadí v jenom prů­chodu jeden bajt, ale je možné napsat verzi, která řadí po 10 bitech), ale to není pro­blém, pro­tože RS je velice rychlý a v po­rov­nání s ostat­ními fázemi běží v za­ne­dba­tel­ném čase.

Ale pořád je třeba alo­ko­vat 24 bajtů na každý řazený prvek. To se nedá nijak obejít a je s tím třeba po­čí­tat. Sa­motná rych­lost alo­kace ale ne­před­sta­vuje pro­blém.

Vý­sledky jsou uspo­ko­jivé. f+sort je první jed­no­dušší verze, která tohle po­u­žívá jen jako pre­pro­ces­sing. Vezme celý vý­sle­dek LSD radix sortu tak jak je a seřadí ho. Ja­vov­ský Tim­Sort do­slova letí na už téměř se­řa­ze­ných vstu­pech. f+s*rt je to, co po­pi­suji výše.

Řazení slov z čes­kých textů:

Rych­lost na prvek byla téměř shodná pro 900000 slov i 4 mi­li­ony.

Řazení ná­hodně ge­ne­ro­va­ných stringů [a-zA-Z0-9]+:

V tomto pří­padě ma­po­vání fun­guje fan­tas­ticky a téměř vůbec není třeba dělat dru­hotné řazení. To je způ­so­beno tím, že stringy jsou dost dlouhé, ná­hodně roz­lo­žené a téměř bez du­pli­cit.

Úzká hrdla výkonu pře­kva­pivě před­sta­vuje pro­chá­zení prvků při kom­pri­maci pre­fixu, pře­rov­nání poin­terů podle vý­sled­ného pořadí radix sortu a in­spekce sa­mot­ných prvků při řazení (V ukázce kódu výše to od­po­vídá funkci prefixOfString, řádku „pře­vést na vstupní stringy“ a pak zá­vě­rečné metodě sorted). Každý tento přesun způ­sobí jeden ne­vy­hnu­telný cache-miss, který na mém stroji v nej­lep­ším pří­padě trvá 16ns. Tedy něco kolem 32-48 na­no­sekund je pro­mr­háno na dvou nebo třech mov in­struk­cích4 , zbytek trvá kom­pri­mace pre­fixů, pří­prava dat pro radix sort, sa­motný radix sort a zá­vě­rečné řazení.

Pro­storu pro zlep­šení už moc není a tohle může být velice blízko ma­xi­mální rych­losti, které je možné vůbec do­sáh­nout. A to podle mě docela dobře od­po­vídá pů­vod­nímu po­ža­davku pro­hrá­vat co nejméně.


Dále k tématu:


Pozn:

  1. Řadit v O(n) se dá jen ve spe­ci­ál­ních pří­pa­dech, kdy vstupní data mají ome­zený rozsah hodnot (Pi­ge­onhole sort, Coun­ting sort) nebo známé roz­lo­žení (Bucket sort).
  2. Můžu třeba stringy pře­vést na čí­sel­níky, kdy čí­selná re­pre­zen­tace po­řa­dím od­po­vídá pořadí stringů jako v ně­kte­rých sloup­co­vých da­ta­bá­zích.
  3. Tento případ lehce kom­pli­kuje fakt, že nevím kolik bajtů pre­fixu jsem použil a kolik tedy můžu bez­pečně pře­sko­čit, kdy­bych chtěl druhé kolo řazení pro­vést al­go­rit­mem za­lo­že­ném na ra­di­xech. Můžu určit jenom dolní mez.
  4. Tady by se hodilo mít nějaký Céč­ko­vi­tější jazyk nebo jazyk, který má structy. Pak bych mohl index na­hra­dit přímo poin­te­rem a ušet­řit si jeden cache-miss.
  5. Ale i když to nebude fun­go­vat ide­álně, LSD RS ne­za­bere tolik času a udělá aspoň ně­ja­kou dis­kri­mi­naci, která aspoň trochu urychlí ná­sle­du­jící řazení.
  6. Lo­gický další krok je použít stro­jové učení pro kon­strukci kom­presní funkce.
  7. Pro stringy se vy­platí zjiš­ťo­vat frek­vence sudých a li­chých bajtů zvlášť, pro­tože mají velice roz­dílné frek­vence.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články