Binary tree el. lignende?

[terjeelde]

Hei,

 

Jeg er på jakt etter noe ala dict, men som raskt kan:

 

* sette inn key/value

* slette key

* finne minste key

 

Noen som har gode forslag?

[zotbar1234]

Jeg er på jakt etter noe ala dict, men som raskt kan:

 

* sette inn key/value

* slette key

* finne minste key

 

Noen som har gode forslag?

 

En dict + en "min_key". Noe av problemet er at det er *vanskelig* å gjøre det bedre enn dict hastighets- og minnemessig. Jeg hadde et lite prosjekt der jeg skrev skiplist i C og limte den inn i CPython vha. C-API-et. Jeg vant på minnebruken for noen datastrukturer og tapte for andre (jeg kunne ha vunnet på minne for nesten alle med en custom allocator for level-1 noder i skiplisten). Men jeg vant aldri på tiden for noenlunde realistiske mengder.

 

Arve fra dict og overstyre de metodene som er interessante. O(1) minste element, insertion og deletion. O(K*n) minnebruk, der K = 2 for "små" dict-er, og K = 1.5 for "store" dict-er. Minimalt med innsats og holder til prototypen og vel så det.

 

Alternativ 2 er å bruke heapq. Logaritmisk insertion/deletion, O(1) minste element. O(n) minnebruk. Må se det an.

 

Alternativ 3 er å skrive egen skiplist. Mye arbeid, tvilsom gevinst. Logaritmisk insertion/deletion, O(1) for minste element. O(K*n) minnebruk, for en passende konstant K (eh... gud bedre, 4/3 for p = 0.25).

 

Binært tre blir fort for dyrt plassmessig (og iallfall hvis du skal lage det i python for store datamengder).

Endret 8. desember 2008 av zotbar1234

[terjeelde]

Arve fra dict og overstyre de metodene som er interessante. O(1) minste element, insertion og deletion. O(K*n) minnebruk, der K = 2 for "små" dict-er, og K = 1.5 for "store" dict-er. Minimalt med innsats og holder til prototypen og vel så det.

 

Litt usikker på hvordan du ser for deg å overstyre de forskjellige?

 

For å finne minste f.eks, så ville det vært lett nok å overstyre __setitem__, slik at jeg har en lokal attributt 'min', og hvor hvert nye element som settes inn sjekker om det nye elementet er mindre, og isåfall oppdaterer lokal attributt.

 

Problemet er dersom denne keyen slettes. Da må den som nå er minst finnes med tablescan, med mindre jeg holder styr på order på noe vis.

 

Alternativ 2 er å bruke heapq. Logaritmisk insertion/deletion, O(1) minste element. O(n) minnebruk. Må se det an.

 

Heapq virker å kunne være en morsom løsning. Tenkte egentig i retning av noe som spiser key/value, men ved nærmere ettertanke er det vel ingenting i veien for å bare stappe dette i en klasse, og skrive custom compares-saker. Kanskje ikke esktremt effektivt, men burde ihvertfall gjøre nytten til prototyping.

 

Alternativ 3 er å skrive egen skiplist. Mye arbeid, tvilsom gevinst. Logaritmisk insertion/deletion, O(1) for minste element. O(K*n) minnebruk, for en passende konstant K (eh... gud bedre, 4/3 for p = 0.25).

 

Binært tre blir fort for dyrt plassmessig (og iallfall hvis du skal lage det i python for store datamengder).

 

Lurt litt på å ta utgangspunkt i red-black-tree, og modifisere litt for å ha "dobbel root". En vanlig red-black-tree-root, men også holde styr på minste element. Burde gi O(1) for minste element, O(log N) for arbitrær insert/delete, og O(1) for å slette minste element.

 

Kan jo forsåvidt komplimentere det med en hash for å slå noder opp direkte, og gjøre arbitrær insert/delete O(1) også, men koster jo en del minne og knot.

 

Takk for inputen. Tror jeg lander på å bruke heapq i første omgang, og så evt. gjøre noe mer fancy med en Python extension senere.

[zotbar1234]

Problemet er dersom denne keyen slettes. Da må den som nå er minst finnes med tablescan, med mindre

jeg holder styr på order på noe vis.

 

Jeg sovnet visst litt i timen og så flere ganger

 

Ja, man vil måtte ha 2 strukturer ved siden av hverandre bak dict sitt grensesnitt:

 

* En vanlig dict

* En sortert liste (vel, array, egentlig)

 

Listen tar vare på nøklene. Logaritmisk insertion/deletion.

 

