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ý...

XCHAOS: Coz nebudu po technicke strance vubec rozebirat. Smyslem bylo nazorne demonstrovat, ze tvoje teorie "sak my uz se nejak domluvim, sme prece lidi ne a tyhletcty odborny akademicky termity vlastne nepotrebujeme" je, mirne receno, mylna. Ale ocividne se to, jiz tradicne, minulo ucinkem 8)

ale každopádně se mu neříká Maruška. coz neni pravda. Vim aspon o trech, mozna i vice lidech, ktery tvemu algoritmu Maruska rikaji 8) (to ze jsi ho nikdy nedokoncil na veci nic nemeni 8) )

REDGUY: ok, ale "binární B+ strom" je velmi speciální případ B+ stromu. Současně to vůbec nevypadá jako binární strom, když jsme u toho. Možná se ten pojem dokonce ani nepožívá, ale každopádně se mu neříká Maruška.

XCHAOS: přínos takovéhle debaty mi přijde téměř nulový, sorry. lidi, co mají vůli ke spolupráci, a nestojí jen o to honit si ego, by situaci pochopili po prvních několika příspěvcích (za současného navržení upřesnění použité terminologie). - LOL. Delal jsi nekdy na nejakem vetsi projektu s vic lidma?

Normalni clovek: A tohle udelame pomoci B+ stromu.
XChaos: Oukej, jasne.
[ uplyne nekolik tydnu ]
Normalni clovek behem code review: W. T. F!?!?!?!?!??!?!

XCHAOS: tak o vzájemné interakci přemýšlet FAKT nemusíš: buď si to alokoval jedním způsobem, nebo druhým - Takze budu mi pro alokaci pameti dva ruzne, nezavisle systemy? To ti prijde prakticke? U kazde funkce si pamatovat, jakym zpusovem alokovala pamet na vysledky co vraci? A co kdyz zmenim implementaci funkce, takze misto forget/remember bude muset pouzit malloc? Budu muset prepsat vsechny mista v kodu kde se ta funkce pouziva a kdyz na jedno misto zapomenu, tak se to rozbije? To ti opravdu prijde prakticke a pouzitelne v jakemkoliv netrivialnim projektu?

Nebo ještě pro upřesnění: smart pointer si představuji jako speciální objekt, jehož destruktor obsahuje volání metody odkazovaného objektu pro snížení počtu evidovaných referencí (a případně - diskutabilně - i volání nějakého pokusu o provedení správy paměti - možná podle velikosti objektu který byl uvolněn, nebo v závislosti na tom, jestli ten počet referencí klesl na 0, apod.)

To je všechno fajn - ale chápeš, že ve většině ostatních jazyků kromě C++, které použijí refcounty, toto bude přímo nativní forma implementace VŠECH referencí na VŠECHNY třídy objektů: tedy, je to jakási dost C++ specifická berlička, o které uživatelé většiny vyšších jazyků prostě netuší, že to jejich jazyk má pod kapotou - zatímco u C++ si můžeš vybrat, jestli to pod tu kapotu namontuješ, nebo ne.

DAVIDOWITCH: ale já jsem nemyslel smart pointery :-) mimo C++ se prakticky nevyskytují a tohle není klub o C++

a z toho, co jste mě o tom donutili si nastudovat, jsem přesvědčený, že automatické udržování počtu referencí na objekt je něco jiného, než smart pointery.