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