Datové struktury a stromy v Javě

anonym

Re:Datové struktury a stromy v Javě
« Odpověď #15 kdy: 21. 02. 2018, 18:27:19 »
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š.


gll

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

anonym

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

anonym

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

gll

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


anonym

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

anonym

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

anonym

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

Labrat

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

ded.kenedy

Re:Datové struktury a stromy v Javě
« Odpověď #24 kdy: 21. 02. 2018, 19:13:30 »
Oc mensi znalosti o to vic sebevedomi (a prispevku).

Citace
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?

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

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




Jenda

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

anonym

Re:Datové struktury a stromy v Javě
« Odpověď #26 kdy: 21. 02. 2018, 19:25:06 »
Oc mensi znalosti o to vic sebevedomi (a prispevku).

Citace
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í:
Citace
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.

anonym

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

Labrat

Re:Datové struktury a stromy v Javě
« Odpověď #28 kdy: 21. 02. 2018, 20:11:17 »
Oc mensi znalosti o to vic sebevedomi (a prispevku).

Citace
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í:
Citace
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 ;)

anonym

Re:Datové struktury a stromy v Javě
« Odpověď #29 kdy: 21. 02. 2018, 20:30:13 »
Jak ubohé a laciné  ;)