W dniu niedziela, 14 października 2012 22:51:46 UTC+2 użytkownik kenobi napisał:
> W dniu niedziela, 14 października 2012 22:19:08 UTC+2 użytkownik bartekltg napisał:
>
> > W dniu 2012-10-14 20:01, bartekltg pisze:
>
> >
>
> > >> w tym drugim wypadku (z intami) - jak dokladnie?
>
> >
>
> > >
>
> >
>
> > > Najpierw dla 2 niższych bajtów, potem dla 2 wyzszych.
>
> >
>
> > > Tablica pomocnicza tylko jedna, raz z oryginału lecimy
>
> >
>
> > > na pomocniczą, drugim razem z powrotem.
>
> >
>
> > >
>
> >
>
> > >> (kod w c) bo to jest druga czesc tego o czym ja tu pisze
>
> >
>
> > >
>
> >
>
> > > Mam Ci kod napisać? A za ile;>
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > Niech będzie dzień dobroci.
>
> >
>
> > Przetestowane, porównane z std::sort
>
> >
>
> > Na przedziale n 10^5 - 10^7 przewaga 2 do 3.5 raza
>
> >
>
> > szybsze. Co ciekawe, przewaga pozycyjnego od pewnego
>
> >
>
> > momentu maleje.
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > void pozycyjne(unsigned int * tab, int n)
>
> >
>
> > {
>
> >
>
> > const int shift = 16;
>
> >
>
> > const int K = 1<<shift;
>
> >
>
> >
>
> >
>
> > int * h = new int [K];
>
> >
>
> > unsigned int * temp = new unsigned int [n];
>
> >
>
> >
>
> >
>
> >
>
> >
>
> > for (int j=0;j<K;j++) //zerowanie
>
> >
>
> > h[j]=0;
>
> >
>
> >
>
> >
>
> > for (int j=0;j<n;j++)//zliczanie wystąpień
>
> >
>
> > h[(unsigned short)(tab[j])]++;
>
> >
>
> >
>
> >
>
> > for (int j=1;j<K;j++) //akumulacja/zmiana liczby wystąpień
>
> >
>
> > h[j]+=h[j-1]; //na indeksy
>
> >
>
> >
>
> >
>
> > for (int j=0;j<n;j++)//kopiowanie
>
> >
>
> > {
>
> >
>
> > temp[--h[(unsigned short)tab[j]]]=tab[j];
>
> >
>
> > }
>
> >
>
> > ///////////faza druga
>
> >
>
> > for (int j=0;j<K;j++) //zerowanie
>
> >
>
> > h[j]=0;
>
> >
>
> >
>
> >
>
> > for (int j=0;j<n;j++)//zliczanie wystąpień
>
> >
>
> > h[(unsigned short)(temp[j]>>shift)]++;
>
> >
>
> >
>
> >
>
> > for (int j=1;j<K;j++) //akumulacja/zmiana liczby wystąpień
>
> >
>
> > h[j]+=h[j-1]; //na indeksy
>
> >
>
> >
>
> >
>
> > for (int j=n-1;j>=0;j--)//kopiowanie
>
> >
>
> > {
>
> >
>
> > tab[--h[(unsigned short)temp[j]>>shift]]=temp[j];
>
> >
>
> > }
>
> >
>
> >
>
> >
>
> > delete[]temp;
>
> >
>
> > delete[]h;
>
> >
>
> >
>
> >
>
> > }
>
> >
>
> >
>
> nie rozumiem tego zlozenia, jak sortowanie tego
>
> co bylo posortowane po niskiej polowie po wysokiej czesci zlozy sie tak by wszystko
bylo ok?


w kazdym razie jesli to nie ma bledu i dziala
to jest to sprytny kawalek kodu - dziwne jednak jakoby to mialo byc tylko 2-3 razy
szybsze, new
mona wyrzucic i zrobic histogramy na statycznych tablicach