Splay træer

Jeg sad og læste lidt om splay træer og bemærkede følgende:

http://en.wikipedia.org/wiki/Splay_tree skrev:

Possibility of creating a persistent data structure version of splay trees[...] and requires amortized O(log n) space per update.

Jeg har et par steder, hvor jeg har brug for sådan en persistent datastruktur. Men jeg synes at logaritmisk plads per opdatering er for meget. Hidtil har jeg brugt en linket liste, som (med mit brugsmønster) kan opnå konstant plads per opdatering, men som dog er langsom til opslag.

Jeg spekulerer på om der findes et bedre kompromis mellem pladsforbrug og tidsforbrug hvis jeg gerne vil beholde det konstante pladsforbrug og opnå et tidsforbrug der er bedre end lineært per operation.

#1

Som jeg læser den wiki artikel så et det lidt usædvanelige pladsforbrug kun hvis "allows access to both the previous and new versions after an update". Hvis du ikke har brug for den feature, så bør du kunne persistere i konstant space - artiklen siger også "Space O(n) O(n)" oppe i højre hjørne. Det forudsætter dog muligvis at det hele loades til memory og arbejde på der og så først gemmes til disk til sidst.

#2

Men hvis ikke det er in memory og gem til sidst, så skal der slet ikke bruges binært træ, så ....

Du kan evt overveje en splay-liste (et én-dimensionelt splay-træ). Hvis dit access-mønster ikke er uniformt, så får du amortiseret god access-tid og simpel persistering.

arne_v (2) skrev:

Som jeg læser den wiki artikel så et det lidt usædvanelige pladsforbrug kun hvis "allows access to both the previous and new versions after an update".

Det følger direkte fra definitionen af en persistent datastruktur.

arne_v (2) skrev:

Hvis du ikke har brug for den feature

Det har jeg. Mere præcist er det jeg har brug for følgende: Jeg har et array som løbende bliver opdateret. Dette array kunne sagtens fylde hele min RAM ud. Jeg gemmer på nuværende tidspunkt en log over alle ændringer af arrayet, som fortæller hvad der bliver skrevet i hver enkelt array indgang hvornår og hvorfor.

Nu har jeg brug for at kunne besvare spørgsmål om hvad der stod i en specifik array indgang på et givet tidspunkt.

Jeg kunne lave en binær søgning i min log for at finde det tidspunkt opslaget er interesseret i. Men derfra ville jeg så være nødt til at lave en lineær søgning baglæns indtil jeg finder den seneste opdatering af den pågældende arrayindgang.

Pally (4) skrev:

Du kan evt overveje en splay-liste

Jeg kender ikke den struktur og fik ingen relevante resultater, da jeg søgte efter det.

Et splay-træ er (i en vis forstand) 2 dimensionel. En splay-liste er en simpel liste (og i samme forstand) 1 dimensionel.

Splay mekanismen er, at et tilgået element forventes at blive tilgået igen 'snart'; ergo rykker man det længere frem i listen. Man kan enten rykke det helt forrest eller nøjes med at rykke det en enkelt position frem.

Givet et ikke-uniformt access-mønster, så vil de oftest tilgåede elementer over tid være at finde forrest i listen og derfor være meget effektive at tilgå. Worst case er naturligvis forfærdelig men pointen er den amortiserede effektivitet.

Fordelen ved en splay-liste er en utrolig simpel struktur og en ekstrem simpel splay mekanisme. Ulempen er, at den ikke giver mening for datamængder der fylder meget (det skal kunne rummes i en liste (evt af pointer)).

Det blev i min studietid nævnt som et muligt PhD emne. Effektiviteten var vist kun formodet og antydet heuristisk; intet konkret bevis. Hvad status rent teoretisk er ved jeg ikke.

kasperd (5) skrev:

Det følger direkte fra definitionen af en persistent datastruktur.

Ah.

En "persistent data structure" er ikke det samme som en "persistent" "data structure".

Pally (6) skrev:

Splay mekanismen er, at et tilgået element forventes at blive tilgået igen 'snart'; ergo rykker man det længere frem i listen. Man kan enten rykke det helt forrest eller nøjes med at rykke det en enkelt position frem.

Det er præcist den metode jeg har brugt indtil nu. Jeg har altid rykket elementet helt forrest. Det har den fordel, at det samtidigt giver mig mulighed for at vedligeholde en LRU cache, elementerne er netop linket i den rækkefølge de sidst er tilgået.

Men til søgning er det håbløst. Jeg ved ikke om real life brugsmønstre vil give gode eller dårlige resultater, for jeg har ikke nok real life data at analysere endnu. Men baseret på extrapolering af det begrænsede materiale jeg har vil den metode overhovedet ikke holde.

Der vil i praksis være tale om en meget lang liste, og når et element er blevet tilgået vil det sjældent blive tilgået igen inden for den nærmeste fremtid (fordi der ligger en cache et andet sted). Det vil i praksis sige at dengang jeg brugte strukturen som du beskrev havde jeg gennemsnitlig lineær adgangstid. Og pladsforbruget, hvis man laver en persistent variant vil typisk være proportional med tidsforbruget, så jeg forventer det vil komme til at bruge kvadratisk plads. (n opdateringer der skal bruge n plads hver).

arne_v (7) skrev:

En "persistent data structure" er ikke det samme som en "persistent" "data structure".

Nej, den terminologi er ikke den mest intuitive.

kasperd (5) skrev:

Jeg kunne lave en binær søgning i min log for at finde det tidspunkt opslaget er interesseret i. Men derfra ville jeg så være nødt til at lave en lineær søgning baglæns indtil jeg finder den seneste opdatering af den pågældende arrayindgang.

Medmindre du har et tree index paa arrayindegang for loggen.

kasperd (5) skrev:

Det har jeg. Mere præcist er det jeg har brug for følgende: Jeg har et array som løbende bliver opdateret. Dette array kunne sagtens fylde hele min RAM ud. Jeg gemmer på nuværende tidspunkt en log over alle ændringer af arrayet, som fortæller hvad der bliver skrevet i hver enkelt array indgang hvornår og hvorfor.

Hvor meget opdateres data. Er det 10% om året eller 50% om dagen eller?

Jeg har en ide til konstant plads per opdatering men hvor konstanten er lidt stor.

arne_v (9) skrev:

Medmindre du har et tree index paa arrayindegang for loggen.

Det jeg har gjort indtil videre er at jeg har et søgetræ til at indeksere den nyeste værdi i hver array indgang. Jeg har brug for at kunne finde ud af om en given værdi findes i arrayet lige nu, og i givet fald hvor.

Desuden har jeg brug for at kunne finde ud af hvad der har stået i en given array indgang på et givent tidspunkt. At finde ud af hvad der står i en given array indgang lige nu er nemt, så slår jeg bare op i arrayet. Historiske opslag har jeg ikke implementeret endnu.

arne_v (10) skrev:

Hvor meget opdateres data. Er det 10% om året eller 50% om dagen eller?

Mit overslag baseret på ekstrapolering siger at hver array indgang vil blive skrevet ca. 6-7 gange i døgnet men at de fleste vil overskrive med samme værdier som der stod før. Jeg rammer nok tæt på at i løbet af et døgn vil 50% af array indgangene blive ændret. Og jeg vil have brug for at kunne lave opslag i gamle værdier minimum 6 måneder tilbage uanset hvor mange gange den givne array indgang er blevet overskrevet.

Jeg kunne lave en fil med en blok med plads til f.eks. 256 opdateringer per array indgang, på den måde ville opslag være meget effektive, da jeg bare kunne indlæse den blok der relaterede til den array indgang jeg var interesseret i og lave en binær søgning i den indlæste blok. Til gengæld ville det betyde noget spildplads at allokere samme antal opdateringer til hver eneste array indgang, men endnu værre, ville det potentielt være meget ineffektivt at opdatere den pågældende fil.

Det ville betyde at mit indeks ikke længere ville være append-only, men det kunne jeg nok leve med.

arne_v (10) skrev:

Jeg har en ide til konstant plads per opdatering men hvor konstanten er lidt stor.

Hvis jeg ved hvor stor konstanten er, så kan jeg jo sammenligne med hvad logaritmisk plads ville koste. Jeg har en absolut øvre grænse på antal array indgange, så log(n) vil være mindre end 32.

Jeg tror ikke at min ide kan bruges i dit tilfælde. Der opdateres alt for meget,

Ideen er:
* pages af M bytes
* pages nummereret 0..
* N levels
* N-1 levels of index pages
* et level data page
* index page = M/sizeof(page number) page numbers
* data page = M/sizeof(element) data elementer
* on disk pages opdateres aldrig
* opdaterede pages skrives i enden af filen

Det tager N page reads at loade ethvert element.

Det tager N page writes at opdatere et enkelt element.

Det tager et sted mellem N og X*(N-1)+1 at opdatere X elementer.

Enhver opdatering resulterer i en ny root page.

