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. 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
4) lepsze rozwiązanie if( zero )
Rzecz jasna, też nie wiem czy nic nie spartoliłem, macie kod do
sprawdzenia:
http://pastebin.com/uRAqi8iv

Wyniki:

samorobka
poprawność:
12 457 1 56 89 11 55
100 zajelo 4.551e-06s
1000 zajelo 2.9805e-05s
10000 zajelo 0.000306844s
100000 zajelo 0.004824s
1000000 zajelo 0.050433s
10000000 zajelo 0.564702s
100000000 zajelo 6.84356s // najlepszy wynik

hashmapa budowana
poprawność:
12 457 1 56 89 11 55
100 zajelo 2.5173e-05s
1000 zajelo 0.000193544s
10000 zajelo 0.00218883s
100000 zajelo 0.0375231s
1000000 zajelo 0.797666s
10000000 zajelo 9.25089s
zbior budowany
poprawność:
12 457 1 56 89 11 55
100 zajelo 2.7255e-05s
1000 zajelo 0.000254757s
10000 zajelo 0.00330752s
100000 zajelo 0.0667916s
1000000 zajelo 1.46435s
10000000 zajelo 23.8021s
hashmapa usuwana
poprawność:
12 457 1 56 89 11 55
100 zajelo 2.0964e-05s
1000 zajelo 0.000203064s
10000 zajelo 0.002271s
100000 zajelo 0.0400408s
1000000 zajelo 0.68298s
10000000 zajelo 7.91133s
sortowanie
poprawność:
1 11 12 55 56 89 457
100 zajelo 4.154e-06s
1000 zajelo 5.4322e-05s
10000 zajelo 0.00068978s
100000 zajelo 0.00846882s
1000000 zajelo 0.100396s
10000000 zajelo 1.16484s
100000000 zajelo 13.3129s

sortowanie stab
poprawność:
12 457 1 56 89 11 55
100 zajelo 1.2285e-05s
1000 zajelo 0.000156857s
10000 zajelo 0.00193924s
100000 zajelo 0.023655s
1000000 zajelo 0.394504s
10000000 zajelo 7.24644s


> hashmapa budowana
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 12 457 1 56 89 11 55
> szybkość
> 10 zajelo 1.206e-06s
> 100 zajelo 2.12195e-05s
> 1000 zajelo 0.00019574s
> 10000 zajelo 0.00224614s
> 100000 zajelo 0.0319085s
> 1000000 zajelo 0.447895s
> 10000000 zajelo 7.09252s
>
> zbior budowany
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 12 457 1 56 89 11 55
> szybkość
> 10 zajelo 6.55151e-07s
> 100 zajelo 1.02252e-05s
> 1000 zajelo 0.000142235s
> 10000 zajelo 0.00210293s
> 100000 zajelo 0.0458803s
> 1000000 zajelo 0.809938s
> 10000000 zajelo 14.873s
>
> hashmapa usuwana
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 12 457 1 56 89 11 55
> szybkość
> 10 zajelo 1.7566e-06s
> 100 zajelo 2.02052e-05s
> 1000 zajelo 0.000217613s
> 10000 zajelo 0.00229402s
> 100000 zajelo 0.0311955s
> 1000000 zajelo 0.484313s
> 10000000 zajelo 5.8356s
>
> sortowanie
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 1 11 12 55 56 89 457
> szybkość
> 10 zajelo 5.79164e-08s
> 100 zajelo 8.72629e-07s
> 1000 zajelo 1.14487e-05s
> 10000 zajelo 0.000183957s
> 100000 zajelo 0.00351675s
> 1000000 zajelo 0.0574259s
> 10000000 zajelo 0.73433s
>
> sortowanie stab
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 12 457 1 56 89 11 55
> szybkość
> 10 zajelo 2.14358e-07s
> 100 zajelo 3.83037e-06s
> 1000 zajelo 7.91519e-05s
> 10000 zajelo 0.00108764s
> 100000 zajelo 0.0153062s
> 1000000 zajelo 0.267471s
> 10000000 zajelo 5.37913s


Pozdrawiam