Datové struktury a stromy v Javě

Labrat

Re:Datové struktury a stromy v Javě
« Odpověď #30 kdy: 21. 02. 2018, 21:03:50 »
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.


tisnik

Re:Datové struktury a stromy v Javě
« Odpověď #31 kdy: 21. 02. 2018, 21:07:02 »
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 :-)

sdfasdfasfasfd

Re:Datové struktury a stromy v Javě
« Odpověď #32 kdy: 21. 02. 2018, 21:17:09 »
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.

Re:Datové struktury a stromy v Javě
« Odpověď #33 kdy: 21. 02. 2018, 21:55:29 »
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í.

Jonas

Re:Datové struktury a stromy v Javě
« Odpověď #34 kdy: 21. 02. 2018, 22:03:45 »
Citace
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 :)


tisnik

Re:Datové struktury a stromy v Javě
« Odpověď #35 kdy: 21. 02. 2018, 23:22:00 »
Citace
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á)

Jonas

Re:Datové struktury a stromy v Javě
« Odpověď #36 kdy: 22. 02. 2018, 00:10:50 »
Citace
(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 :)

Jenda

Re:Datové struktury a stromy v Javě
« Odpověď #37 kdy: 22. 02. 2018, 10:01:21 »
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.

tisnik

Re:Datové struktury a stromy v Javě
« Odpověď #38 kdy: 22. 02. 2018, 10:56:35 »
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.

MarSik

Re:Datové struktury a stromy v Javě
« Odpověď #39 kdy: 22. 02. 2018, 12:05:46 »
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

Labrat

Re:Datové struktury a stromy v Javě
« Odpověď #40 kdy: 22. 02. 2018, 13:27:03 »
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čí.

Někdo

Re:Datové struktury a stromy v Javě
« Odpověď #41 kdy: 22. 02. 2018, 14:04:46 »
Citace
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

Labrat

Re:Datové struktury a stromy v Javě
« Odpověď #42 kdy: 22. 02. 2018, 15:27:54 »
Citace
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.

Jenda

Re:Datové struktury a stromy v Javě
« Odpověď #43 kdy: 22. 02. 2018, 16:20:55 »
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.

Labrat

Re:Datové struktury a stromy v Javě
« Odpověď #44 kdy: 22. 02. 2018, 16:47:17 »
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.