funkcionálně.cz

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

YOLO tree

30. 9. 2016 — k47

Stará in­ter­ne­tová moud­rost říká „you only live once“. Život je příliš krátký na jis­toty a někdy to prostě musíme risk­nout. Jako třeba během kon­strukce bi­nár­ního vy­hle­dá­va­cího stromu (BST).

BST je super věc, všichni ho známe, mi­lu­jeme a na­pí­šeme si jeden nebo dva ještě před sní­daní. Ale i přesto má určité vlast­nosti, které, i když se zdají na­prosto sa­mo­zřejmé, nemusí zrovna být to, co by člověk chtěl. Kon­strukce BST je striktně sek­venční a nedá se (přímo1 ) naivně pa­ra­le­li­zo­vat. To zna­mená, že pokud chci nejmenší ele­ment nějaké sek­vence, musím nejdřív po­sta­vit celý BST v čase O(n log(n)) a teprve potom z něj vy­hmát­nout mi­ni­mum. V tom oka­mžiku je ale už pozdě, pro­tože jsem udělal všechnu práci nutnou k se­řa­zení sek­vence. V ide­ál­ním pří­padě bych udělal jen ne­zbytně nutné množ­ství práce a kon­strukci zbytku bych líně od­lo­žil na poz­ději.

Na­proti tomu je quicksort (QS) nebo radix sort (RS) před­sta­vuje po­ten­ci­álně líné al­go­ritmy. Když chci n-tý nejmenší prvek, tak si ho v jed­no­duše quick­se­lectnu a cestou udělám li­ne­ární množ­ství práce vstříc plně se­řa­ze­nému stupu. Stejně tak jsou všechny QS/RS naivně pa­ra­le­li­zo­va­telé. Jako všechny al­go­ritmy, které vstup re­kur­zivně roz­dělí a pak jed­not­livé části ne­zá­visle zpra­co­vá­vají, se u nich dá tri­vi­álně do­sáh­nout lo­ga­rit­mic­kého pa­ra­lel­ního zrych­lení.

BST se od QS/RS od­li­šuje tím, že vý­sled­kem není jen se­řa­zená sek­vence, ale dy­na­mická datová struk­tura, do které můžu při­dá­vat nebo z ní ode­bí­rat prvky.

Když chci to nej­lepší z obou světů, musím na to jít jako Abe a Aaron z Pri­meru:

They took from their surroun­dings what was needed and made of it so­me­thing more.

Re­i­fi­kací quicksortu můžu dostat BST, který je dy­na­mický a vy­vá­žený a jeho kon­strukce je líná a naivně pa­ra­le­li­zo­va­telná.

Jako při každé re­i­fi­kaci začnu s ne­hmot­ným pro­ce­sem a zhmot­ním ho do datové struk­tury. Když v QS vy­bí­rám pivot, re­i­fi­kuji ho jako uzel stromu s tím, že všechny menší prvky při­jdou doleva a ty větší do­prava. Takhle po­stu­puji re­kur­zivně k listům a, když si to moje srdce žádá, strom prů­běžně vy­va­žuji.

Strom je tvořen dvěma druhy uzlů – ne­re­a­li­zo­va­nými a re­a­li­zo­va­nými. Ty ne­re­a­li­zo­vané jsou jed­no­du­ché se­znamy prvků, re­a­li­zo­vané uzly jsou pak tvo­řeny pi­vo­tem a dvěma pod­stromy.

Začnu s ne­re­a­li­zo­va­ným se­zna­mem:

[6, 8, 3, 1, 4, 2, 9, 5, 0, 7]

Vyberu pivot, udělám z něj jeden re­a­li­zo­vaný uzel, roz­dě­lím seznam na dva ne­re­a­li­zo­vané se­znamy a ty strčím jako pod­stromy. V tomto pří­padě výběr pro­bíhá v Ho­a­rově stylu první dobrá, ale je možné použít i kom­pli­ko­va­nější metody jako best-of-3 nebo quasi best-of-9.

                   (6)
                  /   \
[3, 1, 4, 2, 5, 0]     [8, 9, 7]

