Dnia Sat, 13 Oct 2012 11:58:34 -0700, kenobi napisal:

> za jakis czas sobie klepne pewnie to uogolnienie, np dla 32 bit mozna
> pewnie w jednym przebiegu zrobic histogram na gornych bitach wygenerowac
> czesciowo uporzadkowany wynik i w kolejnym posortowac kawalki, albo tez i
> inaczej ladnie dobierajac po efektywnosci - w kazdym razie raczej da sie
> to uogolnic :U

Dla stringów też się da. Taki 8-bajtowy string to 2^64 tak jak int64
to 2^64 jak i float to 2^64. Ymmv, ale widzę morfizm, wystarczy uzupełnić
string zerami do najdłuższego, zera tak rzadko występują. Jedynie te
floaty mają jakieś NaNy i InfY, ale int się nadaje. A jak się zmienne
typu String wrzuci w histogram potem, to można histogramować po
intach zbudowanych ze znaków, robi się to raz, a nie z bajtów, wystarczy
jak wszystkiemu porównywalnemu walnąc raz przypisanie znaku do liczby,
znaki są znane, według lexykografii i jesteśmy w domu po jednym
przebiegu, chyba że wszystkie przypisane liczby są takie same, ale
wtedy zaczyna się od stringów obciętych uprzednio co sprawia
że porównanie potem jest szybsze, można bezkosztowo prawie
offsetem załatwić.

Uogólniając, ma się możliwość histogramowania wszystkiego do czego
można przypisać liczbę bez uprzedniego sortowania.

--
Edek

do góry

On 13.10.2012 14:46, Edek Pienkowski wrote:
> Dnia Sat, 13 Oct 2012 13:52:31 +0200, Michoo napisal:
>
>> Co Ty byś proponował do nauki algorytmów?
>
> Coś co ma "contraints" do spełnienia [1], najlepiej nietrywialne [2]; może
> być wykres Gannta z zadań, ale niektóre uczelnie preferują np. peephole.
Na _początek_? Może wybiję cię ze złudzeń, które też miałem idąc na
studia - na informatykę nie idzie banda geeków i nerdów, którzy
hackowali amigi, atmegi, czy inne zabawki. Większość ludzi swój pierwszy
program napisze na zajęciach. Ich trzeba nauczyć "co to jest algorytm".

> Nie zaczynałbym edukacji od "zobacz, na ile możliwości można zrobić coś
> tak banalnego jak sortowanie, jakie piękne metody".
>
Raczej - coś tak banalnego jak sortowanie można zrobić tak, tak i tak.
Naucz się pokazywać różnice między tymi podejściami zanim przejdziemy dalej.


--
Pozdrawiam
Michoo

do góry

W dniu sobota, 13 października 2012 21:18:12 UTC+2 użytkownik Edek Pienkowski
napisał:
> Dnia Sat, 13 Oct 2012 11:58:34 -0700, kenobi napisal:
>
>
>
> > za jakis czas sobie klepne pewnie to uogolnienie, np dla 32 bit mozna
>
> > pewnie w jednym przebiegu zrobic histogram na gornych bitach wygenerowac
>
> > czesciowo uporzadkowany wynik i w kolejnym posortowac kawalki, albo tez i
>
> > inaczej ladnie dobierajac po efektywnosci - w kazdym razie raczej da sie
>
> > to uogolnic :U
>
>
>
> Dla string�w te� si� da. Taki 8-bajtowy string to 2^64 tak jak int64
>
> to 2^64 jak i float to 2^64. Ymmv, ale widz� morfizm, wystarczy uzupe�ni�
>
> string zerami do najd�u�szego, zera tak rzadko wyst�puj�. Jedynie te
>
> floaty majďż˝ jakieďż˝ NaNy i InfY, ale int siďż˝ nadaje. A jak siďż˝ zmienne
>
> typu String wrzuci w histogram potem, to mo�na histogramowa� po
>
> intach zbudowanych ze znak�w, robi si� to raz, a nie z bajt�w, wystarczy
>
> jak wszystkiemu por�wnywalnemu waln�c raz przypisanie znaku do liczby,
>
> znaki s� znane, wed�ug lexykografii i jeste�my w domu po jednym
>
> przebiegu, chyba �e wszystkie przypisane liczby s� takie same, ale
>
> wtedy zaczyna si� od string�w obci�tych uprzednio co sprawia
>
> �e por�wnanie potem jest szybsze, mo�na bezkosztowo prawie
>
> offsetem za�atwi�.
>
>
>
> Uog�lniaj�c, ma si� mo�liwo�� histogramowania wszystkiego do czego
>
> mo�na przypisa� liczb� bez uprzedniego sortowania.
>
>
nieczytelny tekst da sie przeczytac tylko niektore slowa - tu jest zrodlo tego
pomyslu
przynajmniej ja stad sie o tym dowiedzialem