Når det gjelder heapq, så hjelper jo den ikke å finne et vilkårlig nøkkel (skjønner ikke hva jeg tenkte på). Så jeg tror faktisk at heapq + dict vil være den enkleste kombinasjonen som burde gi en ok prototype -- O(1) oppslag, O(logN) insertion/deletion, O(1) for å finne minste element.

 

Lurt litt på å ta utgangspunkt i red-black-tree, og modifisere litt for å ha "dobbel root". En vanlig red-black-tree-root, men også holde styr på minste element. Burde gi O(1) for minste element, O(log N) for arbitrær insert/delete, og O(1) for å slette minste element.

 

Vil ikke du måtte rebalansere treet dersom du sletter det minste elementet?

 

Hvilke operasjoner dominerer egentlig?

[terjeelde]

Når det gjelder heapq, så hjelper jo den ikke å finne et vilkårlig nøkkel (skjønner ikke hva jeg tenkte på). Så jeg tror faktisk at heapq + dict vil være den enkleste kombinasjonen som burde gi en ok prototype -- O(1) oppslag, O(logN) insertion/deletion, O(1) for å finne minste element.

 

Mulig du har rett, men er ikke helt sikker.

 

Inserts er greie. Stappe inn i dict og heapq.

 

Finne minste element er greit takker være heapq.

 

Finne og slette minste element er greit. Finn med heapq, slett fra dict.

 

Men å finne og slette arbitrært element kan være værre. Greit fra dict, men kommer tilbake til at jeg må fjerne arbitrært element fra heapq, med mindre jeg på noe vis kan bruke dict for å holde styr på hvor i heapq listen det er, og fjerne på den måten.

 

Vil ikke du måtte rebalansere treet dersom du sletter det minste elementet?

 

Jo, men mener å huske rebalansering av red-black trær trenger maks 3 rotasjoner, så fortsatt O(1), siden jeg vet hvor elementet er, og ikke trenger å slå det opp.

 

Hvilke operasjoner dominerer egentlig?

 

Vet ikke helt enda.

 

Tanken er å bruke det for timere. Enten det er "dette skal gjøres om en halvtime", eller å bruke det til retransmit-timere for forskjellige UDP protokoller (DNS, SIP osv).

 

Jeg mistenker retransmit-timere er det som bør være hovedfokus, siden dette blir en del av inner-event-loop.

 

For f.eks SIP blir det satt en timer for hver enkelt request som sendes (evt. forwardes). Da spørs det om svar er mottatt innen timeren fyrer. Hvis svar blir mottatt, så slettes timeren uten å fyre.

 

I tillegg vil hver select() / kevent() / epoll() sjekke når neste timer er, for å vite hvor lenge den skal blokke. Når kallet unblockes fetches (, kjøres) og slettes minste element, frem til neste er i fremtiden.

 

Kan vel i teorien bruke en hash for å peke til alle elementer, og på den måten også gjøre deletes av arbitrære elementer O(1), men mistenker det ikke er verdt det.

[zotbar1234]

Men å finne og slette arbitrært element kan være værre. Greit fra dict, men kommer tilbake til at jeg må fjerne arbitrært element fra heapq, med mindre jeg på noe vis kan bruke dict for å holde styr på hvor i heapq listen det er, og fjerne på den måten.

 

