On 2012-10-13, M.M. <m...@g...com> wrote:
> Moim zdaniem cos w okolicach insertion/selection bedzie wlasnie
> optymalnym algorytmem.

Not even close :).

Insertion/selection sort w pesymistycznym wariancie wykonuje N*(N-1)/2
porównań. Czyli w tym wypadku wychodzi 190. Do tego dochodzi konieczność
zapisywania, ewentualnego przesuwania tablic itp itd.

Sortowanie optymalne: max 62 porównania.

pozdrawiam,
PK

do góry

W dniu 2012-10-13 23:56, PK pisze:
> On 2012-10-13, M.M. <m...@g...com> wrote:
>> 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.
>
> Jeśli trzeba posortować miliard razy 20 liczb, to lepiej napisać
> optymalny sort dla 20 liczb.

Na pewno stosuje się (albo teoretykom wydaje się, że
się stosuje, tzw matematyka stosowana) taki spacjalizowany
algorytm dla 5. Dużo ifów:)
Dlaczego dla 5? Bo w mamy algorytm magicznych piątek;)

Dla 20 byłby już zbyt skomplikowany. Za duży.

No, chyba, że miałeś na myśli coś typu insertionsort
skompilowany na stale na 30, czy 5 razy posoruj
piątki i 3 razy 'merge'.

pzdr
bartekltg

do góry

W dniu 2012-10-14 00:35, PK pisze:
> On 2012-10-13, kenobi <p...@g...com> wrote:
>> a jaki to jest ? ;-)
>
> Nie chodziło się na żaden wstęp do programowania ani nie czytało Knutha,
> co?
>
> Optymalny sort dla wektora liczb o znanej długości, to po prostu drzewo
> decyzyjne (binarne) z porównaniami elementów. Jeśli wykonujesz tylko
> konieczne porównania, to takie drzewo wyznacza Ci dolne ograniczenie dla
> pesymistycznych wariantów (czyli ile porównań zawsze wystarcza do
> posortowania n liczb).
>
> Okazuje się, że do posortowania 20 liczb wystarczają 62 porównania.

Co daje 2^62 możliwych wyników - gałęzi algorytmu.

Jeśli zamieniasz elementy miejscami by zmniejszyć tą
ilość, już wykonujesz niepotrzebne operacje.

Dla 20 można taki algorytm napisać, ale jest on chyba
dość teoretycznym tworem.
Dla 4 i 5 to się takie rzeczy pisało, ale dla 20...

pzdr
bartekltg

do góry

On 2012-10-13, bartekltg <b...@g...com> wrote:
> Na pewno stosuje się (albo teoretykom wydaje się, że
> się stosuje, tzw matematyka stosowana) taki spacjalizowany

Stosuje się w praktyce - zapewniam :).

> algorytm dla 5. Dużo ifów:)
> Dlaczego dla 5? Bo w mamy algorytm magicznych piątek;)
>
> Dla 20 byłby już zbyt skomplikowany. Za duży.

Duży to kwestia względna. Napisanie (wygenerowanie) nie kosztuje
zupełnie nic. Pozostaje kwestia rozmiaru programu, ale to nie
zawsze jest problem.

pozdrawiam,
PK

do góry

W dniu 2012-10-14 00:59, PK pisze:
> On 2012-10-13, bartekltg <b...@g...com> wrote:
>> Na pewno stosuje się (albo teoretykom wydaje się, że
>> się stosuje, tzw matematyka stosowana) taki spacjalizowany
>
> Stosuje się w praktyce - zapewniam :).
>
>> algorytm dla 5. Dużo ifów:)
>> Dlaczego dla 5? Bo w mamy algorytm magicznych piątek;)
>>
>> Dla 20 byłby już zbyt skomplikowany. Za duży.
>
> Duży to kwestia względna. Napisanie (wygenerowanie) nie kosztuje
> zupełnie nic. Pozostaje kwestia rozmiaru programu, ale to nie
> zawsze jest problem.

Ale dla 20? Bez sztuczek to nam się nie tylko w cache,
ale i w RAMie nie zmieści.

