Szevasztok!
Lenne egy elméleti kérdésem: olyan adatszerkezet kellene nekem, amire igaz:
* rendezett
* log2(n) beszúrás
* log2(n) keresés
* ha megvan egy elem, akkor konstans időben el tudom érni az előtte és utána levőt
Szerintetek mi lenne a legjobb? Skip list? Vagy valamilyen fa struktúra?
- 4752 megtekintés
Hozzászólások
Én egy olyan kiegyensúlyozott fát (pl. piros-fekete) fa képzelek el erre megoldásként, melynek csúcsai láncolt listát alkotnak (tehát minden csúcs tartalmaz egy értéket és egy mutatót a növekvő sorrendben következő csúcsra és egy mutatót a növekvő sorrendben előző csúcsra).
Lehet, hogy van egyszerűbb megoldás is.
- A hozzászóláshoz be kell jelentkezni
milyen az a piros-fekete fa?
- A hozzászóláshoz be kell jelentkezni
- A hozzászóláshoz be kell jelentkezni
A csúcsok külön láncolására nincs szükség; a rendezőfa (keresőfa) amúgy is a kulcs szerint rendezetten tárolja (vagy linkeli) az elemeket, a bejárás pedig történhet iteratívan is, nem kell feltétlenül rekurzió. Vagyis lehet "iterátor objektumod", amelyet akkor léptetsz előre vagy hátra, amikor akarsz. Jobb esetben az iterátor objektum csak akkor válik érvénytelenné, ha pont azt az elemet törlöd a fából, amelyikre mutat (akár kulcs (vagyis keresés) alapján, akár magán az iterátoron keresztül).
Azt nem feltétlenül lehet kijelenteni, hogy minden egyes léptetés O(1)-be kerülne, de azt igen, hogy a teljes (rendezett) bejárás O(n) műveletigényű.
(... Mindjárt kifejti valaki, hogy a fák rosszak, mert a bejárásuk össze-vissza ugrál a memóriában, és kinyírja a cache-t. Például.)
- A hozzászóláshoz be kell jelentkezni
Ebben az esetben a bejárás nem túl fontos. Kicsit pontosítok miről lenne szó: Az egyes elemek egy adathalmaz különböző szegmenseit reprezentálnák. Ha beérkezett egy új szegmens, akkor azt elhelyezi a struktúrában, és megnézi, hogy az előtte vagy az utána következő szegmenssel folytonos adatsort alkot-e. Ha igen, akkor "összeolvasztja" a kettőt.
- A hozzászóláshoz be kell jelentkezni
Ha az intervallumok páronként diszjunktak, valamint mondjuk balról zártak, jobbról nyíltak, továbbá az uniójúk kiadja a teljes (jobbról nyílt) "szakaszt", akkor szerintem simán használhatsz erre bármilyen bináris fát.
Eszembe jutott az intervallumfa, de ott is aszondja, hogy In a simple case, the intervals do not overlap and they can be inserted into a simple binary tree and queried in O(log n) time.
Beszúrod O(log n) időben. (Mivel nincs átfedés, azért az intervallum minimumát lehet kulcsnak használni.) Ha pontosan ez az intervallum már szerepelt, akkor visszakapod az ütköző intervallumra mutató tree node-ot, és hibát jelezhetsz. Ha sikerült beszúrni, akkor visszakapod azt az iterátort, ahova bekerült. Erre mondasz egy prev-et. Ha összeolvaszthatók, akkor a két forrást törlöd, és beszúrod az összeolvasztottat. Ezután megcsinálod ugyanezt next-tel is.
Mire kell egyébként az egész? Ha csak arra van szükséged, hogy véletlenszerű sorrendben érkező szakaszokat újrarendezve írj ki, akkor nem kell összeolvasztani. Ez lényegében egy (páronként eltérő kulcsokat alkalmazó) prioritásos sor, amiből lyukmentesen akarsz elemeket kivenni. Ekkor:
Ha korlátlan a buffer, akkor egy sima heap is elég (bár az rbtree is megfelelő): beszúrod, ami jött, aztán megpróbálsz a fa/kupac elejéről addig olvasni, amíg nem tapasztalsz lyukat. Van egy külön változód, amiben tárolod, hogy a kiírás folytatásához milyen intervallumnak kell megérkeznie. Ezt a fa/kupac ürítésekor lépteted, és ezzel veszed észre a lyukat, illetve ezzel veszed észre, ha megszűnt a lyuk a sor elején.
Ha korlátos a buffer (előre tudod, legfeljebb mennyit buffer-elsz fel lyuk esetén), akkor elég egy sima tömb (ring buffer), aminek mindene O(1). Mindig tudod, a teljes szekvenciában mit képes lefedni a ring buffer. Ha ezen túleső intervallum érkezik, eldobod, ha beleesik, O(1) alatt elhelyezed.
- A hozzászóláshoz be kell jelentkezni
Feltételezhető, hogy nem lesz átfedés. Kösz a linket, ez az intervallumfa elég érdekes. Amúgy egy torrent kliensen dolgozom, és a disk cahce megvalósításához kell. Ugyanis a kliens átlag 16kB méretű blokkokban kapja a fájlok darabjait, és a legtöbb kliens ezért használja ezt a disk cache technikát, aminek az a lényege, hogy a beérkezett blokkokat csak akkor írja lemezre, amikor nagyobb összefüggő adathalmazt tud kiírni. Ez növeli a teljesítményt és a lemeztöredezettségre is jó hatással van.
- A hozzászóláshoz be kell jelentkezni
Én is a piros-fekete fa és a skip list között vacillálok.
- A hozzászóláshoz be kell jelentkezni
Self-balancing binary search tree
In the asymptotic ("Big-O") sense, a self-balancing BST structure containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time, and ordered enumeration of all items in O(n) time. For some implementations these are per-operation time bounds, while for others they are amortized bounds over a sequence of operations.
Implementáció dögivel van, én is írtam magamnak egyet (kiveheted pl. az lbzip2-ből), de ha valami nehézsúlyúra vágysz, akkor lásd Ben Pfaff GNU libavl-jét.
- A hozzászóláshoz be kell jelentkezni
http://avl-array.sourceforge.net/avl_array/overview.html
Log(N) indexeles, Log(N) beszuras. Eleg jo.
----------------------
while (!sleep) sheep++;
- A hozzászóláshoz be kell jelentkezni