W dniu niedziela, 14 października 2012 18:57:57 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 18:45, kenobi pisze:
>
>
>
> >
>
> > jak rozumiesz co mowie to moglbys sie
>
> > do tego odniesc
>
>
>
> Ty nie masz zamiaru czytać (i to od paru
>
> postów i chyba 2 dni) to ja nie będę się
>
> produkował i przepisywał podręcznika.
>
>
>
> Załapałeś counting sorta. Chcesz go rozwinąć,
>
> ale bujasz się między stworzeniem z niego radix
>
> sorta (czyli kilkakrotnie przez zliczanie)
>
> i kubełkowego.
>
>
>
>
>
> > to inne pytanie ;) jakim algorytmem postortowalbys
>
> > 1) milion unsigned shortow
>
> > 2) milion unsigned intow ?
>
>
>
> Zależy od warunków. W normalnych: std::sort().
>
>
>
> W jakiś specyficznych, gdy to jest ważne
>
> i rzeczywiście tam siedzi wąskie gardło
>
> algorytmu, w przypadku [1] dałbym przez zliczanie
>
> (zwłaszcza, że nie wymagasz stabilności!),
>
> a w [2] zastanowiłbym się nad pozycyjnym
>
> (2 razy przez zliczanie).
>
>
>
> pzdr
>
> bartekltg
>
>
>
>
>
> Tak mi się przypomniało:
>
> http://en.wikipedia.org/wiki/Dutch_national_flag_pro
blem





wobec tego ze sa to wlasnie te metody o
ktorych mowie od samego poczatku nazywajac je
sposobem kasperskiego - wobec czego ty
oponujesz oprocz nazewnictwa ?