(Ne­re­a­li­zo­vané se­znamy uvádím vždy v hra­na­tých zá­vor­kách. Do ku­la­tých píšu pivot re­a­li­zo­va­ného uzlu.)

Takhle můžu po­kra­čo­vat, dokud budu chtít. Můžu třeba re­a­li­zo­vat jen cestu k nejmen­šímu prvku v prů­měr­ném li­ne­ár­ním čase:

                (6)
               /   \
            (3)     [8, 9, 7]
           /   \
        (1)     [4, 5]
       /   \
    (0)     [2]

Jak je vidět, velká část stromu vůbec nebyla vy­hod­no­cena.

Stejně tak můžu strom po­sta­vit na­jed­nou (pod­stromy můžu po­ten­ci­álně stavět pa­ra­lelně) re­kur­zivní apli­kací tohoto pra­vi­dla.

Tato QS in­spi­ro­vaná kon­strukce je úzce spjatá s BST. Knuth o tom psal v The Art of Com­pu­ter Pro­gra­m­ming: Když jako pivot po­u­ží­vám vždycky první ele­ment, je vý­sledný strom stejný jako když stavím bi­nární strom bez vy­va­žo­vání. Ve vý­sledku pro­vedu stejná po­rov­nání, jen v jiném pořadí.

Pokud strom ne­spl­ňuje moje po­ža­davky na vy­vá­že­nost, můžu ho prů­běžně ba­lan­co­vat.

V mém pří­padě může být levý pod­strom příliš velký:

                   (6)
                  /   \
[3, 1, 4, 2, 5, 0]     [8, 9, 7]

Rotace si v tomto pří­padě vynutí čás­teč­nou re­a­li­zaci pod­stromu.

              (6)
             /   \
          (3)     [8, 9, 7]
         /   \
[1, 0, 2]     (4)
                 \
                  [5]

Po rotaci to bude vy­pa­dat takhle:

              (4)
             /   \
          (3)     (6)
         /       /   \
[1, 0, 2]     [5]     [8, 9, 7]

Musel jsem re­a­li­zo­vat jednu úroveň stromu. Tento proces může po­kra­čo­vat re­kur­zivně až k listům v prů­měr­ném li­ne­ár­ním čase (a quicksor­tov­ské O(n^2) v nej­hor­ším pří­padě).

K vy­va­žo­vání se nehodí tech­niky z red-black nebo AVL stromů. Ty po­tře­bují ozna­čit každý uzel (buď barvou nebo hloub­kou) a to nutně vede k re­a­li­zaci celého pod­stromu.

Když jsem o tom pře­mýš­lel, ně­ja­kou dobu jsem ne­vě­děl, jak tenhle pro­blém vy­ře­šit. Pak jsem ale v paperu Im­ple­men­ting sets ef­fi­ci­ently in a functi­o­nal lan­gu­age na­ra­zil na size ba­lan­ced trees – tedy stromy vy­va­žo­vané podle ve­li­kosti. Ve­li­kost pod­stromu je lo­kální vlast­nost, kterou znám ne­hledě na to, zdali je pod­strom re­a­li­zo­vaný nebo ne. Ba­lan­co­vání začne jen, když je jeden pod­strom k-krát větší než ten druhý.

Vy­va­žo­vání ale v prin­cipu nemusí být nutné, pro­tože když vy­bí­rám pivot ná­hodně, v prů­měr­ném pří­padě je vý­sledný strom vy­ba­lan­co­vaný s prů­měr­nou hloub­kou 1.386 log(n). Takže místo ba­lan­co­vání bych mohl jen ran­do­mi­zo­vat pořadí vstupu.

Quicksort styl kon­strukce vede k le­nosti. Teď jak na dy­na­mické vlast­nosti? Chci mít mož­nost do stromu při­dá­vat a ode­bí­rat prvky a za­cho­vat při tom jeho lenost a asymptoty.

Vklá­dání je tri­vi­ální. Místo toho, aby byl uzel buď re­a­li­zo­vaný nebo ne, může být re­a­li­zo­vaný se seznam ne­re­a­li­zo­va­ných změn.

