• úvod
  • témata
  • události
  • tržiště
  • diskuze
  • nástěnka
    • přihlásit
    registrace
    ztracené heslo?
    XCHAOSANSI C/C99 (specifikace), GNU C (gcc, glibc), Tiny C (tcc) a POSIX - ne nutně C++,g++,libstdc++ nebo Win32 API
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    1 odpověď
    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)
    XCHAOS
    XCHAOS --- ---
    (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 ?)
    XCHAOS
    XCHAOS --- ---
    3 odpovědi
    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)
    XCHAOS
    XCHAOS --- ---
    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ý...
    REDGUY
    REDGUY --- ---
    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) )
    QUICK
    QUICK --- ---
    2 odpovědi+1
    Ja to tady rad sleduju, je to jeden z mala odborne/neodborne zabavnych klubu :) Dik za smartpointry a refcount.

    Ale jak vypada teda ten binarni b+ tree? Ja si pamatuju, ze lidi od nas litali od zkousek se zjistenim, ze b-tree opravdu neni binarni strom. Tak jak se daji zkombinovat a co z toho?
    XCHAOS
    XCHAOS --- ---
    1 odpověď
    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.
    REDGUY
    REDGUY --- ---
    1 odpověď
    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!?!?!?!?!??!?!
    REDGUY
    REDGUY --- ---
    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?
    XCHAOS
    XCHAOS --- ---
    -1
    DAVIDOWITCH: ano, měl jsem párkrát co do činění s lidmi, kteří dělali doktorát :-) řekl bych, že jde o proces, na jehož konci budou vědět "všechno o ničem" - resp. většinou je to opravdu hodně úzce specializované, že.

    věz, že většina lidí kolem tebe, se kterými se budeš setkávat, v libovolném oboru, nebude tak úzce specializovaná, jako jsou specializovaní doktorandi. a nebudou se vyjadřovat tak přesně, jak je zvykem na akademické půdě, apod.

    zásadním nedorozuměním by přesto bylo dobré předcházet, to je fakt.
    XCHAOS
    XCHAOS --- ---
    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.
    XCHAOS
    XCHAOS --- ---
    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.
    XCHAOS
    XCHAOS --- ---
    -1
    změnil jsem úroveň diskuze na "polodbornou", aby bylo jasné, že jsou vítáni i lidé, pro které je programování především jednou z mnoha massive multiplayer online počítačových her, které lze hrát.

    nemusí nutně prchnout, jen protože neznají nuance typu smart pointer, nebo se nechtějí zabývat COM objekty (ostatně tenhle klub o nich explicitně není - je o tom, jak se programuje v GNU světě, a řada těch veleodborných poznámek je zde bohužel offtopic, přesto je moderátor toleruje..)
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    1 odpověď
    A kratsi to rozhodne mohlo bejt. Stacilo "aha, jasny, myslel sem smart pointery, ne refcounty." A ne se hadat.
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    1 odpověď
    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?
    XCHAOS
    XCHAOS --- ---
    DAVIDOWITCH: tak ano, bude to "manuální escape analysis" - přímo během psaní kódu :-) já si vůbec nehraju na automatickou garbage collection :-)
    XCHAOS
    XCHAOS --- ---
    2 odpovědi-2
    DAVIDOWITCH: jako programátor momentálně pracuju pouze na free/open source softwareových projektech (resp. ta trocha bastleni pro firmu, kterou stejně spoluvlastním, nestojí za řeč).

    akademické programování asi bude hodně o "hraní se slovíčky", to je pochopitelné.

    a fakt nemyslím, že jsem byl "umlácen argumenty" - víceméně, ano, budu opatrnější než něco řeknu, že "něco v nějakém jazyce nejde" - je tím myšleno "jazyk pro to nemá podporu, muselo by se to v něm vždycky dělat ručně".

    popravdě, ať už je klub odborný nebo poloodborný - 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).

    máš asi opravdu velkou potřebu předvádět, že umíš použít některé termíny přesněji než někdo jiný - to ale fakt není můj problém a fakt to šlo celé pojmout stručněji.
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    1 odpověď
    XCHAOS: Ale ta konverze bude manualni, ne automaticka (prekladacem, memory alokatorem), right?
    DAVIDOWITCH
    DAVIDOWITCH --- ---
    1 odpověď
    XCHAOS: No, takhle. Nevim kde pracujes. Tam kde ja (nemecka uni, delam doktorat) je technika hodne moc o "hrani si se slovicky". Protoze pokud se pouziva zavedenej termin spatne, nadela to spoustu paseky. Pouzivat refcount pro smartpointery je ten lepsi pripad. Protoze, v mem oboru, je napriklad opravdu velkej rozdil mezi stochastic progressive photon mapping a probabilistic progressive photon mapping. Prestoze to je v anglictine skoro synonymum.

    A protoze ty tuhle naprosto zasadni zasadu v odbornem klubu (ac svem) neuznavas a kdyz se nekdo zdesi ze pouzivas termin blbe, tak se zacnes hadat, tak si myslim ze ten flamewar za to stal. Byls umlacen k tomu, abys uznal ze refcount je neco jinyho a ze to co chces ty je automaticky reference counting. (A tady zase ustoupim ja, nemusi to bejt nezbytne smart pointer, muzes mit reference treba na disky, a kdyz uz ho nikdo nepotrebuje, tak ho zacnes zalohovat nebo co ja vim.)
    XCHAOS
    XCHAOS --- ---
    1 odpověď-1
    jinak ta strategie alokace kterou tu od začátku tlačím (a tedy ta makra remember/forget ) je podle mě blízká tomuhle: http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29#Escape_analysis - akorát jsem pochopitelně nevěděl, že se tomu tak říká :-)
    Kliknutím sem můžete změnit nastavení reklam