[ czy wczesniej nim zaczalem mowic o tych
metodach (nazywajac je metodami ksperskiego)
tez bys ich uzyl? czy jawily ci sie juz wczesniej
jako najprawdopodobniej jedyny powazny sposob w
podobnych wypadkach (zwlaszcza w tym pierwszym),
tak jak to wlasnie wyraznie naswietlil kasperski?

To jest pytanie pomocnicze majace na celu
ustelenie wobec czego ty oponujesz w stosunku
do kasperskiego

(Pytam bo jakies oponowanie jakby tu sie pojawilo
i komplenie serio nie wiem o co chodzi)

pozatym

w tym drugim wypadku (z intami) - jak dokladnie?
(kod w c) bo to jest druga czesc tego o czym ja tu pisze

do góry

tamte hasla przeczytalem ale sa to dosyc
ogolnikowe nazwy ogolnikowo zarysowanych
sposobow i nie precyzuja one dokladnie tego
o czym ja mowie - (wlasnie juz ta krytykowana
nazwa metoda kasperskiego o wiele dokladniej
mowi o co mi chodzi

do góry

W dniu 2012-10-14 19:43, kenobi pisze:

> wobec tego ze sa to wlasnie te metody o
> ktorych mowie od samego poczatku nazywajac je
> sposobem kasperskiego - wobec czego ty
> oponujesz oprocz nazewnictwa ?

Myleniem pozycyjnego z kubełkowym
i wymyślaniu od nowa pozycyjnego z błędem
w konstrukcji.

> [ czy wczesniej nim zaczalem mowic o tych
> metodach (nazywajac je metodami ksperskiego)
> tez bys ich uzyl?

W post wyżej wyspecyfikowanych okolicznościach
- oczywiście.

Ty nam nie pokazałeś nowego algorytmu. Podejrzewam,
że _wszyscy_ tu wiedzieli o jego istnieniu.

Zobacz zresztą na reakcję po tamtym poście.
Ludzie się albo póbują domyśleć, co tam napisałeś,
albo mówią 'no, ja 30 lat temu też się zachwycilem'.

> czy jawily ci sie juz wczesniej
> jako najprawdopodobniej jedyny powazny sposob w
> podobnych wypadkach (zwlaszcza w tym pierwszym),
> tak jak to wlasnie wyraznie naswietlil kasperski?

Dobrze się czujesz? Światopogląd Ci się obalił?
Ludzie zajmujący się programowaniem znają
zliczanie, a kasperski to antywirus.


> To jest pytanie pomocnicze majace na celu
> ustelenie wobec czego ty oponujesz w stosunku
> do kasperskiego

Kasperski wywołał kiepskie wrażenie*). Taki chłopek
roztropek z usenetu odkrywającego na nowo koło
i nie potrafiącego zrozumieć zadania na konkursie
i swojego błędu (skoro się nim chwali).

W dodatku bezczelnie oszukuje, pisząc nieprawde w ksiażce,
co już naświetlił Michoo. Co zresztą bardzo źle wróży
reszcie książki, skądinąd o interesującym temacie.

*) na podstawie tego fragmentu. Nadal nie wiem, kto to
jest.

> (Pytam bo jakies oponowanie jakby tu sie pojawilo
> i komplenie serio nie wiem o co chodzi)


> 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;>

Czytaj wiki, czytaj googla, pewnie bez trudu znajdziesz.

pzdr
bartekltg

do góry

W dniu 2012-10-14 19:56, kenobi pisze:
> (wlasnie juz ta krytykowana
> nazwa metoda kasperskiego o wiele dokladniej
> mowi o co mi chodzi

Jakim cudem mówi, jak odwołuje
sie do nazwiska, w dodatku kojarzącego się
co najwyżej z antywirusem?

Dobra, kończę ten jałowy temat, bo to bez sensu.

BTW, Póki nie zobaczę w sieci wiarygodnych źródeł
określających takim mianem ten algorytm, będę
ostentacyjnie nie rozumiał tej nazwy;)

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 20:01:19 UTC+2 użytkownik bartekltg napisał:
> W dniu 2012-10-14 19:43, kenobi pisze:
>
>
>
> > wobec tego ze sa to wlasnie te metody o
>
> > ktorych mowie od samego poczatku nazywajac je
>
> > sposobem kasperskiego - wobec czego ty
>
> > oponujesz oprocz nazewnictwa ?
>
>
>
> Myleniem pozycyjnego z kubełkowym
>
> i wymyślaniu od nowa pozycyjnego z błędem
>
> w konstrukcji.
>

w jaki sposob mylenie i z jakim bledem ?



>
>
> > [ czy wczesniej nim zaczalem mowic o tych
>
> > metodach (nazywajac je metodami ksperskiego)
>
> > tez bys ich uzyl?
>
>
>
> W post wyżej wyspecyfikowanych okolicznościach
>
> - oczywiście.
>
>
>
> Ty nam nie pokazałeś nowego algorytmu. Podejrzewam,
>
> że _wszyscy_ tu wiedzieli o jego istnieniu.
>
>
>
> Zobacz zresztą na reakcję po tamtym poście.
>
> Ludzie się albo póbują domyśleć, co tam napisałeś,
>
> albo mówią 'no, ja 30 lat temu też się zachwycilem'.
>
>
>
> > czy jawily ci sie juz wczesniej
>
> > jako najprawdopodobniej jedyny powazny sposob w
>
> > podobnych wypadkach (zwlaszcza w tym pierwszym),
>
> > tak jak to wlasnie wyraznie naswietlil kasperski?
>
>
>
> Dobrze się czujesz? Światopogląd Ci się obalił?
>
> Ludzie zajmujący się programowaniem znają
>
> zliczanie, a kasperski to antywirus.
>
>

no niezupelnie, spodziewam sie ze coponiektorzy
znaja zliczanie, ale mz do swiadomosci wielu
swiadomosc tego jak dobra to jest metoda niezbyt sie przetarła



>
>
>
> > To jest pytanie pomocnicze majace na celu
>
> > ustelenie wobec czego ty oponujesz w stosunku
>
> > do kasperskiego
>
>
>
> Kasperski wywołał kiepskie wrażenie*). Taki chłopek
>
> roztropek z usenetu odkrywającego na nowo koło
>
> i nie potrafiącego zrozumieć zadania na konkursie
>
> i swojego błędu (skoro się nim chwali).
>
>
>
> W dodatku bezczelnie oszukuje, pisząc nieprawde w ksiażce,
>
> co już naświetlił Michoo. Co zresztą bardzo źle wróży
>
> reszcie książki, skądinąd o interesującym temacie.
>

no nieladnie,

>
>
> *) na podstawie tego fragmentu. Nadal nie wiem, kto to
>
> jest.
>
>
>
> > (Pytam bo jakies oponowanie jakby tu sie pojawilo
>
> > i komplenie serio nie wiem o co chodzi)
>
>
>
>
>
> > 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;>
>
>
>
> Czytaj wiki, czytaj googla, pewnie bez trudu znajdziesz.
>
>
>
> pzdr
>
> bartekltg

