Path: csiph.com!au2pb.net!feeder.erje.net!1.eu.feeder.erje.net!weretis.net!feeder4.news.weretis.net!feeder2.ecngs.de!ecngs!feeder.ecngs.de!81.171.118.62.MISMATCH!peer02.fr7!news.highwinds-media.com!newsfeed.neostrada.pl!unt-exc-01.news.neostrada.pl!newsfeed2.atman.pl!newsfeed.atman.pl!.POSTED!not-for-mail From: bartekltg Newsgroups: pl.comp.programming Subject: =?UTF-8?Q?Re:_Tablica_int_i_usuwanie_duplikat=c3=b3w?= Date: Wed, 16 Sep 2015 12:52:07 +0200 Organization: ATMAN - ATM S.A. Lines: 42 Message-ID: References: <3aivb8qrco1q$.13cffg23pn4pg.dlg@40tude.net> <50609ffa-fe60-473f-8adc-5be498ec3dc2@googlegroups.com> NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Trace: node2.news.atman.pl 1442400727 14483 89.73.81.145 (16 Sep 2015 10:52:07 GMT) X-Complaints-To: usenet@atman.pl NNTP-Posting-Date: Wed, 16 Sep 2015 10:52:07 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.2.0 In-Reply-To: <50609ffa-fe60-473f-8adc-5be498ec3dc2@googlegroups.com> X-Received-Bytes: 2627 X-Received-Body-CRC: 3769250486 Xref: csiph.com pl.comp.programming:27509 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