Re: Tablica int i usuwanie duplikatów

Newsgroups	pl.comp.programming
Date	2015-09-19 09:58 -0700
References	(19 earlier) <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> <mtk1ej$581$1@node1.news.atman.pl>
Message-ID	<06313417-a986-4d9a-a5aa-1eb3f65d4dbe@googlegroups.com> (permalink)
Subject	Re: Tablica int i usuwanie duplikatów
From	"M.M." <mmarszik@gmail.com>

Show all headers | View raw

On Saturday, September 19, 2015 at 6:10:59 PM UTC+2, bartekltg wrote:
> 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.
Tutaj miałem te obawy:
for (int i=0; i<100000/size+1;i++)
    tab.erase( f( tab.begin(),tab.end() ), tab.end()  );


> > 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 ;->
Etam :)


> > 4) lepsze rozwiązanie if( zero )
> 
> No tak, zero to całkiem poprawna wartość inta;>
> Dorzuć kilka zer do testowej tablicy, nie działa.
To się gdzieś rypłem, ale na wydajność to zbytnio nie
wpływa.



> Nagmatwałeś troche z różną ilośćią zer;-)
Był błąd, powinno być tak:
    for( int i=0 ; i<size ; i++ ) {
        if( t[i] != 0 ) {
            if( ! exist_mm( t[i] , u , s2) )
                t[size2++] = t[i];
        } else if( !zero ) {
            t[size2++] = 0;
            zero = true;
        }
    }



> po odgmatwaniu widać, że ręczna hashmapa jest kilkanaście(!)*
> razy szybsze. No to śledztwo:
> 
> Tochę porównujemy jakbłka z gruszkami.
No ale jaka wygoda w programowaniu :D


> 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, 
Hmmm ja bym się spodziewał się max 1.5 raza.


> 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.
Nie wiem co jest bardziej kosztowne. Ciągły if(zero), czy dodatkowa 
tablica bitów. Z tablicą bitów, w przypadku mocno zapełnionej 
tablicy, można przeskoczyć 64 zapełnienia w jednym ifie.

U mnie samoróbka (po zmianie funkcji hash i poprawieniu zer) działa
około 3 razy szybciej niż sortowanie i uniq.

http://pastebin.com/bEat8KH2

samorobka
poprawność:
12 457 0 1 56 89 11 55 
100 zajelo 2.794e-06s
1000 zajelo 1.986e-05s
10000 zajelo 0.000210824s
100000 zajelo 0.00289853s
1000000 zajelo 0.0475682s
10000000 zajelo 0.460168s
100000000 zajelo 4.75097s

hashmapa budowana
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.5469e-05s
1000 zajelo 0.000191005s
10000 zajelo 0.00231907s
100000 zajelo 0.0382351s
1000000 zajelo 0.791762s
10000000 zajelo 9.07928s
zbior budowany
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.4478e-05s
1000 zajelo 0.000254404s
10000 zajelo 0.00330699s
100000 zajelo 0.0680503s
1000000 zajelo 1.4365s
10000000 zajelo 23.5209s
hashmapa usuwana 
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.6489e-05s
1000 zajelo 0.000204336s
10000 zajelo 0.00230099s
100000 zajelo 0.0386139s
1000000 zajelo 0.687652s
10000000 zajelo 7.9165s
sortowanie 
poprawność:
1 11 12 55 56 89 457 
100 zajelo 6.077e-06s
1000 zajelo 5.4831e-05s
10000 zajelo 0.000708904s
100000 zajelo 0.00844671s
1000000 zajelo 0.100287s
10000000 zajelo 1.16515s
100000000 zajelo 13.3513s

sortowanie stab
poprawność:
12 457 1 56 89 11 55 
100 zajelo 1.053e-05s
1000 zajelo 0.000133041s
10000 zajelo 0.00170499s
100000 zajelo 0.0232212s
1000000 zajelo 0.395624s
10000000 zajelo 7.17122s


> *) 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.
Możne domyślnie ma też kiepską funkcje hash? QT ma bardzo
kiepską. std - nie wiem.

Pozdrawiam

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