Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: Jonas 21. 02. 2018, 14:18:35
-
Ahojte, verim ze sa v tejto komunite najde mnoho Javistov ktory by mi vedeli odpovedat nasledujuci dotaz.
Vedeli by ste mi prosim poradit dobre zdroje na ucenie datovych struktur, nejake ich porovnanie ako funguju, preco je struktura X lepsia ako Y, a ake je jej vhodne vyuzitie, ake su ich zlozitosti, kolekcie, atd. s ohladom na ich implementaciu v Jave. Viete o nejakej dobrej knihe, alebo stranke ktora by pokryla taketo veci? Nemusi to byt zrovna obrovska 2000 stranova biblia, ak by tam ale bolo vsetko a strucne bolo by to idealne :). Dakujem za odpovede.
-
klasicka literatura: the art of computer programming
http://broiler.astrometry.net/~kilian/The_Art_of_Computer_Programming%20-%20Vol%201.pdf
https://vivekupadhyay125.files.wordpress.com/2013/08/donald-e-knuth-the-art-of-computer-programming-vol-3.pdf
-
Najdi si datovou strukturu, např. LinkedList, ArrayList, HashMap, dej to do googlu a podívej se na stackoverflow. Žádný lepší rozbor asi nenajdeš.
-
Anglická wikipedie.
-
uplny zaklad v cestine
https://java.vse.cz/pdf/skripta-datoveStruktury.pdf
-
uplny zaklad v cestine
https://java.vse.cz/pdf/skripta-datoveStruktury.pdf
Hm, to vypadá spíš jako překlad javadocu než originální dílo :) Ale jo, proč ne.
-
Pokud ty struktury znáte a chcete vědět implementační detaily Javy, tak existuje například výborná prezentace tady: http://www.iro.umontreal.ca/~dufour/cours/ift3912/docs/12-memory-efficient-java.pdf
-
Mě třeba příjde, že nevím, kde bych použil strom. V podstatě HashSet má stejnou časovou složitost pro vyhledávání jako vyvážený binární strom. Je to logické, pohybování se v setřízeném hashi metodou rozděl a panuj je v principu úplně stejné, jako ve vyváženém binárním stromu.
Ze stromů mi stačí znát binární strom a vyvážený binární strom a to jen tak, ab se neřeklo - stejně to používat nebudeš. Podstatně důležitější je dobrá znalost HashSet a HashMap, tzn. vědět, jak dělat vlastní hashe, proč je nepotřebuješ dělat, proč je nutné overridnout equals, když overridneš hashCode.
Já třeba do této chvíle nevím, proč mi HashMap nedokáže vrátit více než 1 prvek k danému hashi. Pořeboval jsem to a musel jsem zbytečně dělat svou vlastní třídu, kerá závislost 1:N v HashMap implementovala. (už se na mě chystá Jirsák)
-
Ikdyž teď když se nad tím zamýšlím, tak je to vlastně kravina aby to umělo 1:N... No nic. Prostě v těchto věcech hlavně musí mít javista jasno 8)
-
Mě přijde celkem dobrá tahle knížka http://www.martinus.cz/?uItem=55657. Příklady jsou sice v pascalu, ale dá se to brát jako pseudokód. O implementační detaily, stejně nejde. Výhoda je, že je to pěkně popsané, jde to přesně tak do detailů jak začátečník potřebuje na úrovni základního kurzu na VŠ, tak to není zbytečně dlouhé. Proti tomu ten knuth je spíš pro lidi co to chtějí buď implementovat do standardní knihovny, nebo to učit. Ne že by to nešlo použít, ale je tam toho zbytečně moc.
-
Mě třeba příjde, že nevím, kde bych použil strom. V podstatě HashSet má stejnou časovou složitost pro vyhledávání jako vyvážený binární strom. Je to logické, pohybování se v setřízeném hashi metodou rozděl a panuj je v principu úplně stejné, jako ve vyváženém binárním stromu.
Ze stromů mi stačí znát binární strom a vyvážený binární strom a to jen tak, ab se neřeklo - stejně to používat nebudeš. Podstatně důležitější je dobrá znalost HashSet a HashMap, tzn. vědět, jak dělat vlastní hashe, proč je nepotřebuješ dělat, proč je nutné overridnout equals, když overridneš hashCode.
Já třeba do této chvíle nevím, proč mi HashMap nedokáže vrátit více než 1 prvek k danému hashi. Pořeboval jsem to a musel jsem zbytečně dělat svou vlastní třídu, kerá závislost 1:N v HashMap implementovala. (už se na mě chystá Jirsák)
HashSet rozhodně nemá složitost jako vyhledávání ve stromu (to má TreeSet). Tam se nepoužívá žádný strom, ale jednosměrná funkce (což bys měl vědět, když víš že je potřeba napsat hashCode) a u těchto dvou implementací se může dost podstatně lišit i paměťová složitost. Ze stromů se běžně používá červenočerný a b-tree někdy se hodí použít i halda (například c++ std::map je RB, b-tree jsou databáze, filesystémy - všude kde je velikost stromu mimo paměť). Implementovat je asi nebudeš, ale aspoň bys měl vědět jejich složitosti a kdy je použít.
-
Já třeba do této chvíle nevím, proč mi HashMap nedokáže vrátit více než 1 prvek k danému hashi. Pořeboval jsem to a musel jsem zbytečně dělat svou vlastní třídu, kerá závislost 1:N v HashMap implementovala. (už se na mě chystá Jirsák)
Proč vlastní? Jak Apache tak Guava MultiMapy umí.
https://google.github.io/guava/releases/21.0/api/docs/com/google/common/collect/Multimap.html
https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/MultiMap.html
-
Mě třeba příjde, že nevím, kde bych použil strom.
Kdekoliv, kde si nevystacis s nahodnym pristupem k jednotlivym prvkum a kde chces mit hodnoty serazene pri sekvencnim pristupu.
V podstatě HashSet má stejnou časovou složitost pro vyhledávání jako vyvážený binární strom.
HashSet ma v prumernem pripade O(1) v nejhorsim O(n). V pripade vyvazenych stromu mas obvykle nejakou garanci kolem O(log n).
Je to logické, pohybování se v setřízeném hashi metodou rozděl a panuj je v principu úplně stejné, jako ve vyváženém binárním stromu.
WTF? Tohle nejak nechapu.
-
Pro teoretický background slídy k ADS1 a 2 a k DS1, KSP kuchařky a Marešův Průvodce labyrintem algoritmů.
https://ktiml.mff.cuni.cz/~fink/teaching/data_structures_I_2016_17/
http://ktiml.mff.cuni.cz/~cepek/vyuka.html
https://ksp.mff.cuni.cz/kucharky/
http://pruvodce.ucw.cz/
Mě třeba příjde, že nevím, kde bych použil strom. V podstatě HashSet má stejnou časovou složitost pro vyhledávání jako vyvážený binární strom.
Vyvážený vyhledávací strom umí oproti hashtable rychle "next" a "prev". Také bych čekal, že na HDD budou mít B stromy menší prostorový overhead při ještě rozumné rychlosti.
-
Je to logické, pohybování se v setřízeném hashi metodou rozděl a panuj je v principu úplně stejné, jako ve vyváženém binárním stromu.
WTF? Tohle nejak nechapu.
[/quote]
Proč to nechápeš. Představ si, jak bude probíhat hledání nějakého čísla ve vyváženém binárním stromu a jak bude probíhat hledání nějakého čísla v setřízeném poli metodou rozděl a panuj. Bude to dělat prakticky úplně to samé:
1. Skočí to na střední prvek VS skočí to na Root node
2. je číslo menší než prvek? Doleva, jinak doprava VS je číslo menší než aktuální node? Doleva, jinak doprava.
3. atd.
Je to úplně stejné. Proto říkám, že na co ti jsou binární vyvážené stromy, když máš HashMapu. Prostě ty vyvážené binární stromy na 99% use casu v Javě prostě nepotřebuješ.
-
A ať neteoretizujeme, zkus uvést nějaký konrétní příklad, kde v javě budeš používat binární strom namísto HashMapy. Uveď konkrétní úkol. To by mě docela zajímalo. Protože já to teda ještě neviděl. Ano, dělal jsem s R-stromy na bakalářce, ale ty byly v rámci databázového enginu psaného v C++. něco takového v Javě nikdy dělat nebudeš.
-
Proč to nechápeš. Představ si, jak bude probíhat hledání nějakého čísla ve vyváženém binárním stromu a jak bude probíhat hledání nějakého čísla v setřízeném poli metodou rozděl a panuj. Bude to dělat prakticky úplně to samé:
1. Skočí to na střední prvek VS skočí to na Root node
2. je číslo menší než prvek? Doleva, jinak doprava VS je číslo menší než aktuální node? Doleva, jinak doprava.
3. atd.
Je to úplně stejné. Proto říkám, že na co ti jsou binární vyvážené stromy, když máš HashMapu. Prostě ty vyvážené binární stromy na 99% use casu v Javě prostě nepotřebuješ.
Jak skočíš v hash mapě na střední prvek?
-
Proč to nechápeš. Představ si, jak bude probíhat hledání nějakého čísla ve vyváženém binárním stromu a jak bude probíhat hledání nějakého čísla v setřízeném poli metodou rozděl a panuj. Bude to dělat prakticky úplně to samé:
1. Skočí to na střední prvek VS skočí to na Root node
2. je číslo menší než prvek? Doleva, jinak doprava VS je číslo menší než aktuální node? Doleva, jinak doprava.
3. atd.
Je to úplně stejné. Proto říkám, že na co ti jsou binární vyvážené stromy, když máš HashMapu. Prostě ty vyvážené binární stromy na 99% use casu v Javě prostě nepotřebuješ.
Jak skočíš v hash mapě na střední prvek?
To je otázka, kterou se mě v podstatě ptáš na tohle: jak skočiš v poli integerů setřízeném na stacku na středový prvek toho pole. A na to snad odpověď znáš.
-
A skáčeš na střední prvek v poli, tzn. když má to pole o velikosti 100 prvků, tak snad si můžeš vytáhnout 50. prvek. Přičemž 50. prvek samozřejmě nevypovídá nic o jeho hodnotě. Ale to ani u vyváženého binárního stromu.
-
A skáčeš na střední prvek v poli, tzn. když má to pole o velikosti 100 prvků, tak snad si můžeš vytáhnout 50. prvek. Přičemž 50. prvek samozřejmě nevypovídá nic o jeho hodnotě. Ale to ani u vyváženého binárního stromu.
zjisti si co je hash mapa
-
A skáčeš na střední prvek v poli, tzn. když má to pole o velikosti 100 prvků, tak snad si můžeš vytáhnout 50. prvek. Přičemž 50. prvek samozřejmě nevypovídá nic o jeho hodnotě. Ale to ani u vyváženého binárního stromu.
zjisti si co je hash mapa
To si spíše zjisti ty, já to vím.
-
A ačkoliv nejsem nerd natoli, abych se hrabal v mechanismu vyhledávání prvku v hashmapě podle klíče, a kvůli tobě to dělat nebudu, pochybuju, že v hash tabulce se hledá sekvenčně.
-
Tzn. jaksi apriori předpokládám, že hasha jsou v HashMapě setřízeny podle velikosti do pole a že se v tom poli vyhledává nějakým sofistikovanějším algoritmem, ne že se sekvenčně prochází.
-
A ačkoliv nejsem nerd natoli, abych se hrabal v mechanismu vyhledávání prvku v hashmapě podle klíče, a kvůli tobě to dělat nebudu, pochybuju, že v hash tabulce se hledá sekvenčně.
A tady, milé děti, vidíte, proč je důležité se vzdělávat.
-
Oc mensi znalosti o to vic sebevedomi (a prispevku).
Tzn. jaksi apriori předpokládám, že hasha jsou v HashMapě setřízeny podle velikosti do pole a že se v tom poli vyhledává nějakým sofistikovanějším algoritmem, ne že se sekvenčně prochází.
To predpokladas blbe. Uz jenom z principu, podle ceho by tam byly serazeny, kdyz mas jen hashCode a equals?
A ačkoliv nejsem nerd natoli, abych se hrabal v mechanismu vyhledávání prvku v hashmapě podle klíče, a kvůli tobě to dělat nebudu, pochybuju, že v hash tabulce se hledá sekvenčně.
Schvalne jsem si to rozklikl a HashMap v Jave opravdu pouziva separatni retezeni, tj. sekvencni pruchod ala spojovy seznam. Jeste se casto pouziva otevrene adresovani, ale tam ti algoritmy typu divide et impera jsou prd platne.
A ať neteoretizujeme, zkus uvést nějaký konrétní příklad, kde v javě budeš používat binární strom namísto HashMapy.
Mam v pameti kolekci entit (treba "zaznam o uzivateli") a chci jej vypsat serazeny, pridavat/odebirat zaznamy, a mit to porad serazene.
-
Schvalne jsem si to rozklikl a HashMap v Jave opravdu pouziva separatni retezeni, tj. sekvencni pruchod ala spojovy seznam.
Já měl za to, že když počet prvků (kolizí) v daném bucketu překročí nějakou mez, tak se přejde na stromečky.
http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/a006fa0a9e8f/src/share/classes/java/util/HashMap.java#l143
-
Oc mensi znalosti o to vic sebevedomi (a prispevku).
A ačkoliv nejsem nerd natoli, abych se hrabal v mechanismu vyhledávání prvku v hashmapě podle klíče, a kvůli tobě to dělat nebudu, pochybuju, že v hash tabulce se hledá sekvenčně.
Schvalne jsem si to rozklikl a HashMap v Jave opravdu pouziva separatni retezeni, tj. sekvencni pruchod ala spojovy seznam. Jeste se casto pouziva otevrene adresovani, ale tam ti algoritmy typu divide et impera jsou prd platne.
Nápodobně.
Tady to máš komplet, musel jsem si tu blbost kvůli vám číst:
https://www.geeksforgeeks.org/internal-working-of-hashmap-java/
1. V Javě se spojový seznam používá jen do určité míry, než dojde k rehashování:
Time complexity is almost constant for put and get method until rehashing is not done.
2. Implementace v Javě nepoužívá rozděl a panuj (je to uděláno tak, že není potřebný), ale hash je přesně jak jsem řekl setřízen podle velikosti do pole, přičemž každý index toho pole představuje zminimalizovaný hash, to umožňuje rovnou skočit na spravný prvek pole při hledání. Tzn. hash o velikosti int je na začátku HashMapy zredukován do čísla 0-15. Tím dochází při vkládání k duplicitám a ty jsou řešený použitím seznamu, ale jen do určitého bodu, než dojde k přeuspořádání pole, viz bod 1
3. Pořád jste nikdo nevyvrátili to, co tady celou dobu tvrdím: ten kluk se ptá na stromy a datové struktury v Javě a nikdo jste mu, kromě mě, nevysvětlili, proč v 99.9% případů bude používat když už tak HashMapu a ne nějaké stromy. A ještě tu ze mě budete dělat blbce.
-
Protože pro Java programátora je akorát tak dobré vědět, co vlastně binární strom je, jak funguje vyvážený binární strom, ale TO JE TAK VŠECHNO! Další xyz stromu jsou mu nanic a on v Javě nepoužije nikdy ani ty binární, jen je dobré je znát. Proto mu přesně odpovídám na jeho otázku, tzn. aby se zaměřil na HashMap a HashSet. A ArrayList, LinkedList a proč v 95% případů ani ten LinkedList používat nebude.
-
Oc mensi znalosti o to vic sebevedomi (a prispevku).
A ačkoliv nejsem nerd natoli, abych se hrabal v mechanismu vyhledávání prvku v hashmapě podle klíče, a kvůli tobě to dělat nebudu, pochybuju, že v hash tabulce se hledá sekvenčně.
Schvalne jsem si to rozklikl a HashMap v Jave opravdu pouziva separatni retezeni, tj. sekvencni pruchod ala spojovy seznam. Jeste se casto pouziva otevrene adresovani, ale tam ti algoritmy typu divide et impera jsou prd platne.
Nápodobně.
Tady to máš komplet, musel jsem si tu blbost kvůli vám číst:
https://www.geeksforgeeks.org/internal-working-of-hashmap-java/
1. V Javě se spojový seznam používá jen do určité míry, než dojde k rehashování:
Time complexity is almost constant for put and get method until rehashing is not done.
2. Implementace v Javě nepoužívá rozděl a panuj (je to uděláno tak, že není potřebný), ale hash je přesně jak jsem řekl setřízen podle velikosti do pole, přičemž každý index toho pole představuje zminimalizovaný hash, to umožňuje rovnou skočit na spravný prvek pole při hledání. Tzn. hash o velikosti int je na začátku HashMapy zredukován do čísla 0-15. Tím dochází při vkládání k duplicitám a ty jsou řešený použitím seznamu, ale jen do určitého bodu, než dojde k přeuspořádání pole, viz bod 1
3. Pořád jste nikdo nevyvrátili to, co tady celou dobu tvrdím: ten kluk se ptá na stromy a datové struktury v Javě a nikdo jste mu, kromě mě, nevysvětlili, proč v 99.9% případů bude používat když už tak HashMapu a ne nějaké stromy. A ještě tu ze mě budete dělat blbce.
My z tebe ale blbce neděláme, to zvládáš sám ;)
-
Jak ubohé a laciné ;)
-
Jak ubohé a laciné ;)
“hash je přesně jak jsem řekl setřízen podle velikost”
Leda tak prd. Radši si nastuduj, jak hashmapa funguje.
-
Ahojte, verim ze sa v tejto komunite najde mnoho Javistov ktory by mi vedeli odpovedat nasledujuci dotaz.
Vedeli by ste mi prosim poradit dobre zdroje na ucenie datovych struktur, nejake ich porovnanie ako funguju, preco je struktura X lepsia ako Y, a ake je jej vhodne vyuzitie, ake su ich zlozitosti, kolekcie, atd. s ohladom na ich implementaciu v Jave. Viete o nejakej dobrej knihe, alebo stranke ktora by pokryla taketo veci? Nemusi to byt zrovna obrovska 2000 stranova biblia, ak by tam ale bolo vsetko a strucne bolo by to idealne :). Dakujem za odpovede.
Začni tady https://docs.oracle.com/javase/8/docs/technotes/guides/collections/index.html prosím. Znalost JCF je nejenom užitečná, ale na pohovorech na ní většinou dojde řeč, i k porovnávání složitostí při různých operacích. Sun^W Oracle to má popsané dobře.
Porovnání existujících kolekcí je tady: https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html
OT: určitě nestačí znát jen HashMap a HashSet, nenech se prosím zmást diskuzí tady na rootu :-)
-
Jak ubohé a laciné ;)
“hash je přesně jak jsem řekl setřízen podle velikost”
Leda tak prd. Radši si nastuduj, jak hashmapa funguje.
hodnoty hashmapy jsou ulozeny normalne v poli indexovanem od 0 do N, akorat je zde hash funkce, ktera prevede klic na index.
klidne muze byt klic "fasfasfasfa" hash funkci prepocten na index 0 a klic "a" preveden na index 10000000000000000........
hash funkce muze byt jakakoliv, ale pro ruzne klice by nemela generovat indexy, ktere jsou stejne.
-
Pořád jste nikdo nevyvrátili to, co tady celou dobu tvrdím: ten kluk se ptá na stromy a datové struktury v Javě a nikdo jste mu, kromě mě, nevysvětlili, proč v 99.9% případů bude používat když už tak HashMapu a ne nějaké stromy.
Když už takovéhle triviality nevíte, pomohlo by vám, kdybyste se podíval do JavaDoc na to, jaké potomky má rozhraní Map – podle toho zjistíte, jaké existují (alespoň ve standardní knihovně) specializace, čím se liší, a pak už se vám bude lépe uvažovat nad tím, k čemu by se mohly používat.
Takže zjistíte, že existuje např. SortedMap, která má na rozdíl od obecné mapy klíče seřazené. To znamená, že můžete dělat takové věci, jako „dej mi výsek mapy od – do“, „dej mi všechny prvky větší než“. Implementací SortedMap je např. TreeMap, což je právě ten strom, na který se ptáte.
Abyste viděl nějaký hodně konkrétní příklad, tak když budete mít mapu osob, kde bude klíčem třeba datum a umožníte hledat rozsah údajů, třeba „vše za rok 2017“. V tom vám mapa, která umí prvky porovnávat pouze na ekvivalenci (což je třeba právě hashmapa) nepomůže, a potřebujete alespoň tu SortedMap.
Pokud nerozumíte tomu, jak hashmapa funguje, zapomeňte na to, že je uvnitř nějaké pole (akorát vás to mate), a zapamatujte si hlavně to, že hashmapa umí porovnávat klíče pouze na ekvivalenci, neumí je porovnat větší/menší a neví tedy nic o jejich pořadí.
-
na pohovorech na ní většinou dojde řeč, i k porovnávání složitostí při různých operacích. Sun^W Oracle to má popsané dobře.
kde prosim je popsana ta zlozitost v oracle dokumentacii? neviem ci som slepy, ale nevidim to tam :)
-
na pohovorech na ní většinou dojde řeč, i k porovnávání složitostí při různých operacích. Sun^W Oracle to má popsané dobře.
kde prosim je popsana ta zlozitost v oracle dokumentacii? neviem ci som slepy, ale nevidim to tam :)
Tady u jednotlivých implementací: https://docs.oracle.com/javase/tutorial/collections/implementations/index.html
Například pro seznamy tady: https://docs.oracle.com/javase/tutorial/collections/implementations/list.html
+ se to zmiňuje i v JavaDocu u jednotlivých kolekcí, třeba tady: https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html
(většinou ale nepíšou O(n), ale rozepisují jako "linear time", taky namísto O(n log n) píšou "n*log(n) time" atd., takže se to trošku hůř hledá)
-
(většinou ale nepíšou O(n), ale rozepisují jako "linear time", taky namísto O(n log n) píšou "n*log(n) time" atd., takže se to trošku hůř hledá)
jo to bude ono ... som to este necital poriadne len ocami prebehol a nevsimol som si ziadne big O :)
-
Já si nemůžu pomoct, ale přijde mi, že anonym si myslí, že vyhledávání v hashtable funguje tak, že se spočítá hash, který může být podstatně větší než velikost hashtable, a pak se v hashtable binárně vyhledá. Jenže tak to nefunguje, ten hash má hodnotu 0..velikost_tabulky-1 (v nejjednodušším případě tak, že větší hash prostě zmodulíme velikostí tabulky) a ty přistoupíš pouze k tomu jednomu bucketu, kam toto ukazuje.
Nedorozumění by asi vyřešilo, kdyby anonym popsal, jak přesně si myslí, že to funguje, a kde tam vidí to vyhledávání půlením intervalu.
-
Já si nemůžu pomoct, ale přijde mi, že anonym si myslí, že vyhledávání v hashtable funguje tak, že se spočítá hash, který může být podstatně větší než velikost hashtable, a pak se v hashtable binárně vyhledá. Jenže tak to nefunguje, ten hash má hodnotu 0..velikost_tabulky-1 (v nejjednodušším případě tak, že větší hash prostě zmodulíme velikostí tabulky) a ty přistoupíš pouze k tomu jednomu bucketu, kam toto ukazuje.
Nedorozumění by asi vyřešilo, kdyby anonym popsal, jak přesně si myslí, že to funguje, a kde tam vidí to vyhledávání půlením intervalu.
Taky mam tu obavu, ze si to mysli, ale zase "agilni" a hlasity je :) Praveze vyhoda hashtabulky je, ze prvni vyhledani je jen primy pristup k n-temu prvku tabulky (podle hashe), takze tato cast je O(1), coz je super. Nevyhoda potom v kolizich, protoze nastupuje pruchod seznamem, i kdyz jde pouzit i jine struktury. Mozna tedy mysli tuto druhou cast?
Btw napriklad v Jave 1.1 nebo 1.2 (ted z hlavy nedam) se hash pro stringy pocital jen z prvnich n znaku, takze to v realnych situacich vedlo i ke 100% kolizim.
-
3. Pořád jste nikdo nevyvrátili to, co tady celou dobu tvrdím: ten kluk se ptá na stromy a datové struktury v Javě a nikdo jste mu, kromě mě, nevysvětlili, proč v 99.9% případů bude používat když už tak HashMapu a ne nějaké stromy. A ještě tu ze mě budete dělat blbce.
Pro malé struktury opravdu moc nebude, většina kódu je založená na ArrayList a HashMap (+ nějaké odvozeniny jako Set, concurrent varianty a tak).
Jakmile ale začne zpracovávat data, která se nevlezou do paměti (nebo je tam nechce), tak je strom nebo linked list jediná rozumná možnost. HashMapa i ArrayList se v souboru implementují blbě.
Java kolekce jsou zaměřená na rychlost a ne na paměťovou efektivitu, takže je právě dobré vědět, že existuje něco jako Trove [1] nebo MapDB [2].
[1] https://bitbucket.org/trove4j/trove - efektivní kolekce (vč. kolekcí primitivních typů)
[2] http://www.mapdb.org/ - kolekce na disku
Co by určitě měl znát jsou teoretické časové složitosti jednotlivých operací nad těmi typy. To už ale není nic Java specifického. Pěkná tabulka třeba tady: https://stackoverflow.com/a/559862/1996623
-
Já si nemůžu pomoct, ale přijde mi, že anonym si myslí, že vyhledávání v hashtable funguje tak, že se spočítá hash, který může být podstatně větší než velikost hashtable, a pak se v hashtable binárně vyhledá. Jenže tak to nefunguje, ten hash má hodnotu 0..velikost_tabulky-1 (v nejjednodušším případě tak, že větší hash prostě zmodulíme velikostí tabulky) a ty přistoupíš pouze k tomu jednomu bucketu, kam toto ukazuje.
Nedorozumění by asi vyřešilo, kdyby anonym popsal, jak přesně si myslí, že to funguje, a kde tam vidí to vyhledávání půlením intervalu.
“Anonym” je typický dnešní lopatoid, bez znalostí a zkušeností nad rámec zvláštní školy, ale zato hlasitý a s egem. Snad se aspoň poučí.
-
V podstatě HashSet má stejnou časovou složitost pro vyhledávání jako vyvážený binární strom.
HashSet ma v prumernem pripade O(1) v nejhorsim O(n). V pripade vyvazenych stromu mas obvykle nejakou garanci kolem O(log n).
Tohle platilo do Java 7, od Java 8 už je to u HashMap (což je použito i v HashSet) v nejhorším případě O(log n): http://openjdk.java.net/jeps/180
-
V podstatě HashSet má stejnou časovou složitost pro vyhledávání jako vyvážený binární strom.
HashSet ma v prumernem pripade O(1) v nejhorsim O(n). V pripade vyvazenych stromu mas obvykle nejakou garanci kolem O(log n).
Tohle platilo do Java 7, od Java 8 už je to u HashMap (což je použito i v HashSet) v nejhorším případě O(log n): http://openjdk.java.net/jeps/180
Ale vyhledávání furt bude sekvenční, o to javamanovi šlo.
-
Ale vyhledávání furt bude sekvenční, o to javamanovi šlo.
Já to chápu tak, že vyhledávání bude logn pokud koliduje hash32 % size a lineární pokud kolidují přímo hashe. Ale Javu neznám.
-
Ale vyhledávání furt bude sekvenční, o to javamanovi šlo.
Najít medián bude vždy lineární.
Já to chápu tak, že vyhledávání bude logn pokud koliduje hash32 % size a lineární pokud kolidují přímo hashe. Ale Javu neznám.
-
Já to chápu tak, že vyhledávání bude logn pokud koliduje hash32 % size a lineární pokud kolidují přímo hashe. Ale Javu neznám.
Já asi nechápu místní význam pojmu vyhledávání.
Přístup k náhodnému prvku HashMapy pomocí klíče bude O(1) = konstantní, nebo při kolizi nejhůře O(log n). Ve starších verzích nejhůře O(n) = lineární. V obou případech je N počet kolidujících prvků se stejným hash (nebo hash % bucket_count). Navíc dojde k přepočítání té hash struktury, když začne být příliš plná.
Pokud hledám podle hodnoty, tak je složitost HashMapy O(n), protože ty prvky musím projít všechny. S tím může pomoci LinkedHashMap (pořadí podle času vložení) nebo spíše jedna ze SortedMap implementací. Ty už ovšem interně používají strom a náhodný přístup pomocí klíče je O(log n). Na druhou stranu hledání podle hodnoty je také O(log n), protože můžu použít půlení intervalu.
Další možností je mít mapy dvě - podle klíče a podle hodnoty. Cena za to je větší spotřeba paměti. Takovou strukturu najdete třeba v Guavě: https://github.com/google/guava/wiki/NewCollectionTypesExplained#bimap
Nic z toho není specifické pro Javu a podobné struktury najdete i v jiných jazycích. Všechny ty časové složitosti jsou pořád stejné jako nás kdysi učili na škole a není na nich nic magického. Prostě hledání klíče v "hash poli" je O(1), ve stromu O(log n) a v poli O(n). Všechny ty struktury co tu popisujete jsou jen kombinací těchto tří.
-
Přístup k náhodnému prvku HashMapy pomocí klíče bude O(1) = konstantní, nebo při kolizi nejhůře O(log n). Ve starších verzích nejhůře O(n) = lineární. V obou případech je N počet kolidujících prvků se stejným hash (nebo hash % bucket_count).
Jak se udělá logaritmický přístup k prvku, když mají všechny prvky stejný hash? Předpokládám, že je podle ničeho jiného nemůžeš porovnávat, máš jenom hash a equals().
-
Pokud je k dispozici jen hash a equal, pak je nejvyšší složitost lineární. Pokud jdou objekty porovnávat, je na hash-slotu strom.
-
Máte oba samozřejmě pravdu, nicméně zrovna v Javě u Map (narozdíl od typického použití Setu) jsou klíče takřka vždy porovnatelné. Nebo alespoň dostatečně často, abychom si mohli dovolit zjednodušení v diskusi. V Javě má stejně smysl mluvit jen o amortizovaném O(1), protože to N je malé a ta kolekce se sama přepočítá jakmile to začne být výhodné.
Já jsem hlavně reagoval na to, že tu spousta lidí hází pojmy jako vyhledávat a lineární a vůbec nevnímají tu konstantní složitost pro náhodný přístup pomocí hashe. Vůbec si nepředstaví ten algoritmus a cykly v něm (a nebo netuší co je principem hash tabulky...).
-
Máte oba samozřejmě pravdu, nicméně zrovna v Javě u Map (narozdíl od typického použití Setu) jsou klíče takřka vždy porovnatelné. Nebo alespoň dostatečně často, abychom si mohli dovolit zjednodušení v diskusi. V Javě má stejně smysl mluvit jen o amortizovaném O(1), protože to N je malé a ta kolekce se sama přepočítá jakmile to začne být výhodné.
Já jsem hlavně reagoval na to, že tu spousta lidí hází pojmy jako vyhledávat a lineární a vůbec nevnímají tu konstantní složitost pro náhodný přístup pomocí hashe. Vůbec si nepředstaví ten algoritmus a cykly v něm (a nebo netuší co je principem hash tabulky...).
Někteří jen poukazovali na chybné tvrzení, že medián v hashmapě jde najít jinak než sekvenčně. To s klíči vůbec nesouvisí, nalezení i-tého prvku v nesetříděné množině pro libovolné i je lineární.
-
Někteří jen poukazovali na chybné tvrzení, že medián v hashmapě jde najít jinak než sekvenčně. To s klíči vůbec nesouvisí, nalezení i-tého prvku v nesetříděné množině pro libovolné i je lineární.
A na to právě reagoval MarSik, protože nalezení i-tého prvku v nesetříděné množině je prostě nesmysl. Když je ta množina nesetříděná, nemají prvky v ní žádné pořadí a neexistuje žádný i-tý prvek. Pokud je ale řeč o poli, tam jsou prvky seřazené podle svého pořadí v tom poli – a nalezení i-tého prvku se provede v konstantním čase, protože je to jen jednoduché přičtení adresy.
Takže v hashmapě se hledá tak, že se vypočítá hash klíče a tento hash modulo velikost hashovací tabulky je přímo index v dané tabulce (přístup je tedy konstantní). Pokud je pod tímto hashem jediný klíč, mám výsledek, pokud dojde ke kolizi a pod stejným hashem je uloženo víc klíčů, je nutné ještě najít ten správný klíč. Obecně je pak v tabulce uložen neseřazený seznam klíčů a pak nezbývá než porovnat klíče jeden po druhém, dokud se nenajde shoda (tedy složitost je lineární). Pokud je možné klíče seřadit, lze to optimalizovat a v případě kolize klíčů použít nějakou strukturu, ve které se lépe vyhledává, než neseřazený seznam.
-
Někteří jen poukazovali na chybné tvrzení, že medián v hashmapě jde najít jinak než sekvenčně. To s klíči vůbec nesouvisí, nalezení i-tého prvku v nesetříděné množině pro libovolné i je lineární.
A na to právě reagoval MarSik, protože nalezení i-tého prvku v nesetříděné množině je prostě nesmysl. Když je ta množina nesetříděná, nemají prvky v ní žádné pořadí a neexistuje žádný i-tý prvek. Pokud je ale řeč o poli, tam jsou prvky seřazené podle svého pořadí v tom poli – a nalezení i-tého prvku se provede v konstantním čase, protože je to jen jednoduché přičtení adresy.
Takže v hashmapě se hledá tak, že se vypočítá hash klíče a tento hash modulo velikost hashovací tabulky je přímo index v dané tabulce (přístup je tedy konstantní). Pokud je pod tímto hashem jediný klíč, mám výsledek, pokud dojde ke kolizi a pod stejným hashem je uloženo víc klíčů, je nutné ještě najít ten správný klíč. Obecně je pak v tabulce uložen neseřazený seznam klíčů a pak nezbývá než porovnat klíče jeden po druhém, dokud se nenajde shoda (tedy složitost je lineární). Pokud je možné klíče seřadit, lze to optimalizovat a v případě kolize klíčů použít nějakou strukturu, ve které se lépe vyhledává, než neseřazený seznam.
Nechápeš, pročež píšeš nesmysly. Představ si pole čísel v náhodném pořadí. Nalezení i-tého největšího prvku je lineární. A stejně lineární je to i v hashmapě, když jsou hodnotami čísla (na klíči nesejde). Nalezení mediánu je jen speciální případ nalezení i-tého největšího prvku.
-
Nechápeš, pročež píšeš nesmysly. Představ si pole čísel v náhodném pořadí. Nalezení i-tého největšího prvku je lineární. A stejně lineární je to i v hashmapě, když jsou hodnotami čísla (na klíči nesejde). Nalezení mediánu je jen speciální případ nalezení i-tého největšího prvku.
Co má nalezení i-tého prvku společného s HashMapu? Máte samozřejmě pravdu, pokud se bavíme o hledání hodnoty v poli nebo o procházení všech prvků. Jenže to u mapy nedává smysl. Mapa slouží na získání hodnoty podle klíče a žádné hledání se tam nekoná. Hash se použije jako přímý offset do pole.
-
Jak se udělá logaritmický přístup k prvku, když mají všechny prvky stejný hash? Předpokládám, že je podle ničeho jiného nemůžeš porovnávat, máš jenom hash a equals().
Jen taková technická poznámka, nakonec nemáte totiž úplně pravdu:
Pokud je bucketů méně než možných hashů (tj. vždy), tak v případě kolize nemají všechny prvky stejný hash (kolize je na úrovni indexu bucketu). Takže se dá porovnávat ten hash samotný.
Navíc, pokud mají dva prvky stejný hash klíče, tak se z hlediska kolekcí jedná o ten samý prvek. Tj dojde k přepsání hodnoty pro ten klíč a žádná kolize nenastane.
-
Nechápeš, pročež píšeš nesmysly. Představ si pole čísel v náhodném pořadí. Nalezení i-tého největšího prvku je lineární. A stejně lineární je to i v hashmapě, když jsou hodnotami čísla (na klíči nesejde). Nalezení mediánu je jen speciální případ nalezení i-tého největšího prvku.
Co má nalezení i-tého prvku společného s HashMapu? Máte samozřejmě pravdu, pokud se bavíme o hledání hodnoty v poli nebo o procházení všech prvků. Jenže to u mapy nedává smysl. Mapa slouží na získání hodnoty podle klíče a žádné hledání se tam nekoná. Hash se použije jako přímý offset do pole.
To se zeptejte javamana. On každou diskusi převrátí na hlavu. Asi nevěděl pořádně, co je hashmapa, a zamotal se.
-
Navíc, pokud mají dva prvky stejný hash klíče, tak se z hlediska kolekcí jedná o ten samý prvek. Tj dojde k přepsání hodnoty pro ten klíč a žádná kolize nenastane.
Ne.
-
Nechápeš, pročež píšeš nesmysly. Představ si pole čísel v náhodném pořadí. Nalezení i-tého největšího prvku je lineární. A stejně lineární je to i v hashmapě, když jsou hodnotami čísla (na klíči nesejde). Nalezení mediánu je jen speciální případ nalezení i-tého největšího prvku.
Nesmysly tu píše spousta lidí, ale já ani MarSik to nejsme. i-tý největší prvek pole je úplně něco jiného, než i-tý prvek pole. i-tý největší prvek se vztahuje k hodnotám těch prvků, a mimo jiné předpokládá, že ty prvky umím porovnat a tedy seřadit. i-tý prvek se vztahuje k pořadí těch prvků v poli, v programátorském zápisu je to prostě pole.
V hashmapě to „stejně lineární“ není – a bylo by dobré, kdybyste si konečně zjistil, jak hashmapa funguje. Začněme tím, že v hashmapě jsou dvě struktury, ve kterých se prvek hledá. První struktura je hashtabulka, klíčová struktura pro hashmapu – je to pole, ve kterém index pole přímo odpovídá hashi klíče. Mám klíč, z něj vypočítám hash, ten hash převedu do rozsahu velikosti pole (např. hash modulo velikost pole), a tahle hodnota se použije přímo jako index té hashtabulky. Vyhledávání v té tabulce tedy není v lineárním čase, ale v konstantním – je to prostě přístup do pole podle indexu. No a protože může dojít ke kolizi hashů, tj. víc klíčů má stejný hash a mělo by být umístěných ve jedné položce té hashtabulky, musím mít možnost uložit na tu pozici ne jeden klíč, ale jejich množinu. Nejjednodušší je udělat tam spojový seznam, v něm se pak konkrétní hodnota opravdu hledá v lineárním čase, ale pokud klíče umím setřídit, můžu tam použít i jinou strukturu, ve které půjde rychleji hledat – třeba seřazený seznam nebo binární vyhledávací strom.
Představte si to třeba pro hashtabulku o velikosti čtyř prvků. Prázdná vypadá takhle:
hashtable[0] = ();
hashtable[1] = ();
hashtable[2] = ();
hashtable[3] = ();
Budete tam chtít vložit klíč 'a', vypočítáte jeho hash, třeba 32745, a ten převedete do rozsahu hashtabulky, třeba modulo 4, takže vám vyjde index do hashovací tabulky 1. Takže klíč uložíte:
hashtable[0] = ();
hashtable[1] = ('a');
hashtable[2] = ();
hashtable[3] = ();
Pak budete chtít vložit klíč 'b', hash 126, index do hashovací tabulky 2:
hashtable[0] = ();
hashtable[1] = ('a');
hashtable[2] = ('b');
hashtable[3] = ();
Klíč 'c', hash 8293121, index do hashovací tabulky 1:
hashtable[0] = ();
hashtable[1] = ('a', 'c');
hashtable[2] = ('b');
hashtable[3] = ();
Vidíte, že tam došlo ke kolizi hashů (respektive až těch indexů v hashtabulce), takže pro hash 1 mám uložené dva různé klíče.
Když teď budu chtít v mapě najít klíč 'd', určím jeho hash 172340, index je 0, takže si v konstantním čase v hashtabulce najdu řádek s indexem 0:
hashtable[0] = (); //nalezený řádek v tabulce
hashtable[1] = ('a', 'c');
hashtable[2] = ('b');
hashtable[3] = ();
Vidím, že seznam klíčů je prázdný, tedy klíč 'd' v mapě není. Kdyby mi vyšel index 1, musím klíč hledat v té množině ('a', 'c'), a teprve pokud by tohle byl nesetříděný seznam, bude mít toto hledání lineární složitost. Tohle už je ale implementační detail, který může být v různých implementacích řešený různě. Podstatný pro hashovací tabulku je ten „trik“ že hash je přímo indexem pole a tudíž jeho vyhledání má konstantní časovou složitost.
-
Pokud je bucketů méně než možných hashů (tj. vždy), tak v případě kolize nemají všechny prvky stejný hash (kolize je na úrovni indexu bucketu). Takže se dá porovnávat ten hash samotný.
Navíc, pokud mají dva prvky stejný hash klíče, tak se z hlediska kolekcí jedná o ten samý prvek. Tj dojde k přepsání hodnoty pro ten klíč a žádná kolize nenastane.
Nikoli, dva prvky se stejným hashem jsou i z pohledu kolekcí pořád dva různé prvky. To, že může dojít ke kolizi, je základní princip hashe – a pro ukládání dat do hashtabulky se nepoužívají kryptograficky silné hashovací funkce, takže k těm kolizím reálně dochází a počítá se s nimi.
Máte pravdu, že v praxi může dojít ke dvěma typům kolizí – kolizi hashů, a kolizi indexů bucketu. To už je ale spíš otázka praktické implementace. V teorii je výpočet hashe záležitostí té hashtabulky, protože to ona ten hash potřebuje a objekt ukládaný do hashtabulky teoreticky nemusí nic o nějakém hashi vědět. Tím pádem si hashtabulka spočítá už rovnou hash o správné velikosti, aby šel rovnou použít jako index do té hashtabulky. Proto se v případě hashtabulky tomu indexu říká i hash. Ale třeba v Javě je to implementováno tak, jak popisujete – tj. výpočet hashe je (objektově nečistě) implementován přímo v každém objektu, tj. výpočet hashe vrací hash o nějaké univerzální velikosti (konkrétně integeru), a HashMap nebo HashSet si tenhle univerzální hash musí následně převést do rozsahu odpovídajícího aktuální velikosti hashtabulky (pole).
-
Navíc, pokud mají dva prvky stejný hash klíče, tak se z hlediska kolekcí jedná o ten samý prvek.
Ne.
Mno dobře, existuje speciální případ, kdy dvě různé hodnoty podle equals mají stejný hashCode. Nebyl jsem úplně přesný.
- If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
- It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
-
Nechápeš, pročež píšeš nesmysly. Představ si pole čísel v náhodném pořadí. Nalezení i-tého největšího prvku je lineární. A stejně lineární je to i v hashmapě, když jsou hodnotami čísla (na klíči nesejde). Nalezení mediánu je jen speciální případ nalezení i-tého největšího prvku.
Nesmysly tu píše spousta lidí, ale já ani MarSik to nejsme. i-tý největší prvek pole je úplně něco jiného, než i-tý prvek pole. i-tý největší prvek se vztahuje k hodnotám těch prvků, a mimo jiné předpokládá, že ty prvky umím porovnat a tedy seřadit. i-tý prvek se vztahuje k pořadí těch prvků v poli, v programátorském zápisu je to prostě pole.
V hashmapě to „stejně lineární“ není – a bylo by dobré, kdybyste si konečně zjistil, jak hashmapa funguje. Začněme tím, že v hashmapě jsou dvě struktury, ve kterých se prvek hledá. První struktura je hashtabulka, klíčová struktura pro hashmapu – je to pole, ve kterém index pole přímo odpovídá hashi klíče. Mám klíč, z něj vypočítám hash, ten hash převedu do rozsahu velikosti pole (např. hash modulo velikost pole), a tahle hodnota se použije přímo jako index té hashtabulky. Vyhledávání v té tabulce tedy není v lineárním čase, ale v konstantním – je to prostě přístup do pole podle indexu. No a protože může dojít ke kolizi hashů, tj. víc klíčů má stejný hash a mělo by být umístěných ve jedné položce té hashtabulky, musím mít možnost uložit na tu pozici ne jeden klíč, ale jejich množinu. Nejjednodušší je udělat tam spojový seznam, v něm se pak konkrétní hodnota opravdu hledá v lineárním čase, ale pokud klíče umím setřídit, můžu tam použít i jinou strukturu, ve které půjde rychleji hledat – třeba seřazený seznam nebo binární vyhledávací strom.
Představte si to třeba pro hashtabulku o velikosti čtyř prvků. Prázdná vypadá takhle:
hashtable[0] = ();
hashtable[1] = ();
hashtable[2] = ();
hashtable[3] = ();
Budete tam chtít vložit klíč 'a', vypočítáte jeho hash, třeba 32745, a ten převedete do rozsahu hashtabulky, třeba modulo 4, takže vám vyjde index do hashovací tabulky 1. Takže klíč uložíte:
hashtable[0] = ();
hashtable[1] = ('a');
hashtable[2] = ();
hashtable[3] = ();
Pak budete chtít vložit klíč 'b', hash 126, index do hashovací tabulky 2:
hashtable[0] = ();
hashtable[1] = ('a');
hashtable[2] = ('b');
hashtable[3] = ();
Klíč 'c', hash 8293121, index do hashovací tabulky 1:
hashtable[0] = ();
hashtable[1] = ('a', 'c');
hashtable[2] = ('b');
hashtable[3] = ();
Vidíte, že tam došlo ke kolizi hashů (respektive až těch indexů v hashtabulce), takže pro hash 1 mám uložené dva různé klíče.
Když teď budu chtít v mapě najít klíč 'd', určím jeho hash 172340, index je 0, takže si v konstantním čase v hashtabulce najdu řádek s indexem 0:
hashtable[0] = (); //nalezený řádek v tabulce
hashtable[1] = ('a', 'c');
hashtable[2] = ('b');
hashtable[3] = ();
Vidím, že seznam klíčů je prázdný, tedy klíč 'd' v mapě není. Kdyby mi vyšel index 1, musím klíč hledat v té množině ('a', 'c'), a teprve pokud by tohle byl nesetříděný seznam, bude mít toto hledání lineární složitost. Tohle už je ale implementační detail, který může být v různých implementacích řešený různě. Podstatný pro hashovací tabulku je ten „trik“ že hash je přímo indexem pole a tudíž jeho vyhledání má konstantní časovou složitost.
MarSik chápe, co je medián a o co javablbovi šlo.
-
Navíc, pokud mají dva prvky stejný hash klíče, tak se z hlediska kolekcí jedná o ten samý prvek.
Ne.
Mno dobře, existuje speciální případ, kdy dvě různé hodnoty podle equals mají stejný hashCode. Nebyl jsem úplně přesný.
- If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
- It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
To je právě princip hashtabulky, a proto se taky odpovídající pole dynamicky zvětšuje s růstem počtu prvků, protože hash%velikost pole se může rovnat dost často, když je pole malé a prvků hodně. Ono vůbec najít dobrou hašovací funkci je složité a formální důkaz "kvality hashe" bývá matematicky netriviální (věty kolem prvočísel a tak). Naštěstí to vše řeší standardní knihovna.
-
MarSik chápe, co je medián a o co javablbovi šlo.
A taky chápe, že když odpovídám 10xCoderovi, odpovídám 10xCoderovi a ne MarSikovi.
-
Jenom pár komentářů : a) nalezení i-teho největšího prvku v poli může mít O(log), pokud máte dovoleno to pole preusporadat - algoritmus je podobný quicksortu s tím, že pracujete vždy jen na jedné polovině a tu druhou ignorujet a b) nezapominat na výpočet toho hashe (zejména pro složité objekty), prosím - zažil jsem geniální nápady, kdy programátor navrhl velmi ďábelský výpočet nekolidujiciho hashe , který vedl
na amortizovanou časovou složitost mimo veškeré chápání . lidé
-
MarSik chápe, co je medián a o co javablbovi šlo.
A taky chápe, že když odpovídám 10xCoderovi, odpovídám 10xCoderovi a ne MarSikovi.
My víme, že jsi pomalejší, už se neztrapňuj ;)
-
Jenom pár komentářů : a) nalezení i-teho největšího prvku v poli může mít O(log), pokud máte dovoleno to pole preusporadat - algoritmus je podobný quicksortu s tím, že pracujete vždy jen na jedné polovině a tu druhou ignorujet a b) nezapominat na výpočet toho hashe (zejména pro složité objekty), prosím - zažil jsem geniální nápady, kdy programátor navrhl velmi ďábelský výpočet nekolidujiciho hashe , který vedl
na amortizovanou časovou složitost mimo veškeré chápání . lidé
a) To asi nebude nejhorší složitost, ne? Ta je O(n).
b) Je třeba myslet, no.
-
Ad a) moje chyba, ja myslel na quickselect, akorát jsem si to popletl ještě s něčím jiným, co teď řeším. Na vysvětlení dodávám, že mám brzké ráno
-
Ad a) moje chyba, ja myslel na quickselect, akorát jsem si to popletl ještě s něčím jiným, co teď řeším. Na vysvětlení dodávám, že mám brzké ráno
V poho. Aspoň se teď spousta místních dověděla, že nějaký quickselect existuje :)