Mapning fra opdaterings id/tidspunkt til root page nummer kræver en seperat løsning, men:
1) det er en overkommelig opgave
2) alle løsninger må have det problem

Hvis vi antager:
M = 16 KB
N = 3
sizeof(page number) = 8
sizof(elment) = 32
så kan en fil håndtere 2 milliarder elementer

Læsning af element koster 3 læsninger af 16 KB ialt 48 KB.

Opdatering af et enkelt element koster 3 læsningr af 16 KB ialt 48 KB.

Det er helt fint.

Problemet er at filen også vokser med 48 KB for hver enkelt opdatering.

Hvis man opdaterer 1% af elementerne enkeltvist, så får det filen til at vokse med 960 GB.

Hvis man opdaterer 1% af elementerne i bundter af X, så vil væksten være mindre. Præcist hvor meget mindre vil afhænge af mønstret.

N = 4 og M = 2 KB kan klare 1 milliard elementer og vil vokse med 8 KB per enkelt opdatering og 80 GB for 1% enkelt opdateringer.

50% om dagen for 6 måneder hænger ikke sammen medmindre i er villige til at bruge omkring 1 PB disk space.

Og der må være betydeligt bedre løsninger på problemet.

arne_v (12) skrev:

Og der må være betydeligt bedre løsninger på problemet.

Det må der. Din løsning er stadig logaritmisk. Det du beskriver er en mere eller mindre triviel persistenst version af et B-træ. Jeg kunne gøre det samme med et træ med fanout på blot 2. Et mindre fanout betyder mindre knuder, til gengæld vokser den konstante faktor på antal knuder. Med 2 milliarder elementer vokser antallet af interne knuder derfor til 31.

Hvis hver knude består af to pointere på 8 bytes, så fylder hver knude 16 bytes. Det giver 496 bytes til interne knuder. Desværre kan jeg nok ikke med den løsning holde mig indenfor 512 bytes, da bladet kommer til at fylde mere end 16 bytes.

Men de to pointere i hver knude er spild. Jeg ved at den ene af de to altid vil pege ind i samme opdatering. Og jeg ved hvor i opdateringen de forskellige niveauer lagres, så jeg ved faktisk præcist hvad værdien af den ene af de to pointere er. Jeg ved bare ikke hvilken af de to. Men hvis jeg gemmer et 32 bits index, der fortæller hvilken array indgang denne opdatering omhandler, så kan jeg regne ud om den pointer jeg kender er til højre eller til venstre.

Så kunne jeg nøjes med at gemme pointeren til den anden side. Hvis jeg samtidigt sparer lidt på størrelsen af pointerne og holder mig til 7 bytes, så kan jeg reducere I/O på bekostning af lidt mere CPU brug. Så ender jeg med at bruge 217 bytes på pointerne. Så har jeg 39 bytes til resten af oplysningerne om opdateringen, og kan have to opdateringer indenfor en 512 bytes blok.

Til sammenligning indeholder min log på nuværende tidspunkt typisk 240-344 bytes per opdatering. Men i princippet kan jeg skære det ned til 120 bytes på bekostning af nogle data, som rent teknisk ikke betyder noget, men som måske skal opbevares alligevel af juridiske årsager.

I sidste ende ender jeg nok på at det logaritmiske forbrug, jeg selv havde i tankerne, vil resultere i at mit indeks fylder omtrent det samme som loggen +/- en faktor to. Jeg havde håbet på et indeks, betydeligt mindre end loggen. Men det er måske ikke realistisk.

I mine overvejelser af problemet fandt jeg på en metode til at lave noget, der minder om binær søgning i en linket liste. Jeg har beskrevet det i detaljer, men jeg ved ikke om det hjælper mig ret meget tættere på en løsning.

Min tanke var at jeg kunne bruge en linket liste af alle opdateringer for en specifik array indgang og bruge den beskrevne algoritme til effektivt at søge i dem.

Men for at kunne gøre det skal jeg stadig kunne finde den nyeste opdatering for den ønskede array indgang. Og hvis jeg har en algoritme til at gøre dette givet de data jeg har tænkt mig at gemme, så kunne samme algoritme bruges til at finde den nyeste array indgang på ethvert givet tidspunkt, hvilket ville gøre ovennævnte linkede liste redundant.

Jeg fandt en artikel om persistens, som giver en løsning som jeg måske kan bruge til noget. Den ændrer godt nok på eksisterende knuder, så den vil skulle modificeres lidt for at leve helt op til mine ønsker.