XCHAOS: Hele, ja nejak nevidim zadnej conclusion z toho bodu (3). Mas teda kus spojaku, kterej je obarvenej.. co z toho plyne, nebo k cemu ta barva bude?

XCHAOS: A hlavne v defaultni konfiguraci glibc malloc pouziva mmap az pro bloky od 128k vejs, takze u tech mensich mas smulu bez ohledu na architekturu.

ANT_39: ano, v předchozím jsem úplně zapomněl na 0) existence nějakého klíče, podle které má smysl ty uzly uspořádat.

(pochopitelně, jako obecný kontejner, u kterého nezáleží na pořadí, je to nesmysl - tam stačí pole nebo jednoduchý spojový seznam)

REDGUY: ...a rozhodně jen pro některé architektury, ano. prostě občas ty stránky přeskládat lze, občas ne.

třeba u mě by se to částečně tlouklo s tou "kontextovou správou paměti": ne úplně, pravda, ale je to jeden z důvodů, proč jsem se na to zatím nadšeně nevrhnul.

ISTEVE: je to prostě "spojový seznam + něco navíc". co třeba takhle:

1) všechny uzly (vrcholy grafu) jsou spojené orientovanými hranami tak, že je lze jednoznačně procházet jako nezacyklený, spojový seznam - máme právě jeden "vstupní" uzel a právě jeden "výstupní" uzel (ze které už nevede žádná hrana). těmto "primárním" hranám říkám "next".

2) z každého uzlu (kromě výstupního) může (ale nemusí) vést ješrtě maximálně jedna orientovaná hrana, která vede jinam, než ta primární (kterou jsou pospojované uzly spojového seznamu) a která nikdy nevede do uzlu, který by nebyl součástí toho "podřízeného" spojového seznamu. volitelným sekundárním hranám říkám "seek".

toto je podle mě téměř vyčerpávající definice, ale já se domnívám, že kritický detail by mohl spočívat ve:

3) u uzlů, ze kterých nevede sekundární orientovaná hrana ("seek") máme alternativně ještě možnost jejich další kategorizace (např. "obarvení" - paralela k red-black trees, což je používaná datová struktura) (což se v Céčku implementuje velice snadno tak, že ty seek pointery budou ukazovat na něco, co z definice vůbec nebude smět být přidáno jako prvek toho binárního b+ stromu - triviální je označení hodnotou NULL, další jednoznačně "zakázaná" možnost je "ukazuji sám na sebe", apod. )

ANT_39: viz teď co jsem psal v bodě 3): já se domnívám, že by měl existovat nějaký trik, kterým "vyhandluju" informační entropii za výpočetní výkon :-) jinými slovy - pokud by to bylo jen tak, jak jsem to nakreslil zde - [ XCHAOS @ ANSI C/C99 (specifikace), GNU C (gcc, glibc), Tiny C (tcc) a POSIX - ne nutně C++,g++,libstdc++ nebo Win32 API ] - ale já se domnívám, že trik by mohl spočívat ve využití informační hodnoty těch uzlů, které nemají platný ten "seek" pointer. paralelu vidím ve struktuře http://en.wikipedia.org/wiki/Red-black_tree - kterou jsem sice úplně nepochopil, ale jednak jsou to takové hezké anarchistické barvy :) jednak je tam evidentně nějaký přidaný "prvek samoorganizace"

u mě jsou dva rozdíly: jednak je to binární B+ strom a nejen binární strom, a jednak (z myslím pochopitelných implementačních důvodů) chci obarvovat jen ty uzly, ze kterých nevedou dvě další hrany.

ve skutečnosti: zatím všechny moje pokusy nějak si to představit dost selhaly: ale víceméně si myslím, že by mohly být "obarveny" třeba ty uzly, na kterých nebo za kterými bezprostředně končí nějaká ta "seek" hrana. měl jsem vymyšlených několik takových "pravidel obarvování", ale na všechno jsem po několika pokusech našel nějaký protipříklad.

XCHAOS: Muzes definovat pravidla "binarniho B+-stromu"?

ANT_39: Kdybych tak mel trik, kterym o libovolnem Turingove stroji dokazu rozhodnout jestli se zastavi nebo ne, to by byla bomba 8)

XCHAOS: jak sakra jednoduše udržovat ty indexy použitelné i pro přidání nového prvku Jo, potrebujes to orakulum :)

ANT_39: no ano, realloc() je o tom, že nakonec stejně asi použiju pole místo nějakého "vylepšeného spojového seznamu" - na tuhle strukturu SAMOZŘEJMĚ vliv nemá, je to o diskuzi, co použít MÍSTO ní.

spojový seznam je ale pořád výborný, pokud se ti může stát, že přidáváš prvek někam náhodně doprostřed: tam je "posouvání" části toho pole pointerů pořád operace která může mít režii - zvlášť při vkládání na začátek. pole pointerů je skvělé, pokud víš kolik toho bude, a pokud víš, že všechny prvky dostaneš hned na začátku, a pak už žádný bud nepřibude, nebo (diskutabilně) přibude jen na konec.