Możesz powiedzieć coś więcej o tych praktycznych zastosowaniach,
jak wygląda implementacji i do jakich liczb to się stosuje?

pzdr
bartekltg

do góry

W dniu 2012-10-13 20:58, kenobi pisze:

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

Wymyśliłeś sortowanie pozycyjne.

Pamiętaj, że aby zadziałało należy
zadbać, aby nasza podprocedura robiąca
sortowanie przez zliczanie na wybranych bitach
sortowaniem stabilnym. A zaczynać od najmniej
znaczących bitów.

pzdr
bartekltg

do góry

On 2012-10-13, bartekltg <b...@g...com> wrote:
> Co daje 2^62 możliwych wyników - gałęzi algorytmu.

Niestety nie wiem co nazywasz "gałęzią algorytmu".
Drzewo decyzyjne ma unikatowe liście, czyli jest ich 20!.

> Jeśli zamieniasz elementy miejscami by zmniejszyć tą
> ilość, już wykonujesz niepotrzebne operacje.

W drzewku decyzyjnym nie ma niepotrzebnych operacji. Na tym polega
ta idea. Chyba nie łapiesz o czym piszę :).

> Dla 20 można taki algorytm napisać, ale jest on chyba
> dość teoretycznym tworem.
> Dla 4 i 5 to się takie rzeczy pisało, ale dla 20...

Teretycznym nie, bo ktoś to już napisał (istnieją wyniki).
Nie mniej w tym algorytmie nie chodzi o optymalizację, tylko
o wyznaczenie dolnego ograniczenia. Poza tym o tę głównie o tę
ideę są oparte sorty sprzętowe (dla tych, którzy nie chcą tracić
czasu na niepotrzebne operacje komputerów :)).

Zresztą istnieje algorytm (Ford & Johnson Merge-Insertion Sort),
który dla małych n jest bliski optymalnemu (i tym samym jest
zapewne najlepszym algorytmem dla krótkich ciągów). Dla n=20
akurat jest optymalny. Polecam poszukać, bo to naprawdę nieźle
wyrzeźbiona rzecz :).

pozdrawiam,
PK

do góry

Dnia Sat, 13 Oct 2012 21:25:41 +0200, Michoo napisal:

> 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".

Heh, pewnym podejściem selekcji studentów pomimo akceptowania matury
byłyby na wstępie ćwiczenia "napisz peephole, mając struktury danych,
język funkcyjny, który przez ostani tydzień wyłożyliśmy i parę przykładów.
Najlpiej, jakby działał w ogólnym przypadku, ocena 5 tego wymaga". Ale
wtedy skończyłoby się narzekanie na poziom studentów, a na coś trzeba
zwalić. <niepolityczne uwagi over/>

Wbrew pozorom, niektórzy uczyli powyższego jakieś lata temu, z tym
że bandy ludzi, którzy sobie postawili znak przy przejściu dla pieszych
o nazwie "Nerd X-ing". Użyj googla, fajny znak, mieli zacięcie do detali.
Przedmiot był jak najbardziej wstępny i nie wymagał niczego poza "general
aptitude and pre-calculus high school maths" [1]. Jak widać albo rybki
albo akwarium, albo się zakłada częściowe znerdzenie (pol: kujonizm)
albo się nie robi nawet oprogramowania do pralek nie mówiąc o kalkulatorach
(smartfony pominę). <ok, niepolityczne uwagi naprawdę over/>

Inaczej mówiąc, uważam pisanie optymalizacji używając modelu
sekwencyjnego procesora w języku funkcyjnym za coś, co można robić
_przed_ algorytmiką, żeby wszyscy wiedzieli, co to jest procesor i umieli
napisać, zrozumieć i poprawić kilka prostych struktur danych. No i
cudów nie ma, nie wszystkim to się uda - z tym że na części uczelni
na świecie nie ma polityki "mamy straszny poziom i robimi 10
egzaminów poprawkowych", tylko "ok, w miarę ci poszło", bo nikt
cudów nie oczekuje. Ważna jest idea, którą jednak warto załapać,
jeżeli chce się specjalizować w tym akurat kierunku. Przypuszczam,
że rozwija myślenie w innym kierunku niż przysłowiowe całki.

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

