Re: Tablica int i usuwanie duplikatów

From	bartekltg <bartekltg@gmail.com>
Newsgroups	pl.comp.programming
Subject	Re: Tablica int i usuwanie duplikatów
Date	2015-09-19 18:10 +0200
Organization	ATMAN - ATM S.A.
Message-ID	<mtk1ej$581$1@node1.news.atman.pl> (permalink)
References	(18 earlier) <13goui39dxzb2.1kw5grc7j0y14.dlg@40tude.net> <mthp48$epf$1@node2.news.atman.pl> <1amtzmln34a1o$.kdovd8ebh5p5$.dlg@40tude.net> <mticic$1e6$1@node2.news.atman.pl> <6d350592-2efd-448d-ba48-66154113be54@googlegroups.com>

Show all headers | View raw

On 19.09.2015 13:35, M.M. wrote:
> On Saturday, September 19, 2015 at 3:08:29 AM UTC+2, bartekltg wrote:
>> http://pastebin.com/Bd53Qj2e
>>
>> cztery wersje, z hashmapą, ze zbiorem na drzewie, z hashmapą,
>> ale wstepnie wypelnioną i opróżnianą, oraz wersja naiwna.
>> Do tego wersja z sortowaniem, która biła na głowę wszystko;-)
>>
>> Dalej w kodzie nie ma nic ciekawego a jest brzydki:]
>>
>> M.M jednak miał niezłą intuicję, algorytm naiwny trzyma się jako
>> tako do 1000 liczb! Przynajmniej w porównaniu do kontenerowych,
>> w stosunku do sortowania to przebija już dla 10.
> Jeśli algorytmy się przełączają na inne wersje gdy jest
> mało elementów, to moja intuicja nie ma tutaj zastosowania :)
>
>
>
>
>> Sortowanie diała tak dobrze, że dorzuciłem gdzieś wpominaną wersję,
>> gdzie kopiuję tablice, sortuję, wyszukuję w niej przetwarzanego
>> elementu i indeksu tego elementu używam na tablicy 'czy już było'.
>> Szybsze, ale nie tak jak samo sortowanie i 'unique'.
>>
>> Czy gdzieś nie ma błędów, nie wiem, specjalnie mocno nie testowałem ;-)
> Tylko nie byłem pewny, czy nie sortujesz już częściowo posortowanych
> elementów.


Przecież tablica była losowana, dlaczego miałaby być posorotwana?

     random_device rd;
     mt19937 gen(rd());
....
         generate(tab.begin(), tab.end(), gen);

Przez każdym pojedyńczym pomiarem.

> Lekko zmieniłem Twój kod i dodałem moją samoróbkę. Moją
> samoróbkę można jeszcze ze dwa razy przyspieszyć przez:
> 1) lepszą kompilację
> 2) profilowanie
> 3) lepszą funkcję hash


Napisać to w c++, nie C ;->


> 4) lepsze rozwiązanie if( zero )

No tak, zero to całkiem poprawna wartość inta;>
Dorzuć kilka zer do testowej tablicy, nie działa.



> Rzecz jasna, też nie wiem czy nic nie spartoliłem, macie kod do
> sprawdzenia:
> http://pastebin.com/uRAqi8iv
>
> Wyniki:

Nagmatwałeś troche z różną ilośćią zer;-)
po odgmatwaniu widać, że ręczna hashmapa jest kilkanaście(!)*
razy szybsze. No to śledztwo:

Tochę porównujemy jakbłka z gruszkami.
"
  (unsigned int)(size/2*5+2);

     cout<<"s2 "<<s2<<endl;

     int *u = new int[s2];
"

