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.

A kratsi to rozhodne mohlo bejt. Stacilo "aha, jasny, myslel sem smart pointery, ne refcounty." A ne se hadat.

XCHAOS: Ja neprogramuju akademicky. Ja delam doktorat. To je dost rozdil (typicky se lisi v tom jestli se bavim s panem ucitelem, nebo s researchem NVIDIA). Kazdopadne, ja sem ti navrhl upresneni terminologie. Rekl sem ti, nekolikrat, ze reference counting je jen a pouze pocitani referenci jakkoliv, a ze automaticke pak maji smartpointery. A pokazde sem se dozvedel ze nemam pravdu. Tak co bys chtel priste navrhovat jako upresneni? Nejakou uplne specialni terminologii, abychom uzavreli ferovy kompromis, kdyz jednoznacne nemas pravdu?