No i robi się i tak i tak. Różnica pomiędzy podejściami polega na tym,
że u studentów przede wszystkim należy rozwinąć myślenie. Nie polega to na
wpychaniu wiedzy, bo wiedzę (pamięć faktualną) kążdy ma jaką ma,
pamięta z czym się zetknął (czytając, słuchając robiąc). Pamięć
proceduralną rozwija się inaczej (to ta pamięć odpowiedzialna za między
innymi jazdę na rowerze, z dodatkiem ruchowej - sam wiedza jak się to robi
to za mało), rozwija się ją zderzając z problemami. Trzeba je rozwiązać,
albo polec próbując, bo inaczej nie da się nauczyć "jazdy na rowerze" i
nie da się nauczyć programowania bez rozwalania samemu prostych w sumie
problemów od samego początku.

Biorąc pod uwagę powyższe, implementowanie peephole samemu bez
wystarczających instrukcji danych zanim ktoś zrozumie w ogóle problem
rozwija lepiej niż wykłady,
na których wymienia się sorty i obwieszcza, co to jest złożoność.
Oczywiście, można to samo zrobić z sortem: masz tu tablicę intów (właśnie
ci powiedzieliśmy, co to jest tablica, prawda?) i je posortuj,
czyli ułóż od najmniejszych do największych. I tylko pomagać, jak się ktoś
spyta. Ktoś tak robi? Dawno nie byłem na uczelni.

Potem można wyłoązyć teorię dopiero, bo jak ktoś faktcznie tak jak mówisz
nie wie co to RAM a co to procesor, nie sądzę, żeby w ogóle był w stanie
zrozumieć coś tak prostego jak problemy z sortowaniem. My mamy to już
dawno za sobą, ale ja też kiedyś nie wiedziałem, co to jest program
komputerowy. Z mojego doświadczenia lepiej się przyswaja wiedzę, gdy ma
się za sobą trochę prób, nawet skończonych niepowodzeniem,
bo wtedy się lepiej rozumie temat. Ba, nawet lepiej próbować rzeczy dużo
za trudnych dużo za wcześnie, bo potem wszystko jest prostsze,
fragmenty prawie wpadają w miejsca na brakujące elementy układanki.
Jedynie trzeba zmienić właśnie podejście, zaakceptować niepowodzenia,
przestać udawać że ktoś kto nie wie co to jest program zrozumie
quick-sorta (poza odnotowaniem, że chyba się wie jak to działa)
i ze to jest uczenie algorytmiki.