The quick-sort algorithm requires O(n lg n) operations on average and O(n2)
operations in the worst situation. This
algorithm is very fast. Nevertheless, it needs to be improved! It reminds me of a
quotation from a sci-fi novel by Arkady
and Boris Strugatsky: "We are well aware that this task has no solution... We want to
know how to solve it."
A simple and efficient sorting algorithm exists that, in the worst situation,
requires O(n) operations. No, this is not a joke!
There is such an algorithm. On AMD Athlon 1050, it sorts 10 million numbers in
approximately 0.3 seconds, thousand
times faster than quick sort.
I discovered this algorithm time when I was participated in a computer-science
contest. One of the problems required the
participants to sort seven numbers using no more than three comparison operations.
Seeing this problem as a perfect
opportunity for showing off, I wrote a small program that sorted the numbers without
using any comparison operations.
Unfortunately, my solution was not considered superior. Only after a couple of years
of carefully exploring the existing
sorting algorithms could I evaluate the importance of the result.

kriss kaspersky code optimization effective memory usage

(dalej jest opis ale sprowadza sie to mw do tego co mowie) problemem jest tu ze
dobrze
to dziala jesli wartosci jest duzo a zakres jest waski a niezbyt nadaje sie kiedy
wartosci jest malo, a zakres szeroki ale kiedy wartosci jest duzo i zakres szeroki,
da sie to mz
podzilic pokombinowac i tez ogolnie wykorzystac ten sposob


i tak czesto ja potrzebowalbym sortowac po prostu male inty i wtedy to dziala
blyskawicznie i jest hipergenialna metoda

do góry

On 13.10.2012 14:14, bartekltg wrote:
> W dniu 2012-10-13 11:39, Michoo pisze:
>
>>> Insertionsort jest w oczywisty sposób szybszy w sensie
>>> oczekiwanej liczby porównań (w select wyszukujemy maks
>>> wśród tablic długości n, n-1, n-2...4,3,2, w insert
>>> wkładamy zadany element w tablice długości 1,2..n-1,
>>> a średnio włożymy w połowę długości.
>>
>> Zgadza się.
>>
>>>
>>> Jeśli więc porównanie jest znacznie kosztowniejsze od
>>> przesunięcia, wolimy mieć dwa razy mniej porównań,
>>> nawet kosztem dodatkowych ~n^2 przesunięć.
>>
>> Widziałem nawet takie rozważanie gdzie wyszukiwanie w części
>> posortowanej było robione przeszukiwaniem binarnym, a wstawianie było w
>> czasie stałym - dostajemy złożoność insertion sort n*log(n) ;)
>
> Hehe.
> Złożoność oczywiście pozostaje, ale jakieś tam korzyści
> w działaniu mogą się pojawić.
> Ale mam coś lepszego. Autor pewnej bardzo popularnej książki
> do "c++ i szablonów" buduje wyszukiwanie binarne latając
> po kontenerze ++owaniem iteratora. Komentuje to "++ jest szybkie".
Nie trafiłem - można prosić o tytuł? (Ja za to spotkałem profesora z
ciekawą definicją "native code". ;) )

>>> Żeby nie był to problem czysto akademicki,
>>> niech to będzie 'końcówka qsorta'. Wtedy wywoływany
>>> obszar i tak już najpewniej jest pod ręką.
>>
>> Ale w takiej sytuacji jest heapsort działający zawsze w n*log(n) ;)
>
> Mylisz sytuację.
> Nie chodzi o problem qsorta z niektórymi danymi,
> tylko o to, że gdy, w czasie zrównoważonego działania,
> dochodzimy do rekursywnego wywołania qsorta dla odpowiednio
> małych obszarów, odpala się jakiś mały zwarty n^2.
Z tego co kojarzę standardowym jest użycie heapsorta albo mergesorta
zależnie, czy zależy nam na stabilności. Po co używać coś o złożoności
n^2 skoro ma się rozwiązania n*log(n)?


