Vlákno názorů k článku Programovací jazyk Rust: efektivní práce s prvky uloženými v kolekcích od aaa - Opravte prosim priklad 11, volanie funkcie na konci...
-
xxxxx (neregistrovaný)
No, tak jednoduše to Ord nepůjde. Coby obecná implementace.
Pokud člověk použije B-strom pro případ, aby dostal čísla seřazená dle velikosti, tak vyhodí nesmysl.
Vyhovovat bude pouze v případě, kdy se B-strom používá pro optimalizaci (rychlost ...) řazení. Pokud bychom předem věděli, že postupně zatřiďované prvky jsou blízko ideálnímu vstupnímu rozložení pro b-strom s takovýmto typem porovnávání, pro minimalizaci vykonávaných porovnávání.
-
xxxxx (neregistrovaný)
Jinak, v odpovědi jsem předpokládal tu "matematickou" na obvyklejší, normu (absolutní hodnotu). Typicky na rychlé zkouknutí extrémně malých a extrémně velkých čísel, která mohou znamenat pěknou paseku (a to nemyslím jen nejen pro počítačové limity jako přetečení, podtečení) nebo naopak příjemné zjednodušení dalších výpočtů.
Výjimečně (resp. méně užívaně) je třeba chtít vidět úhel (např. velký fázový posun), takže by se bral úhel.
V obou případech bývá často druhotná hodnota (úhel, norma) úplně nezajímavá /a je jedno zda dle ní nebude řazeno vůbec/. Výjimečně se dá užít jako druhotné řazení (obdobně jako diakritika u některých znaků, velká/malá písmena u case insensitive, ...)
A že libovolné nematematické mi pro b-stromy nedává smysl. V principu.
-
xxxxx (neregistrovaný)
To je věc rustu? Že musí mít každou hodnotu unikátní? Nebo jen může mít problémy s vyvážeností (ale jen s ní) v místě stejných hodnot?
P.S.: Jasně, pokud je stejné porovnání, nemusí vrátit konkrétní stejný item ... ale pokud např.hledám existenci/neexistenci konkrétních (jedničková, nulová, nulová po úpravě /+-x/, extrémy, ...) tak je důležitá _jen_ ta zatřiďovaná hodnota. Ostatní jsou irelevantní (prostě stejné prvky, byť ne binárně stejné).
-
xxxxx (neregistrovaný)
Teď nerozumím. Důležité je, aby se zachovala sekvence < = > vč transitivity.
Tedy aby platilo že pokud a==b a b==c tak i a==c. Stejně tak pro < a > .V tom Tvém příkladu jsi neuvedl vztah mezi b a c. Který známe. Pokud jsou rovny, tak je jedno jaké je jejich pořadí (jsou stejné). Pokud je jedna z nich menší, tak je první ta menší.
Jediný výjimka je v tom, že b-strom není plně vyvážený (pokud kolem toho neudělá něco více, z kontextu), pokud má stejné prvky. Ano, vlastnost b-stromu je vyváženost, takže je otázka zda to pak nazývat b-stromem (z definice). Ale fungovat by mělo.
-
ded.kenedy (neregistrovaný)
Důležité je, aby se zachovala sekvence < = > vč transitivity.
Ano, presne. Ale to co chces ty, tomu neodpovida.
V tom Tvém příkladu jsi neuvedl vztah mezi b a c. Který známe. Pokud jsou rovny, tak je jedno jaké je jejich pořadí (jsou stejné). Pokud je jedna z nich menší, tak je první ta menší.
Jenom, to nemusi platit. Vezmi si, ze prvky, ktere do b-stromu vkladas, jsou mnoziny. Pokud bys je chtel usporadat podle relace A je podmnozinou B, tak budes mit problem, protoze se nejedna o uplne usporadani a muze se se stat, ze o vztahu 'b' a 'c' nemuzes rict nic.
Pokud bys chtel mnoziny v b-stromu usporadat, napr. podle velikosti (coz je asi priklad, kam miris), tak vsechny mnoziny stejne velikosti se budou jevit jako jeden prvek. takze pokud bys tam vlozil mnozinu {a} a pak chtel vlozit {b}, tak se nic nestane, protoze |{a}| = |{b}|, resp {a} =* {b} a to znamena, ze prvek uz tam je.
Jediný výjimka je v tom, že b-strom není plně vyvážený (pokud kolem toho neudělá něco více, z kontextu), pokud má stejné prvky.
To je nesmysl z definice. Relace usporadani prvku nema vliv na strukturu B-stromu, ta je dana procesem vkladani, resp. odebirani prvku.
-
Jiz to psal ded.kenedy, jen bych to chtel uvest pedanticky presne :) :
Pokud si prvky nejsou rovne, musi mit jasne definovano, ktery je mensi. Navic tam musi platit transzitivita (a<b, b<c pak a<c). Jinak totiz nebude spravne fungovat vyhledani prvku v tom b-stromu, pripadne vyhledani pozice, kam se ten prvek ma vlozit.
Pokud si prvky jsou rovne, presto ze nejsou totozne, vystupuji v mnozine jako jeden prvek (tedy nejde tam vlozit dalsi jemu rovny).Teoreticky by se to dalo obejit stejne jako u hash tabulky seznamem na kolize, ale to uz je jina datova struktura s jinou slozitosti operaci. Vetsinou kombinuje nevyhody hashe a nevyhody b-stromu.
-
Samozřejmě to lze také řešit dodefinováním toho porovnání, tak aby to fungovalo. Jen se musí počítat s tím, že ta dodefinice často nemá žádný přirozeně využitelný smysl. (Například u komplexních čísel to může být lexikografické uspořádání nad polárními souřadnicemi. To dává seřazení podle absolutní hodnoty a úhel tam pak hraje roli té dodefinice uspořádání.)
-
xxxxx (neregistrovaný)
Tak koukám, že dle té teoretické definice asi opravdu původní b-tree nemůže mít stejný klíč.
No, je to už 25+ let, co jsem se mohl zabývat pouze teorií. V praxi se duplicity skoro vždy vyskytují, takže znám akorát takové implementace b stromu, které duplicity povolují.
Pro vysvětlení:
Jedena z takových jednodušších implementací (není-li duplicit mnoho) je udělat strom nevyvážený a u duplicit z r-linků udělat něco jako list, buď aniž by l-link byl obsazen (či pro mnoho duplicit si lze určit, že l-link /od stejné r-link child/ jsou jen ty duplicity a odebírat z nich). Jak říkáš, musí se s tím počítat, není to asi ten oficiální b-tree, ale při procházení stromu to je OK (vyčteš jen jednou, na duplicitu se můžeš ptát bokem či rovnou vracíš počet duplicit) Jen při odebírání a rebalancování je třeba kontrolovat zda r-link není stejný a zařídit se dle toho. Proto jsem tu tak motal ty poznámky ohledně nevyváženosti.Omluva. Už mne ani nenapadlo, že by mohl v reálné praxi existovat (zde dokonce přímo definován jazykem), b tree bez duplicit.
P.S.: Koukám i na wiki je v talk probírána právě duplicita.
-
Ten "nevyvážený strom" ale pak dělá přesně to co jsou "seznamy kolizí" u hash tabulky. A kombinuje to potom nevýhody obou řešení: vyhledání konkrétního prvku může být v nejhorším případě O(n), a přitom v průměru je vždy vyhledání O(log(n)) zatímco u hashů je průměr O(1) (přesněji u hashů je to také O(log(n)) protože se musí hashovat na něco co má řádově alespoň log(n) bitů, ale vtip je v tom, že počítání hashe je cache-lokální operace, zatímco prohledání stromu je spíše náhodný přístup do paměti.). Přitom libovolné dodefinování uspořádání srazí složitost v nejhorším případě na O(log(n)).
I z toho důvodu je lepší nechat na programátorovi jak chce duplicity řešit (a jakou z b-stromu odvodí datovou strukturu) než zvolit libovolný mechanismus řešení kolizí přímo v základní knihovně. V opačném případě to totiž dopadá tak, že programátor zvolí datovou strukturu bez přemýšlení, a výkon (nebo i funkčnost) programu stojí za starou belu.
-
ded.kenedy (neregistrovaný)
No, je to už 25+ let, co jsem se mohl zabývat pouze teorií. V praxi se duplicity skoro vždy vyskytují. ... Už mne ani nenapadlo, že by mohl v reálné praxi existovat (zde dokonce přímo definován jazykem), b tree bez duplicit.
Tohle neni o realne praxi, ale nepochopeni dane struktury a "domacim kutilstvi". Podivejte se nekdy i na programy, ktere delal nekdo jiny.
a u duplicit z r-linků udělat něco jako list,
Jak říkáš, musí se s tím počítat, není to asi ten oficiální b-tree, ale při procházení stromu to je OK
Jen při odebírání a rebalancování je třeba kontrolovat zda r-link není stejný a zařídit se dle toho
B-stromy nejsou nejaky ciste teoreticky vymysl, ale maji svou praktickou motivaci, kterou je datava struktura, ktera muze mit jednotlive casti (uzly, resp. stranky) ulozeny v sekundardni pameti, pricemz je optimalizovany pruchod tak, aby jednotlive stranky bylo potreba nacist do pameti prave jednou. Tim, ze si tam budes pridavat dalsi typu uzlu (resp. dat), abys resil nejaky specialni pripad, se ti to cele komplikuje a mam pochybnosti, jestli by slo napriklad pohodlne nacitat data ze sekundarni pameti.
Nema cenu se tu ohanet teorii vs. praxi, protoze zavedeni pomocnych uzlu, seznamu, atd. nema vubec prakticke opodstatneni, protoze misto nich staci vzit usporadani, ktere mas, a udelat z nej uplne usporadani, coz jde vzycky, a mas vystarane.
-
coz jde vzycky
Zase jedno pedantické upřesnění - jde to vždy když existuje nějaký normalizovaný zápis příslušných objektů. Mohlo by se teoreticky stát, že lze stejný objekt zapsat mnoha způsoby, lze zkontrolovat ekvivalenci (totožnost) dvou různých zápisů a přitom by nebylo možné udělat nějaký kanonický zápis objektu.
Jako příklad (hodně přitažený za vlasy a nepraktický, nicméně ilustruje problém) si vezměte třeba scany nějakých dokumentů. Pro jednoduchost řekněme, že těch dokumentů je nějaké omezené množství, a vzájemě se dostatečně liší, že můžete snadno rozpoznat, zda jde o scany totožného dokumentu. Nicméně máte různé scany téhož dokumentu a aby byla situace ještě horší, máte je uložené v různých ztrátových formátech (jpeg). A zrovna potřebujete rozlišit různé scany (protože přestože dovedete identifikovat kterému dokumentu patří, tak v některých jsou hůře čitelné části) ale zároveň chcete jeden scan uložený v různých formátech použít pouze jednou. Pak se hledá kanonický zápis, který by vždy seřadil scany jednoho dokumentu stejně bez ohledu na ztrátovou kompresi, kterou byli uloženy, těžko.
-
xxxxx (neregistrovaný)
Tak co jsem se tak díval kolem, tak mi to připadá, že rust si je vědom těch praktických problémů při porovnávání.
Chápu-li dobře, tak proto je možno (někdy nutno) definovat i PartialEq, PartialOrd a partrial_cmp, které dělají to lidské (ve smyslu praxe, reality) porovnávání. V nich je možno vracet duplicity či None (nejde-li porovnat) a podobně. A ty si mohu používat při svých porovnáváních.
Kdežto čisté Ord (resp. Eq, Hash) jsou určeny vnitřně pro rust, aby umožnily definovat úplné uspořádání (resp. jednoznačnost), pro množiny. I kdyby někdy měly vracet nelogická (až chybná) porovnání z pohledu reality (true pro NaN==NaN, ...).
-
ded.kenedy (neregistrovaný)
Chápu-li dobře, tak proto je možno (někdy nutno) definovat i PartialEq, PartialOrd a partrial_cmp, které dělají to lidské (ve smyslu praxe, reality) porovnávání.
Nechapes to dobre, neni zadne matematicke a lidske porovnani. Jsou algoritmy a problemy u nichz ti staci znat castecne usporadani (napr. relace byt pod mnozinou) a jsou problemy, kdy potrebujes mit uplne usporadani (napr. lexikograficke usporadani mnozin), ktere ma striktnejsi podminky. Pricemz, jak uz jsem psal vyse, pokud mas nejake castecne usporadani, muzes z nej kdykoliv udelat uplne dodatecnymi podminkami.
Kdežto čisté Ord (resp. Eq, Hash) jsou určeny vnitřně pro rust, aby umožnily definovat úplné uspořádání (resp. jednoznačnost), pro množiny
Ty jsou urceny pro pripady, kdy potrebujes mit uplne usporadani (nebo jednoznacnost), neni to o zadnem vntrnim nebo vnejsim pouziti v rustu.
-
Pavel TišnovskýZlatý podporovatelOpraveno (a ještě jedna maličkost v jiné kapitole), díky za upozornění.