Z tymi constraints to jest tak, że to tylko pewna struktura poznawcza,
każdy programista ją ma ("jeżeli w kodzie obok a to zawsze b plus
dodatnie x, to y/(a-b) nie będzie dzieleniem przez zero"), ale trzeba ją
wykształcić. Dodatkowo, pomaga pewien wgląd w proces. Dlatego istnieją
takie przedmioty na niektórych uczelniach jak "Jak się uczyć?" czy
bardziej wyspecjalizowane "Street Fighting Maths" (uczy szybkiego
szacowania i paru innych). Ludzie mogą z nich polewać, ale te przedmioty
mają swoje skutki i przyczyny. Tak samo programy uczelni nie powinny uczyć
tylko tego, co się przyda, ale też wykształcić odpowiednio właśnie taką
pamięć w naszych durnych mózgach jak pamięć proceduralna.
Nie mówiąc już o budowaniu abstrakcji, bo ludzki mózg na raz jest w stanie
trzymać w ręku około 5-8 pojęć, choć da się rozwinąć pojemność o kilka
ćwiczeniami na jakiś czas przynajmniej. Ale nie 10 tys. linii kodu na
raz.
Tych właściwości "hardware" nikt nie przeskoczy, trzeba mieć do tego
narzędzia, część narzędzi to nie jest wiedza to umiejętność posługiwania
się niektórymi pojęciami, którą da się nauczyć tylko robiąc - stąd takie
pojęcie, praktykowane, jak "Learning by doing", w dowolnej postaci, może
być lab, mogą być staże.

Powyższe to w zasadzie tło. Ja po prostu nie widzę większego sensu w
zaczynaniu od algorytmów typu sortowanie, jeżeli ktoś praktycznie nie
próbował poradzić sobie ze strukturami danych,
nie rozumie ani reguł ani ograniczeń ani nie posiada odpowiednich
struktur, które mają naturę qualia [3]. To, czy samą algorytmikę zacznie
się od sorta czy od analizy polegającej na wyłożeniu co to jest złożoność
(to drugie przeczy naturalnym własnościom mózgu niestety), najpierw trzeba
mieć inne narzędzia, i w tym procesie nie ma znaczenia, w ramach jakiego
przedmiotu te umiejętności się dostarczy - ok, nie musi to być w
przedmiocie o nazwie algorytmika, ale musi być w wymaganych przed. A
jeżeli sort ma być wykładany jako coś, co ludzie później uzupełnią wiedzą
praktyczną, to sorka,
ale to się nadaje do programowania pralek (dokładnie tak jak w tym
dowcipie o programistkach, zaprogramuj sobie pralkę [2]).

[1] Można znaleźć wszystko używając wyszukiwarki, ze zwróceniem
uwagi na lata wykładanego przedmiotu. Aktualny program jest na Mitx,
zdaje się "wstęp do programowania" lub jakoś podobnie.

[2] Też może być fajne. Gość w ramach demo wyjął kawałek pralki,
dodał trochę prostej elektroniki i to generowało obrazki i dźwięk.
Co kto lubi, ale nie robił tego w ramach profesji. Nerd p..y ;)

[3] Zdaje się są inne dla każdego człowieka, nie da się o nich
tak wprost rozmawiać. Chyba że mi walniesz strumień świadomości
czegoś prostego, jak myślisz o jakimś prostym problemie,
zczynając od "na co po kolei na ekranie nastawiasz gałkę oczną".

PS. Chyba żem się rozpisał...


--
Edek

do góry

W dniu 2012-10-13 21:33, kenobi pisze:

> I discovered this algorithm time when I was participated in

"Rediscovered", jeśli już. Algorytm jest znany od lat 50;)

> a computer-science contest. One of the problems required
> the participants to sort seven numbers using no more than three
> comparison operations.

Czyli M.M. miał rację, kazali użyć porównań.
Mamy obiekty i możemy je porównywać. Nic o zakresie.

BTW, Coś tu jest pomieszane. trzema porównaniami
można posortować 3 liczby.
Może to było tradycyjne 5 liczb w 7 porównań?

> Seeing this problem as a perfect
> opportunity for showing off,

Pokazać algorytm znany kilkadziesiąt lat i udowadniając
niezrozumienie treści zadania. Ot, takich chlopków
roztropków mamy w necie pełno;)

> I wrote a small program that sorted the
> numbers without using any comparison operations.

Za to tablica h miała 2^32 bajtów długości,
bo sortowali longi. Heh, kto się na to łapie.

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

Aż w końcu znalazł ten, skądinąd ważny algorytm, na wikipedii;)

BTW, daj w końcu jego nazwisko w takiej postaci, abym
mógł go wyszukać w goooglach.

pzdr
bartekltg

do góry

On 2012-10-13, bartekltg <b...@g...com> wrote:
> Ale dla 20? Bez sztuczek to nam się nie tylko w cache,
> ale i w RAMie nie zmieści.

Bez sztuczek nie, ale można to podzielić. Nie mniej wtedy oczywiście
są jakieś straty na dodatkowe kombinowanie, więc może się przestać
opłacać.

>
> Możesz powiedzieć coś więcej o tych praktycznych zastosowaniach,
> jak wygląda implementacji i do jakich liczb to się stosuje?

Widziałem zastosowania dla n=8 (zarówno soft- jak i hardware). Akurat
było to zastosowanie w fizyce (tam się trochę spieszą). Nie wiem czy
istnieje jakiekolwiek inne zastosowanie, gdzie ludzie tak walczą
o nanosekundy - może w jakimś GPS czy innych militariach?

pozdrawiam,
PK

do góry