-
Data: 2015-09-19 18:58:28
Temat: Re: Tablica int i usuwanie duplikatów
Od: "M.M." <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]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
Następne wpisy z tego wątku
- 19.09.15 20:44 bartekltg
- 19.09.15 20:45 slawek
- 19.09.15 20:52 bartekltg
- 19.09.15 21:01 bartekltg
- 20.09.15 16:27 slawek
- 20.09.15 17:14 bartekltg
- 21.09.15 08:09 Tomasz Kaczanowski
- 22.09.15 13:43 M.M.
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
Najnowsze wątki
- 2025-02-10 Spalił się spaliniak
- 2025-02-10 zarowka wifi - z sensowna apka lub lepiej albo lokalnie lub przez web. I zeby harmonogram miala
- 2025-02-10 Chrzanów => Programista NodeJS <=
- 2025-02-10 Kraków => DevOps Engineer (Junior or Regular level) <=
- 2025-02-10 Dlaczego takie preferencje banków?
- 2025-02-10 Białystok => iOS Developer (Swift) <=
- 2025-02-10 Mińsk Mazowiecki => Team Lead / Tribe Lead FrontEnd <=
- 2025-02-10 Białystok => System Architect (Java background) <=
- 2025-02-10 Współczesne mierniki zniekształceń nieliniowych THD audio, produkują jakieś?
- 2025-02-10 Szczecin => Senior Field Sales (system ERP) <=
- 2025-02-10 Gliwice => Business Development Manager - Dział Sieci i Bezpieczeńst
- 2025-02-10 Chrzanów => Specjalista ds. public relations <=
- 2025-02-10 Chrzanów => NodeJS Developer <=
- 2025-02-10 Warszawa => JavaScript / Node / Fullstack Developer <=
- 2025-02-10 Gliwice => Ekspert IT (obszar systemów sieciowych) <=