>>>
>>> Heh, możnaby jakimś studentom zadać;)
>>
>> Wygrzebałem stare sprawozdanie na "algorytmy i struktury danych".
>> Najszybszym algorytmem dla losowych danych był wtedy heapsort napisany w
>> assemblerze (ale miałem na jego optymalizację dobre 3 godziny podczas
>> jazdy pociągiem). Największym zaskoczeniem był Shell:
>> http://grota.be/~michoo/smieci/algo_sort.png
>
> Ładnie.
>
> A co do shella. Już ciąg Pratta miał O(N log^2N)
> To asymptotycznie niedużo więcej niż 'normalne'
> algorytmy. A są lepsze ciągi:
> http://en.wikipedia.org/wiki/Shellsort#Computational
_complexity
>
> Hmm. Piszą, że się nawet w specjalnych zastosowaniach tego używa.
>
> q_med to qsort z medianą z ilu wartości? Wszystkich z przedziału?
z 3 losowych
>
>
> Ale wróćmy do selectsort i insertsort.
>
> Napisałem palce obie wersje(specjalnie dla fira, prawie c):
>
> void insertsort(int * tabl,int first, int last)
> {
> for (int j = first+1;j<=last;j++) //pierwszy nieposortowany
> {
> int i=j;
> int temp = tabl[j];
> while ((i>first) && temp<tabl[i-1])
> {
> tabl[i]=tabl[i-1];
> i--;
> }
> tabl[i]=temp;
> }//for
> }
>
>
>
> void selectsort(int * tabl,int first, int last)
> {
> for (int j=first; j<last; j++)
> {
> int min = j;
> for (int i=j+1;i<=last;i++)
> {
> if (tabl[i]<tabl[min]) min=i;
> }
> int temp = tabl[min];
> tabl[min]=tabl[j];
> tabl[j]=temp;
> }//for
> }
>
>
> I dość brutalną metodę testowania. Długi, losowe identyczne tablice,
> wkładane po kawałkach w obie procedury.
> Robimy ileś powtórzeń dla tablic długości n.
> Za każdym raazem tablica całkowicie losowa.
>
>
> Wyniki.. cóż, mnie zaskoczyły. Sprawdziłem nawet zamieniajac
> w procedurze testowej funkcje miejscami.
A ja jak źle spojrzałem na wykres - insertion u nie też był odrobinę
szybszy.
http://grota.be/~michoo/smieci/sort2.png

>
> Trochę mnie to dziwi. Błędu w implementacji nie widzę.
> czyżby znów cache i liniowy spacer po pamięci?
Średnio wychodzi trochę mniej operacji. Selection ma zawsze 1/2n^2 a
insertion tyle pesymistycznie a średnio połowę. Btw właśnie tak mi
wyszło, że insertion można przedstawić jako "bąbelki od drugiej strony".


Co ciekawe mój selection był minimalnie szybszy od Twojego, mimo dużego
podobieństwa:
void selection(int n,T* data)
{
for(int i=0,p=0;i<n;++i,p=i){
for(int j=i+1;j<n;++j)
if(data[j]<data[p])
p=j;
std::swap(data[i],data[p]);
}
}



--
Pozdrawiam
Michoo

do góry

W dniu sobota, 13 października 2012 22:05:57 UTC+2 użytkownik Michoo napisał:
> Z tego co kojarzę standardowym jest użycie heapsorta albo mergesorta
> zależnie, czy zależy nam na stabilności. Po co używać coś o złożoności
> n^2 skoro ma się rozwiązania n*log(n)?
Algorytmy sortowania o asymptotycznej zlozonosci n^2 moga byc szybsze
od n*log(n) dla malych n, a to z powodu stalego narzutu. Jesli w petelce
trzeba posortowac np. miliard razy po 20 liczb, to warto sprawdzic czy
algorytm kwadratowy nie wypadnie lepiej.
Pozdrawiam

do góry

W dniu sobota, 13 października 2012 19:37:28 UTC+2 użytkownik kenobi napisał:
> oczywiscie i tak jest to slamazarstwo
> najlepsze sortowanie to to co ja nazywam
> metoda chrissa kaserskiego, czyli
> h[ tab[i] ]++;
Przepiekna sztuczka, do dzis pamietam uczucie euforii gdy
sie po raz pierwszy dowiedzialem o tej metodzie :) Zdaje sie ze
ta sztuczka nazywa sie sortowaniem kubelkowym. Niestety ma ona
wade. Gdy ilosc roznych wartosci w tab jest duza to potem na
posortoanie h i tak potrzeba M*log(M) operacji (gdzie M to ilosc
roznych wartosci).

> Podobno kiedys zrobil tak na jakiejs
> olimpiadzie jako nastolatek i komisja
> mu tego nie uznala ;-) zarabista anegdota
> (pisalem o tym z rok czy dwa temu)
Moze w tresci zadania byl jakis kruczek?