Když na­pří­klad do to­ho­hle stromu

                (6)
               /   \
            (3)     [8, 9, 7]
           /   \
        (1)     [4, 5]
       /   \
    (0)     [2]

vložím [ 1.47 4.7 47 ], do­stanu

                (6)-[1.47, 4.7, 47]
               /   \
            (3)     [8, 9, 7]
           /   \
        (1)     [4, 5]
       /   \
    (0)     [2]

Když budu opět chtít získat mi­ni­mum, všechny ne­re­a­li­zo­vané se­znamy, na které na­ra­zím cestou, zre­a­li­zuji:

                (6)
               /   \
            (3)     [8, 9, 7, 47]
           /   \
        (1)     [4, 5, 4.7]
       /   \
    (0)     [2, 1.47]

V tomto pří­padě jsem jen při­dá­val na konec ne­re­a­li­zo­va­ných se­znamů.

Mazání můžu vy­ře­šit dvěma způ­soby. Buď striktně nebo líně. Striktní va­ri­anta najde mazaný prvek ve stromu a hned ho od­straní. Cestou nutně re­a­li­zuje všechny uzly (to by mělo být v nej­hor­ším pří­padě O(n) práce). Líná va­ri­anta do ne­re­a­li­zo­va­ného se­znamu jen přidá tomb­stone. Když se tento objekt even­tu­álně do­stane do listu, od­staní daný ele­ment. Tohle řešení je líné, ale zase může vést k hro­ma­dění tomb­stone ob­jektů v nikdy ne­re­a­li­zo­va­ných čás­tech stromu. To se dá vy­ře­šit tak, že každý pod­strom nejen sle­duje svou ve­li­kost, ale také počet ná­hrobků.

A to by bylo všechno.


Do tohoto bodu jsem se dostal jenom tak, že jsem pře­mýš­lel, kam až se dá vý­chozí myš­lenka do­táh­nout. Pak jsem si ale na­jed­nou uvě­do­mil, že jsem už něco po­dob­ného viděl.

Frak­tální stromy, po­u­ží­vané v TokuDB, mají velice po­dob­nou struk­turu. Druhá verze frak­tál­ních stromů jsou B-stromy, kde je ke kaž­dému vnitř­nímu uzlu při­pnutý buffer aku­mu­lu­jící změny. Ty jsou even­tu­álně (např. když se buffer naplní), pro­pa­go­vány o úroveň níž do bu­f­ferů v pří­sluš­ných uzlech nebo přímo do listů s da­to­vými po­lož­kami.

Frak­tální stromy jsou po­dobné mým YOLO stro­mům, i když k této podobě došly z jiného úhlu. TokuDB se sna­žilo omezit ná­hodné IO ope­race a na­hra­dit je sek­venč­ním zá­pi­sem. Když se buffer naplní, jeho čtení a zápis do niž­ších úrovní je striktně sek­venční. Já jsem se v pří­padě YOLO stromů za­jí­mal jen o líné zpra­co­vání a sle­do­val ho až do ex­trému. V obou pří­pa­dech to došlo k po­dob­ným zá­vě­rům.

Pokud jsou tedy YOLO/frak­tal tree re­i­fi­ka­cemi quicksortu (resp. multi-way quicksortu), musí exis­to­vat po­dobná kon­strukce, která re­i­fi­kuje merge sort. Ta sku­tečně exis­tuje a co víc – po­u­žívá se ve světě da­ta­bází.

Jde o LSMT – Log Structu­red Merge Trees v kom­bi­naci s tzv. fracti­o­nal cas­ca­sing – re­i­fi­ko­vaný merge sort, který je líný a má ty správné asymptoty jako na­pří­klad O(log(n)) hle­dání.

Shodou náhod na LSMT byla za­lo­žena první verze frak­tál­ních stromů z TokuDB.


Dále k tématu:


  1. Můžu pa­ra­lelně po­sta­vit ně­ko­lik BST a pak je naivně slou­čit s ma­xi­málně lo­ga­rit­mic­kým zrych­le­ním.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články