Datové struktury a stromy v Javě

[Jonas]

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.

[Reklama]

[adsfasdfasdfasdf]

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

[anonym]

Najdi si datovou strukturu, např. LinkedList, ArrayList, HashMap, dej to do googlu a podívej se na stackoverflow. Žádný lepší rozbor asi nenajdeš.

[Phi]

Anglická wikipedie.

[adsfasdfasdfasdf]

uplny zaklad v cestine

https://java.vse.cz/pdf/skripta-datoveStruktury.pdf

[Reklama]

[Phi]

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.

[MarSik]

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

[anonym]

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)

[anonym]

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 

[kv]

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.

[kv]

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.

[MarSik]

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

[ded.kenedy]

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.

[Jenda]

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.

[anonym]

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š.