eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingTablica int i usuwanie duplikatówRe: Tablica int i usuwanie duplikatów
  • 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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: