Datové struktury a stromy v Javě

Labrat

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


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

Y'

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

Labrat

Re:Datové struktury a stromy v Javě
« Odpověď #63 kdy: 23. 02. 2018, 14:22:49 »
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 ;)

Labrat

Re:Datové struktury a stromy v Javě
« Odpověď #64 kdy: 23. 02. 2018, 14:24:40 »
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.


y,

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

Labrat

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