OK, to ja też mogę wpisać:
iter stable_unique_1 ( iter first, iter last )
{
     unordered_set<int> temp; //zbiór użytych
     temp.rehash ( distance(first, last)*5/2+2 );  // alokuje wstępnie 
nieco pamieci.

i wtedy nie musimy co chwila robić realokacji i rehashowania,
gotowa hashmapa jest 2.5 raza wolniejsza. I to jest spodziewany
wynik, bo tamta hashmapa rozwiązuje kolizje tworząc listę,
a Twoja stosuje sztuczkę z wartośćią specjalną . Jeśli informację
o zajętości będziesz trzymał w osobnej tablicy, różnica ciut spadnie.


samorobka
100 zajelo 3.4711e-05s
1000 zajelo 0.000145689s
10000 zajelo 0.000330489s
100000 zajelo 0.00406414s
1000000 zajelo 0.0826325s
10000000 zajelo 0.97905s

hashmapa budowana
10 zajelo 1.18089e-06s
100 zajelo 1.31643e-05s
1000 zajelo 0.000130519s
10000 zajelo 0.00139489s
100000 zajelo 0.0192994s
1000000 zajelo 0.233072s
10000000 zajelo 2.65135s

zbior budowany
10 zajelo 6.43753e-07s
100 zajelo 1.03399e-05s
1000 zajelo 0.000142441s
10000 zajelo 0.00209884s
100000 zajelo 0.0432259s
1000000 zajelo 0.777911s
10000000 zajelo 14.2428s

hashmapa usuwana
10 zajelo 1.90731e-06s
100 zajelo 1.9725e-05s
1000 zajelo 0.000195841s
10000 zajelo 0.00210182s
100000 zajelo 0.0296034s
1000000 zajelo 0.389643s
10000000 zajelo 4.44893s

sortowanie
10 zajelo 5.58256e-08s
100 zajelo 8.79121e-07s
1000 zajelo 1.12299e-05s
10000 zajelo 0.000183867s
100000 zajelo 0.00352831s
1000000 zajelo 0.0571969s
10000000 zajelo 0.732117s

sortowanie stab
10 zajelo 2.3127e-07s
100 zajelo 4.69011e-06s
1000 zajelo 8.10539e-05s
10000 zajelo 0.00110062s
100000 zajelo 0.0153352s
1000000 zajelo 0.256625s
10000000 zajelo 5.16851s



*) Domyślnie unordered set ma load_factor 1!
Po zmianie go na przyzwoitszy:
temp.max_load_factor(2.0/5.0);
czas spadł do 4.5 sekund z hakiem. Z grubsza 2 razy więcej
niż z przygotowaną tablicą (tyle się należy spodziewać).
Wiekszosć zwolnienia poprzednio było więc z podowu dużej
liczby kolizji.


pzdr
bartekltg

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-14 21:56 +0200
  Re: Tablica int i usuwanie duplikatów Adam Klobukowski <adamklobukowski@gmail.com> - 2015-09-14 13:50 -0700
  Re: Tablica int i usuwanie duplikatów witek <witek7205@gazeta.pl.invalid> - 2015-09-14 20:23 -0500
    Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 04:10 +0200
  Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 04:10 +0200
    Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-15 09:32 +0200
      Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-15 10:50 +0200
        Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-15 12:01 +0200
          Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-15 14:53 +0200
      Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 14:16 +0200
      Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-16 07:21 +0200
        Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 07:38 +0200
          Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-16 10:57 +0200
            Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 11:34 +0200
              Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 03:31 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 12:52 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 05:03 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 16:49 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 17:31 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 17:58 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 18:25 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 18:28 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 10:41 -0700
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 19:57 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 22:46 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 23:27 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-17 00:23 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-17 05:37 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 00:18 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-18 09:07 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 18:20 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 20:22 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 20:47 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 21:01 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 21:36 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 22:50 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 03:08 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 11:34 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 20:52 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 04:35 -0700
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 04:57 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 14:43 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 05:50 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 15:08 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 06:23 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 15:44 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:20 +0200
                Re: Tablica int i usuwanie duplikatów Tomasz Kaczanowski <kaczus@dowyciecia_poczta.onet.pl> - 2015-09-21 08:09 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:13 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:10 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 09:58 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 20:44 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-22 04:43 -0700
              Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-17 08:12 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-17 15:14 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-17 16:37 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-18 07:22 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 15:15 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-19 20:45 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 21:01 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-20 16:27 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-20 17:14 +0200
          Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 11:05 +0200
            Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 11:40 +0200
              Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 12:05 +0200
  Re: Tablica int i usuwanie duplikatów Sebastian Biały <heby@poczta.onet.pl> - 2015-09-16 19:11 +0200
    Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 10:46 -0700
      Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 19:55 +0200

csiph-web