Man kan evt. la verdiene i dict-en var par, der det ene elementet i paret peker tilbake til heapen (slik at man kan finne hvilken indeks en tilfeldig nøkkel ligger i i heapen.

 

Det til side... dette var en såpass morsom oppgave at jeg har begynt å eksperimentere litt med forskjellige implementasjoner.

 

For *små* datasett og *få* min_key() forespørsler, duger en helt vanlig dict med en slik min_key:

 

	def min_key(self):
	if len(self) == 0:
		raise KeyError("No minimum key (empty mapping)")
	return min(self)

 

*Veldig* enkelt, men *veldig* ubrukelig hvis du har mange min_key forespørsler.

 

En interessant oppdagelse jeg har gjort underveis er at skal du lage et RB-tre som skal konkurrere med dict, vil du nok være pent nødt til å skrive den i C. Selv med psyco er det en gigantisk forskjell mellom et RB-tre (skrevet i python) vs. en dict/skiplist skrevet i C (og limt til python).

 

(...)

Kan vel i teorien bruke en hash for å peke til alle elementer, og på den måten også gjøre deletes av arbitrære elementer O(1), men mistenker det ikke er verdt det.

 

Jeg skal pusle litt mer med dette (finner du en RB-tre-i-C-til-python implementasjon, si i fra). Si i fra dersom du vil ha koden (pm er antageligvis enklest)

Endret 15. desember 2008 av zotbar1234

[terjeelde]

Man kan evt. la verdiene i dict-en var par, der det ene elementet i paret peker tilbake til heapen (slik at man kan finne hvilken indeks en tilfeldig nøkkel ligger i i heapen.

 

Vet ikke helt om det går. Heap-indexene vil jo forflytte seg og bli feil når man setter inn/sletter?

 

Det til side... dette var en såpass morsom oppgave at jeg har begynt å eksperimentere litt med forskjellige implementasjoner.

 

For *små* datasett og *få* min_key() forespørsler, duger en helt vanlig dict med en slik min_key:

 

	def min_key(self):
	if len(self) == 0:
		raise KeyError("No minimum key (empty mapping)")
	return min(self)

 

*Veldig* enkelt, men *veldig* ubrukelig hvis du har mange min_key forespørsler.

 

Grei løsning for prototyping ihvertflal.

 

En interessant oppdagelse jeg har gjort underveis er at skal du lage et RB-tre som skal konkurrere med dict, vil du nok være pent nødt til å skrive den i C. Selv med psyco er det en gigantisk forskjell mellom et RB-tre (skrevet i python) vs. en dict/skiplist skrevet i C (og limt til python).

 

Tanken min var å kode for hånd, eller evt. delvis bruke Cython (fork av pyrex).

 

Som basis for det hele tenkte jeg å bruke red-black-tree koden som er i f.eks FreeBSD og DragonflyBSD:

tree.h

 

Men da evt. utvide for å se om jeg kan gjøre min til O(1).

 

Tanken jeg lurer på er å gjøre slik at jeg lagrer key også "i C modus", slik at compares ikke går mot Python objekter, men "native C objekter", for å gjøre tree traversal raskere osv.

 

Jeg skal pusle litt mer med dette (finner du en RB-tre-i-C-til-python implementasjon, si i fra). Si i fra dersom du vil ha koden (pm er antageligvis enklest)

 

Vil gjerne ha kode hvis du leker deg.

 

Det er noe Python rb-tree-kode her:

 

http://cheeseshop.python.org/pypi/rbtree/

 

Men virker ikke å være maintainet eller dokumentert, ei heller å compile opp greit, så er litt skeptisk.

 

Terje

[zotbar1234]

Man kan evt. la verdiene i dict-en var par, der det ene elementet i paret peker tilbake til heapen (slik at man kan finne hvilken indeks en tilfeldig nøkkel ligger i i heapen.

 

Vet ikke helt om det går. Heap-indexene vil jo forflytte seg og bli feil når man setter inn/sletter?

 

Korrekt. Da vil man måtte fikse på alle nøklene i dict-en som berøres av heap-operasjonene. Det kan tenkes det er veldig pes. Men dict er *veldig* optimalisert, så det å basere en datastruktur på den er ikke nødvendigvis dumt.

 

Tanken min var å kode for hånd, eller evt. delvis bruke Cython (fork av pyrex).

 

Som basis for det hele tenkte jeg å bruke red-black-tree koden som er i f.eks FreeBSD og DragonflyBSD:

tree.h

 

Problemet er vel at ganske mye av limkoden vil måtte spesialskrives (du *vil* implementere hele dict-grensesnittet for RB-treet ditt, slik at du slipper overraskelser).

 

Tanken jeg lurer på er å gjøre slik at jeg lagrer key også "i C modus", slik at compares ikke går mot Python objekter, men "native C objekter", for å gjøre tree traversal raskere osv.

 

Hvis RB-treet ditt skal være generelt (noe jeg anbefaler på det sterkeste, enda du kanskje per i dag sitter bare med heltallsnøkler), så bør du nok la C-koden ta i mot en funksjonspeker for å sammenligne nodene. *Det* i sin tur sparer deg for mange overraskelser når deler av implementasjonen endres på Pythonsiden underveis.

 

Det er noe Python rb-tree-kode her:

 

http://cheeseshop.python.org/pypi/rbtree/

 

Men virker ikke å være maintainet eller dokumentert, ei heller å compile opp greit, så er litt skeptisk.

 

Vi får se. Da har jeg noe mer å leke med i kveld. Såsnart jeg har laget noen gnuplotgrafer med testene, kommer koden.

[terjeelde]

Hvis RB-treet ditt skal være generelt (noe jeg anbefaler på det sterkeste, enda du kanskje per i dag sitter bare med heltallsnøkler), så bør du nok la C-koden ta i mot en funksjonspeker for å sammenligne nodene. *Det* i sin tur sparer deg for mange overraskelser når deler av implementasjonen endres på Pythonsiden underveis.

 

Mistenker det enkleste er å bruke C callbacks.

 

For ett hvert tre registreres en C callback som blir kaldt for å gjøre node-compare, hvor denne C callbacken evt. kan kalle videre til Python-kode. På den måten kan man enten gjøre det i C for situasjoner hvor man vil ha best mulig ytelse, eller i Python det er der godt nok.

[zotbar1234]

Vil gjerne ha kode hvis du leker deg.

 

Sånn, da begynner det å bli noen resultater (ikke helt ferdig med LaTeX-dokumentet som beskriver mine funn enda, men tenkte jeg skulle gi lyd fra meg).

 

Jeg har testet 4 implementasjoner -- en skiplist skrevet i C (jeg hadde en liggende ), et RB-tre skrevet i C (basert på libavl til Ben Pfaff), et RB-tre skrevet i Python (fant på det store internett) og en naiv og dum dict med min_key, slik jeg foreslo tidligere.

 

Test 1: stappe inn 5'000 par på formen (x, None) der x er et tilfeldig tall:

 

skiplist: 0.122s

C rb-tre: 0.090s

Python rb-tre: 4.03s (!)

dum dict: 0.018s

 

Uten tvil kan dict dette med å sette verdier inn i datastrukturen.

 

Test 2: stappe inn 5'000 par på formen (x, None) der x er et tilfeldig tall, og spør etter min_key() for hver 10. insertion:

 

skiplist: 0.129s (denne er i praksis gratis)

C rb-tre: 0.103s (ikke helt gratis, men 0.1*log(5000) er fortsatt billig)

Python rb-tre: 4.121s

dum dict: 0.069s (nesten 4x dyrere)

 

Test 3: Akkurat som test 2, men denne gangen spør vi etter min_key() etter *hver* insertion:

 

skiplist: 0.125s (10% eller 100% har lite å si i dette tilfellet)

C rb-tre: 0.139 (fra å være raskere enn skiplist er vi gått til å være tregere)

Python rb-tre: 6.368s

dum dict: 27.523

 

Moralen -- dict kan være rask, den, men suger algoritmen, så hjelper det ikke at implementasjonen er rask. Dette er bare for 5'000 par, vel å merke.

 

Test 4: Akkurat som test 2, men denne gangen spør vi etter min_key() etter hver 4. insertion:

 

skiplist: 0.133s

C rb-tre: 0.097s

Python rb-tre: 4.065s

dum dict: 0.155s

 

Testen var egentlig bare et første steg til å finne break-even point når det gjelder min_key() forespørsler.

 

Test 5: Stappe inn 5'000 par på formen (x, None) der x er et tilfeldig tall, og etter alle insertions fjern hvert 7. par. Dette er for å teste for bra dårlig insert + delete er tilsammen

 

C skiplist: 0.141

C rb-tre: 0.101

Python rb-tre: 4.086s

dum dict: 0.025s

 

Konklusjonen er at har man garantert få min-operasjoner eller få (key, value)-par, er dict med den min-funksjonen slik foreslått helt suveren. Har man mange par (mange vil være avhengig av platformen man kjører dette på) eller middels med par og mange min_key()-forespørsler, så bør man gå for en skiplist eller et rb-tre (vel å merke, jeg har ikke spesialtilpasset min_key() i rb-trærne på noen spesielle måter. Hver min_key() er log(N) (gå mot venstre fra roten så lenge det er noder)).

 

Det er noe Python rb-tree-kode her:

 

http://cheeseshop.python.org/pypi/rbtree/

 

Men virker ikke å være maintainet eller dokumentert, ei heller å compile opp greit, så er litt skeptisk.

 

Ja, gitt, det var veldig vanskelig å finne et RB-tre implementert i C som samtidig hadde MutableMapping-grensesnittet til Python implementert Jeg endte opp med å stjele koden fra libavl og skrive de mest kritiske (for testen) mappingene selv.

[teflonpanne]

En datastruktur hvor man skal sette inn ting, slette ting og finne minste element pleier man vel gjerne å kalle prioritetskø. Hvordan man implementerer det kommer litt an på forholdet mellom de ovennevnte operasjoner.

[zotbar1234]

En datastruktur hvor man skal sette inn ting, slette ting og finne minste element pleier man vel gjerne å kalle prioritetskø. Hvordan man implementerer det kommer litt an på forholdet mellom de ovennevnte operasjoner.

 

Jeg tolket det opprinnelige innlegget dithen at tilgang til en tilfeldig nøkkel/verdi-par var et krav. Prioritetskøer støtter ikke denne operasjonen.