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