W dniu poniedziałek, 15 października 2012 00:54:24 UTC+2 użytkownik bartekltg
napisał:
> W dniu 2012-10-15 00:43, kenobi pisze:
>
>
>
> > wyniki moich pomiarow w stosunku do qsorta z clib
>
> >
>
> > //tab_size qsort komb-hist
>
>
>
> Nie napisałeś, czym jest komb-hist.
> Jakiś kod, skoro już się bawimy.
>
>
komb-hist czyli kombinowany kasperski, (kasperki
kombinowany 2-pozycyjnie)

ten sam kod

void sortowanie_histogramowe_kombinowane_2pozycyjnie_test
()
{


for (int i=0; i<histogram_size; i++) histogram[i] = 0;
for (int i=0; i<tab_size; i++) histogram[ tab[i] & 0xffff ] ++;
for (int i=1; i<histogram_size; i++) histogram[i] += histogram[i-1];

for (int i=0; i<tab_size; i++) temp[ --histogram[ tab[i] & 0xffff ] ] =
tab[i];

for (int i=0; i<histogram_size; i++) histogram[i]=0;
for (int i=0; i<tab_size; i++) histogram[ (temp[i]>>shift) ]++;
for (int i=1; i<histogram_size; i++) histogram[i]+=histogram[i-1];

for (int i=tab_size-1; i>=0; i--) tab[--histogram[ temp[i]>>shift ]] =
temp[i];


}


ew probowalem uzyc dwu histogramow i zliczac w jednej petli

for (int i=0; i<tab_size; i++)
{
int w = tab[i];
histogram[ w & 0xffff ] ++;
histogram2[ w >> 16 ] ++;
}

moze bylo drobine (1/40) szybsze (pojedyncze wyniki oscyluja
a nie mierzylem w petli)

a jak z wielokrotnym sortowaniem - np 8-pozycyjnym
dla stringow char[32] ? nie byloby to tez szybsze
dla 'zageszczonych' stringow ?


>
> >
>
> > //100 20 u 800 u
> > //1 tys 250 u 1000 u
> > //10 tys 3.3 m 1.2 m
> > //100 tys 40 m 20 m
> > //1 mln 600 m 350 m
> > //10 mln 6.2 s 3.9 s
>
> >
>
> > niecale 2 razy szybsze :/ no ale to jest
>
>
>
> Jakby było uniwersalne (czyli wersja "kombinowana")
>
> i 20 razy szybsze, byłoby w bibliotekach.
>
>
>
> pzdr
>
> bartekltg