> Mozna to uogolnic np w h(tab[i])
> robiac galaz drzewa, albo innymi metodami
> i mysle ze to raczej jest po prostu najszybsze
Jesli jest mala ilosc roznych wartosci (innymi slowy
te same wartosci powtarzaja sie czesto) to z pewnoscia
bedzie najszybsze.

W praktyce pewnie przyda sie jeszcze jakias funkcja hash
czestos[ hash(elementy[i]) % size ]++.

Pozdrawiam

do góry

>
>
> A moim zdaniem o sortowaniu można wspomnieć i tylko tyle. Ja nie
>
> rozumiem, zawsze miałem z tym problem, po co się męczyć poznając
>
> i ćwicząc w każdą stronę wszystkie rodzaje czegoś, jeżeli te
>
> rodzaje nie wnoszą wiele do zrozumienia zasad - wtedy wystarczy
>
> o nich wspomnieć i jak ktoś chce to sobie sprawdzi sam, czy go
>
> fascynują.
>

Programowanie ma wiele odmian i ta jakosmatematyczna niekoniecznie jest najciekawsza,
ale jest to pewien raczej
charakterystyczny kawalek dziedziny
zarazem nieco ciekawy jak i moze i
przymulasty - dla mnie programowanie
to bardziej piksele i asembler ale
posortowac tez mozna (zwl ze to podchodzi
ew pod asembler) (itd) - tak ze szczerze
mowiac zdeczko denerwujesz, polecam
troche spokoju w podejsciu

do góry

W dniu sobota, 13 października 2012 22:53:09 UTC+2 użytkownik M.M. napisał:
> W dniu sobota, 13 października 2012 19:37:28 UTC+2 użytkownik kenobi napisał:
>
> > oczywiscie i tak jest to slamazarstwo
>
> > najlepsze sortowanie to to co ja nazywam
>
> > metoda chrissa kaserskiego, czyli
>
> > h[ tab[i] ]++;
>
> Przepiekna sztuczka, do dzis pamietam uczucie euforii gdy
>
> sie po raz pierwszy dowiedzialem o tej metodzie :) Zdaje sie ze
>
> ta sztuczka nazywa sie sortowaniem kubelkowym. Niestety ma ona
>
> wade. Gdy ilosc roznych wartosci w tab jest duza to potem na
>
> posortoanie h i tak potrzeba M*log(M) operacji (gdzie M to ilosc
>
> roznych wartosci).
>
>

no mnie tez to zdziwilo i tez pamietam moment
jak o tym przeczytalem w tym kawalku
kasperskiego (bardziej utkwilo w pamieci ze
duraki z komisji odrzucily jego rozwiazanie)
ksiage wypozyczylem z mjejskiej biblioteki w bydgoszczy i czytalem to raz pamietam
idac
chyba ze trzy kilometry i czytajac w marszu
po jakichs bydgoskich (niespecjalnie wyjsciowych) peryferiach, (mieszkalem tam
troche wtedy) niezla sprawa

co do tego ze to ma ograniczenia to wydaje mi
sie ze mozna to prawdopodobnie rozwinac/uogolnic a i tak bedzie najlepsze

co do algorytmow to wogole jednak mnie
omijają - w swojej bazie kodu nie mam ani
jednego algorytmu pomijajac rysowanie kolka
bressenhamem (czego nie rozumiem jakies plus szesc minus dwa) ale to bym chyba
zaliczyl
wlasnie do sztuczki optymalizacyjnej -
te bardzo lubie i mam ich sporo


>
> > Podobno kiedys zrobil tak na jakiejs
>
> > olimpiadzie jako nastolatek i komisja
>
> > mu tego nie uznala ;-) zarabista anegdota
>
> > (pisalem o tym z rok czy dwa temu)
>
> Moze w tresci zadania byl jakis kruczek?
>
>
>
> > Mozna to uogolnic np w h(tab[i])
>
> > robiac galaz drzewa, albo innymi metodami
>
> > i mysle ze to raczej jest po prostu najszybsze
>
> Jesli jest mala ilosc roznych wartosci (innymi slowy
>
> te same wartosci powtarzaja sie czesto) to z pewnoscia
>
> bedzie najszybsze.
>
>
>
> W praktyce pewnie przyda sie jeszcze jakias funkcja hash
>
> czestos[ hash(elementy[i]) % size ]++.
>
>
>
> Pozdrawiam

do góry

Dnia Sat, 13 Oct 2012 12:33:40 -0700, kenobi napisal:

> W dniu sobota, 13 października 2012 21:18:12 UTC+2 użytkownik Edek Pienkowski
napisał:
>> Dnia Sat, 13 Oct 2012 11:58:34 -0700, kenobi napisal:
>>
>>
>>
>> > za jakis czas sobie klepne pewnie to uogolnienie, np dla 32 bit mozna
>>
>> > pewnie w jednym przebiegu zrobic histogram na gornych bitach wygenerowac
>>
>> > czesciowo uporzadkowany wynik i w kolejnym posortowac kawalki, albo tez i
>>
>> > inaczej ladnie dobierajac po efektywnosci - w kazdym razie raczej da sie
>>
>> > to uogolnic :U
>>
>>
>>
>> Dla string�w te� si� da. Taki 8-bajtowy string to 2^64 tak jak int64
>>
>> to 2^64 jak i float to 2^64. Ymmv, ale widz� morfizm, wystarczy uzupe�ni�
>>
>> string zerami do najd�u�szego, zera tak rzadko wyst�puj�. Jedynie te
>>
>> floaty majďż˝ jakieďż˝ NaNy i InfY, ale int siďż˝ nadaje. A jak siďż˝ zmienne
>>
>> typu String wrzuci w histogram potem, to mo�na histogramowa� po
>>
>> intach zbudowanych ze znak�w, robi si� to raz, a nie z bajt�w, wystarczy
>>
>> jak wszystkiemu por�wnywalnemu waln�c raz przypisanie znaku do liczby,
>>
>> znaki s� znane, wed�ug lexykografii i jeste�my w domu po jednym
>>
>> przebiegu, chyba �e wszystkie przypisane liczby s� takie same, ale
>>
>> wtedy zaczyna si� od string�w obci�tych uprzednio co sprawia
>>
>> �e por�wnanie potem jest szybsze, mo�na bezkosztowo prawie
>>
>> offsetem za�atwi�.
>>
>>
>>
>> Uog�lniaj�c, ma si� mo�liwo�� histogramowania wszystkiego do czego
>>
>> mo�na przypisa� liczb� bez uprzedniego sortowania.
>>
>>
> nieczytelny tekst da sie przeczytac tylko niektore slowa - tu jest zrodlo tego
pomyslu
> przynajmniej ja stad sie o tym dowiedzialem
>
> The quick-sort algorithm requires O(n lg n) operations on average and O(n2)
operations in the worst situation. This
> algorithm is very fast. Nevertheless, it needs to be improved! It reminds me of a
quotation from a sci-fi novel by Arkady
> and Boris Strugatsky: "We are well aware that this task has no solution... We want
to know how to solve it."
> A simple and efficient sorting algorithm exists that, in the worst situation,
requires O(n) operations. No, this is not a joke!
> There is such an algorithm. On AMD Athlon 1050, it sorts 10 million numbers in
approximately 0.3 seconds, thousand
> times faster than quick sort.
> I discovered this algorithm time when I was participated in a computer-science
contest. One of the problems required the
> participants to sort seven numbers using no more than three comparison operations.
Seeing this problem as a perfect
> opportunity for showing off, I wrote a small program that sorted the numbers
without using any comparison operations.
> Unfortunately, my solution was not considered superior. Only after a couple of
years of carefully exploring the existing
> sorting algorithms could I evaluate the importance of the result.
>
> kriss kaspersky code optimization effective memory usage
>
> (dalej jest opis ale sprowadza sie to mw do tego co mowie) problemem jest tu ze
dobrze
> to dziala jesli wartosci jest duzo a zakres jest waski a niezbyt nadaje sie kiedy
wartosci jest malo, a zakres szeroki ale kiedy wartosci jest duzo i zakres szeroki,
da sie to mz
> podzilic pokombinowac i tez ogolnie wykorzystac ten sposob
>
>
> i tak czesto ja potrzebowalbym sortowac po prostu male inty i wtedy to dziala
blyskawicznie i jest hipergenialna metoda

"Doing the impossible is fun" - Walt Disney.

--
Edek

do góry

On 2012-10-13, Michoo <m...@v...pl> wrote:
> Na _początek_? Może wybiję cię ze złudzeń, które też miałem idąc na
> studia - na informatykę nie idzie banda geeków i nerdów, którzy
> hackowali amigi, atmegi, czy inne zabawki. Większość ludzi swój pierwszy
> program napisze na zajęciach. Ich trzeba nauczyć "co to jest algorytm".

Na szczęście!
:D

Czasem mam wrażenie, że informatyka (ta teoretyczna) stoi w tym kraju
na wysokim poziomie właśnie głównie przez PRL i trudność z dostępem
do różnych Amig i tak dalej. Ale obym nie miał racji, bo to nie
wróżyłoby dobrze na przyszłość :).

pozdrawiam,
PK

do góry