On Tue, 15 Sep 2015 09:32:50 +0200, szemrany <s...@o...off>
wrote:
> I naprawdę algorytmika niczego lepszego nie wymyśliła?

Po prostu zlicz wystąpienia. Dla skończonego zbioru int'ów złożoność
obliczeniowa O(N).

do góry

On 16.09.2015 07:21, slawek wrote:
> On Tue, 15 Sep 2015 09:32:50 +0200, szemrany <s...@o...off> wrote:
>> I naprawdę algorytmika niczego lepszego nie wymyśliła?
>
> Po prostu zlicz wystąpienia. Dla skończonego zbioru int'ów złożoność
> obliczeniowa O(N).

To jest ogólnie nienajgorszy pomysł (padł w wątku trzeci raz),
ale pomijasz koszmarną ilość szczegółów, jak zliczać ;-)

pzdr
bartekltg

do góry

On Wed, 16 Sep 2015 07:38:10 +0200, bartekltg <b...@g...com>
wrote:
> ale pomijasz koszmarną ilość szczegółów, jak zliczać ;-)

Normalnie; zero, mnóstwo. ;)

do góry

Użytkownik "bartekltg" <b...@g...com> napisał:

> jak zliczać ;-)

Właśnie. W tym cały ambaras :)

AK


---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe
Avast.
https://www.avast.com/antivirus

do góry

On 16.09.2015 10:57, slawek wrote:
> On Wed, 16 Sep 2015 07:38:10 +0200, bartekltg <b...@g...com> wrote:
>> ale pomijasz koszmarną ilość szczegółów, jak zliczać ;-)
>
> Normalnie; zero, mnóstwo

Dlatego proponowałem (unordered_)set zamiast (...)map.
Jest/nie ma w pomocniczym zbiorze.

> ;)

Ty już nie udawaj, ze nie wiesz, o co pytam ;-)

pzdr
bartekltg

do góry

On 16.09.2015 11:05, AK wrote:
> Użytkownik "bartekltg" <b...@g...com> napisał:
>
>> jak zliczać ;-)
>
> Właśnie. W tym cały ambaras :)

Przejrzałem pobieżnie Twoje linki o idealnym minilalnym hashu,
to wygląda na sporo roboty dla procesora (porównujemy do
sortowania i zwykłego haszowania z jakimś prostym rozwiązywaniem
kolizji), jeśli potem każdy element odczytamy ~raz.


pzdr
bartekltg

do góry

Użytkownik "bartekltg" <b...@g...com> napisał:

> Przejrzałem pobieżnie Twoje linki o idealnym minilalnym hashu,
> to wygląda na sporo roboty dla procesora (porównujemy do
> sortowania i zwykłego haszowania z jakimś prostym rozwiązywaniem
> kolizji), jeśli potem każdy element odczytamy ~raz.

Nie no zgadza sie. Dlatego to sie nadaje glownie do ("statycznych") setow
typu slowa kluczowe j.prog czy jakis dispatrzer po nazwie dla z gory
okreslonych nazw itp.

Co nie zmienia faktu ze jest to rozwiazanie "prawie idelane" w sensie
zlozonosci O(x)

AK


---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe
Avast.
https://www.avast.com/antivirus

do góry

On Wednesday, September 16, 2015 at 11:34:13 AM UTC+2, bartekltg wrote:
> Dlatego proponowałem (unordered_)set zamiast (...)map.
> Jest/nie ma w pomocniczym zbiorze.
To jest najszybsza metoda w praktyce. Czasami możemy trafić na
dane, dla których funkcja hash da mnóstwo kolizji. Problem
kolizji trochę rekompensuje odpowiednia implementacja hash-table,
ponieważ można ją przeglądać tak jak lubi pamięć cache. W
przypadku RBTree nigdy nie jest przyjaźnie dla cache, ale
jest gwarancja N*Log(N) dla każdych danych.

Pozdrawiam