tenhle "indexovaný spojový seznam" je také dobrý, pokud bys ho vybudoval na začátku, a pak věděl, že potřebuješ jen sem tam něco ubrat nebo přidat: pak by si s ním pracoval jako se spojovým seznam (a pouze odmázaval ty indexy, které případně odkazují na vymazaný prvek). místo pro přidání nového prvku taky krásně najdeš s logaritmickou složitostí (srovnej to s O(N) složitostí operace "pošoupávání všeho" u pole pointerů...)

od začátku mám jen jeden jediný problém: jak sakra jednoduše udržovat ty indexy použitelné i pro přidání nového prvku ? kdybych na tohle měl trik, tak je tahle struktura fakt bomba (ok, sice zabere 2x tolik paměti, než prosté pole pointerů - ale právě proto, že je tam tenhle tradeoff, mi přijde, že bych obětováním této paměti - a případně uložením nějaké "hint" informace do těch seek pointerů - např. odkazy na začátek, odkazy na NULL, odkazy na smluvené hodnoty NIL, kterých nesmí nabývat žádný prvek seznamu, apod. - mohl získat jako bonus nějakou úsporu strojového času...)

ANT_39: no ano. víceméně, před tím rokem nebo kdy debata vyhnila na tom, že se všichni podivovali, proč nepoužiju prostě pole pointerů na cokoliv (stringy, objekty). namítl jsem, že takto jsem kdysi implementoval např. textový editor kdysi v 16ti bitovém DOSu, a že problém je nemožnost jednoduše "nafukovat" to základní pole pointerů. a dostal jsem (poměrně chytrou) odpověď, že realloc() na současných architekturách je výrazně efektivnější: tedy, musel jsem připustit, že "array is not dead" (i Pythoní seznamy jsou implementované jako obyčejná pole pointerů na objekty, když jsme u toho... nebo byly, když jsem se naposledy snažil podívat do zdrojáků)

jinak setřídit spojový seznam je fakt hračka: tohle je o těch "seek-ahead" indexech (v podstatě každý prvek seznamu nemá jen pointer "next" ale ještě pointer "seek" - když tohle prohledáváš, vždycky se nejdřív ptáš na this->seek->key a teprve potom na this->next->key: prohledávání je triviální úloha, netriviální je jen postupný růst této struktury během přidávání prvků... počínaje tím prvním)

(ono je totiž relativně jednoduché udržet tu strukturu +/- někde mezi tou ideální logaritmickou složitostí a N/2, pokud jsou data na vstupu dostatečně náhodná: ale jakmile jsou nějak nevhodně setříděná, tak to strašně snadno zdegeneruje... tudíž kdyby tam tu náhodnost člověk dostal "zvenčí", i pro setříděná data na vstupu, tak by to mohlo pomoct...)

jako už asi rok jsem to zase nechal bejt, přiznávám, že jsem hodně línej.

DAVIDOWITCH: já se víceméně spokojil s myšlenkou, že bych z asi 3 přímočarých "reindexovacích" operací, které lze při vložení prvku provést, vždy nějakou vybral náhodně :-) ale zatím jsem to nezkusil implementovat.

(náhodná volba bývá při sestavování datových struktur používána kupodivu docela často...)

XCHAOS: Na zvetsovaci pole bacha, v momente kdy udelas resize a nemas za nim dost mista, tak se v O(N) prekopiruje. To je duvod proc se vzdycky zvetsuje na nejakej nasobek a ne o konstantu. Pocita se s tim ze "vyrosteni" trva O(N). A pri tom nasobeni to furt ma amortizovanou slozitost O(1) na insert.

Ja mel pocit ze problem s timhle stromem byly, ze potrebujes oracle co ho sestavi, bo sme zatim na vsechno vymysleli protipriklad kterej to rozvazi. (A mam dojem, ale tim uz si nejsem jiste, ze nekdo zkousel formalni dukaz proc to nemuze fungovat)

(a BTW, podobně úchylnými datovými strukturami se lidé zabývají a ne že ne.. když mohou existovat skip-listy a podobné zvrhlosti, proč ne tohle ?)

QUICK: Binární B+ strom by byl velmi zhruba tohle:



...celý problém je, že bych ho chtěl umět sestavit vždycky +/- ideálně oindexovaný - ale současně bez použití rekurzivně volaných funkcí (když bude ideálně oindexovaný, bude prohledávatelný s log2(N) složitostí). ve skutečnost - od té doby, co umím "zvětšovat pole", mě už potřeba téhle datové struktury přijde lehce méně naléhavá, ale stejně - měla by spoustu pěkných vlastností, kdyby jí šlo jednoduše vytvořit (přesněji: kdyby šlo JEDNODUŠE udržet konzistenci toho indexu při přidání jednoho prvku kamkoliv)

QUICK: přesněji řečeno: poloodborný a polozábavný (tady jsou lidé hákliví na nepřesné definice! zvláště někteří...)

Binární B+ strom je současně binární a současně B+. ale není to tak docela strom. někde v historii by měl být dokonce nakreslený...