do góry

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;

}

pzdr
bartekltg

do góry

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];
>

co tu robi to --h ? jest na pewno dobrze?


> }
>


> ///////////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;
>
>
>
> }
>
>
>
> pzdr
>
> bartekltg

do góry

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?

do góry

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

do góry

W dniu 2012-10-14 22:57, kenobi pisze:
> W dniu niedziela, 14 października 2012 22:51:46 UTC+2 użytkownik kenobi napisał:
>> ...użytkownik kenobi napisał:


>>> co tu robi to --h ? jest na pewno dobrze?

Na pewno jest dobrze.

W h trzymasz liczbę wystąpień.

Pod h[0] masz liczbę zer, pod h[1] liczbę jedynek

Robisz sumy częściowe
teraz pod h[0] nadal masz liczbę zer,
ale pod h[1] liczbę zer i jedynek. pod h[2] liczbe zer,
jedynek i dwójek.

Ta na co pokazuje temp[ h[2] ] ?
pokazuje na pierwsze miejsce _po_ ostatniej dwójce.
Czyli ostatnia dwójka powinna znaleśc się na miejscu
o jeden wcześniej.
Robimy --h[2], pod wynikiem wkłądamy co trzeba.

h pełni rolę _ruchomych_ wskaźników pokazujących,
gdzie układać daną liczbę.

Ok, przyznaje, nie jest to wersja edukacyjna,
i zawiera trochę 'chackierskich przedwczesnych
optymalizacji' i skrótowe konstrukcje.
Dopiero co się nimi zachwysałeś

być może
temp[--h[(unsigned short)tab[j]]]=tab[j];
->
kategoria = (unsigned short)tab[j];
--h[kategoria]; //przesuwamy wskażnik tablicy dla elementow kategorii
kategoria
indeks = h[kategoria];
temp[indeks] = tab[j]

byłaby czytelniejsza;)


>> nie rozumiem tego zlozenia, jak sortowanie tego
>>
>> co bylo posortowane po niskiej polowie po wysokiej czesci zlozy sie tak by
wszystko bylo ok?

_Sortowanie stabilne_. Jeśli w drugim sortowaniu dwa elementy są takie
same, to ich względna kolejność pozostanie taka sama jak po pierwszym.

> w kazdym razie jesli to nie ma bledu i dziala

Nie ma, działa.

> to jest to sprytny kawalek kodu - dziwne jednak jakoby to mialo byc tylko 2-3 razy
szybsze,

Bo tu przelatujemy po dużej tablicy 6 razy, a w qsorcie
log(N) razy. Log2(10^7) = 23 (tak naprawdę mniej, bo
końcówkę robi się inaczej, a do tego działa się bardziej
'lokalnie', co jest szybsze).

Dopiero co się szkicem tego algorytmu zachwycałeś.
Od szkicu do implementacji droga wiedzie przez
nieraz upierdliwe szczegóły;)

Drzewa AVL są w idei super. Ale weź na szybko zaimplementuj
równoważenie.

> new mona wyrzucic i zrobic histogramy na statycznych tablicach

Statyczna tablica na 40MB?

To nie jest nawet zły pomysł. To głupi pomysł.

Zrobiłem wersję z dodatkowym parametrem, buforem tworzonym
raz na zewnątrz (poza licznikiem czasu) i przekazywanym do środka.
Różnice były zbyt małe by warto było o nich wspominać,
więc nawet nie pisałem.

pzdr
bartekltg

do góry