P.S.
Chyba w popularnych bibliotekach nie ma implementacji hash-table
która jest przyjazna dla pamięci cache, chyba trzeba samemu
wyrzeźbić. Szczególnie warto samemu, gdy wiemy z góry ile
będzie danych liczb.

do góry

On 16.09.2015 12:31, M.M. wrote:
> On Wednesday, September 16, 2015 at 11:34:13 AM UTC+2, bartekltg wrote:
>> Dlatego proponowałem (unordered_)set zamiast (...)map.
>> Jest/nie ma w pomocniczym zbiorze.
> To jest najszybsza metoda w praktyce. Czasami możemy trafić na
> dane, dla których funkcja hash da mnóstwo kolizji. Problem
> kolizji trochę rekompensuje odpowiednia implementacja hash-table,
> ponieważ można ją przeglądać tak jak lubi pamięć cache. W
> przypadku RBTree nigdy nie jest przyjaźnie dla cache, ale
> jest gwarancja N*Log(N) dla każdych danych.
>
> Pozdrawiam
>
> P.S.
> Chyba w popularnych bibliotekach nie ma implementacji hash-table
> która jest przyjazna dla pamięci cache, chyba trzeba samemu
> wyrzeźbić. Szczególnie warto samemu, gdy wiemy z góry ile
> będzie danych liczb.

w STD jest metoda łańcuchowa. Kiedyś nawet czyałem, że
za tym, że nie sosją jakiergoś adresowania otwartego
stoi za jakaś idealogia.

Parę razy natknąłem się na googlowe tablice mieszające
https://github.com/sparsehash/sparsehash
Kilka gatnków, do wyboru.

Stare, ale ciekawe porównanie:
http://incise.org/hash-table-benchmarks.html


Za to jakiś czas temu złapałem się na tym, że std:hash na intach
... zwraca argument. Jest różnowartośćiowa, ale dość słabo miesza:(



pzdr
bartekltg

do góry

On Wednesday, September 16, 2015 at 12:52:08 PM UTC+2, bartekltg wrote:
> On 16.09.2015 12:31, M.M. wrote:
> > On Wednesday, September 16, 2015 at 11:34:13 AM UTC+2, bartekltg wrote:
> >> Dlatego proponowałem (unordered_)set zamiast (...)map.
> >> Jest/nie ma w pomocniczym zbiorze.
> > To jest najszybsza metoda w praktyce. Czasami możemy trafić na
> > dane, dla których funkcja hash da mnóstwo kolizji. Problem
> > kolizji trochę rekompensuje odpowiednia implementacja hash-table,
> > ponieważ można ją przeglądać tak jak lubi pamięć cache. W
> > przypadku RBTree nigdy nie jest przyjaźnie dla cache, ale
> > jest gwarancja N*Log(N) dla każdych danych.
> >
> > Pozdrawiam
> >
> > P.S.
> > Chyba w popularnych bibliotekach nie ma implementacji hash-table
> > która jest przyjazna dla pamięci cache, chyba trzeba samemu
> > wyrzeźbić. Szczególnie warto samemu, gdy wiemy z góry ile
> > będzie danych liczb.
>
> w STD jest metoda łańcuchowa. Kiedyś nawet czyałem, że
> za tym, że nie sosją jakiergoś adresowania otwartego
> stoi za jakaś idealogia.
>
> Parę razy natknąłem się na googlowe tablice mieszające
> https://github.com/sparsehash/sparsehash
> Kilka gatnków, do wyboru.
>
> Stare, ale ciekawe porównanie:
> http://incise.org/hash-table-benchmarks.html
>
>
> Za to jakiś czas temu złapałem się na tym, że std:hash na intach
> ... zwraca argument. Jest różnowartośćiowa, ale dość słabo miesza:(


Dzięki za benchmarki. Widzę, że QHash ładnie tam wypada. Pamiętam właśnie, że
kiedyś wydziargałem swoją specjalistyczną hash-table i działała tylko
odrobinę szybciej niż qhash.

Pozdrawiam

do góry