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


>> Jeśli sortowalibyśmy listę, problem w ogóle znika.
> Lista musi być na tyle duża, że nie możemy jej skopiować do struktury o
> dostępie swobodnym, ale jest to naciągane, bo przy złożoności n^2
> prawdopodobnie taniej będzie przenieść listę na pamięć zewnętrzną,
> zwolnić, wczytać do tablicy, posortować jakimś q/heap sortem, zapisać na
> pamięć zewnętrzną, zwolnić, wczytać do listy ;)

Zaalokować pamięć, i to wszytko dla 50 intów:)


>> A czasem o wyborze może zadecydować stabilność sortowania.
>
> Jeżeli dobrze widzę to i insertion i selection może być stabilny.

Insertion jest od razu. Jak prosto poprawić selection, nie wiem.
Już w pierwszym ruchu zamieniami maksymalny element (możemy
go wybrać tak, aby wśród kilku równych był to ten właściwy),
ale element pierwszy ląduje w losowym miejscy, zupełnie
zaburzając porządek względem innych elementów o tej samej wartości.

Ok, wiem jak prosto poprawić... ale to wymaga dodatkowej
tablicy długości n:(

>>
>> Tak więc ja bym nie był tak pewny odpowiedzi:)
>>
>> A poważnie, z tą pamięcią to ciekawy problem.
>> Jeśli już mamy całość w cache (nie rozważamy
>> przecież na serio sortowania dużych tablic)
>> ale jednocześnie porównanie jest tanie (inty).
>
>> Ż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.
Daje to kilka, w optymistycznym przypadku (gdy porównania są
tanie) kilkanaście procent przyspieszenia.


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


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.

W kolejności,
n-dlugość tablicy, liczba powtórzeń, wynik dla insert, wynik dla select
Wyniki w ms. Tabelka na końcu.

Wychodzi, że insert jest jednak szybszy. I jego przewaga rośnie

Wykres czasu pojedynczego powtórzenia (nasz wynik/liczba powtórzeń)
na log log
http://w303.wrzuta.pl/obraz/8asI9fMQioF/loglog_czas

Proporcja czasu selectsorca do insertsorta dla rożnych n.
http://w303.wrzuta.pl/obraz/apPnxl5jsfn/zysk
Proporcja liniiowo, n logarytmicznie.

Tabelka na końcu.

Trochę mnie to dziwi. Błędu w implementacji nie widzę.
czyżby znów cache i liniowy spacer po pamięci?

Korzyść jest większa niż *2 wynikające z samej
ilości porównań. Posortowałem też ciag posortowany
odwrotnie. Insert zwalnia, bo wykorzystuje pesymistyczną
liczbę porównań, select nieco przyszpiesza
(if (tabl[i]<tabl[min]) min=i; się nie wykonuje)
ale nadal insert jest ciut szybsze.


pzdr
bartekltg


Tabelka wyników dla tablicy losowej.
n, liczba powtórzeń, wynik dla insert, wynik dla select

2 24999999 185 289
3 11111110 176 226
4 6249999 157 193
5 3999999 142 181
6 2777777 138 185
7 2040816 130 192
8 1562499 119 198
9 1234567 110 198
10 999999 102 195
11 826446 95 190
12 694444 90 184
13 591715 84 179
14 510204 80 174
15 444444 77 170
16 390624 75 166
17 346020 71 162
18 308641 68 158
19 277008 66 154
20 249999 64 152
22 206611 61 146
24 173611 58 140
26 147928 55 137
28 127550 53 132
30 111111 51 129
32 97656 49 126
34 86505 47 123
36 77160 46 121
38 69252 45 118
40 62499 44 116
43 54083 42 114
46 47258 41 111
49 41649 40 109
52 36982 39 107
55 33057 39 104
58 29726 38 104
61 26874 37 101
65 23668 36 99
69 21003 35 98
73 18765 34 97
77 16866 34 95
81 15241 34 94
86 13520 33 92
91 12075 33 91
96 10850 32 90
101 9802 31 89
107 8734 31 88
113 7831 31 88
119 7061 30 85
125 6399 30 85
132 5739 30 84
139 5175 30 83
146 4691 29 83
154 4216 29 81
162 3810 29 81
171 3419 28 79
180 3086 27 79
190 2770 28 78
200 2499 28 77
211 2246 27 77
222 2029 27 76
234 1826 27 76
246 1652 27 75
259 1490 26 75
272 1351 26 75
286 1222 26 74

do góry

On 2012-10-13, Edek Pienkowski <e...@g...com> wrote:
> Nie wiedzieć czemu w edukacji stosuje się sortowanie do nauczania
> algorytmów. Poza złożonością obliczeniową sortowanie nie nadaje się
> na przykład czegokolwiek.

Pomijając już kwestię tego, że sortowanie oczywiście JEST dobrym
tematem w edukacji (z wielu powodów), to jest także jednym z bardziej
istotnych problemów praktycznych. Zatem nauczyć go i tak trzeba.

pozdrawiam,
PK

do góry

On 2012-10-13, Michoo <m...@v...pl> wrote:
> Jeżeli dobrze widzę to i insertion i selection może być stabilny.

*Każdy* algorytm sortowania można uczynić stabilnym. Rzecz w tym, że
część są stabilna od razu, a w niektórych wymaga to małych nakładów.
I są też takie, z którymi walczyć nie warto :).

pozdrawiam,
PK

do góry

Dnia Sat, 13 Oct 2012 13:52:31 +0200, Michoo napisal:

> On 13.10.2012 11:27, Edek Pienkowski wrote:
>> Dnia Fri, 12 Oct 2012 21:08:36 +0200, Michoo napisal:
>>
>>> Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
>>> poczatku, mimo, że zasada działania jest świetnym przykładem "jak nie
>>> projektować algorytmów". A potem licealiści/studenci na pytanie o
>>> najprostszy algorytm sortowania odpowiadają "bąbelki"...
>>
>> Nie wiedzieć czemu w edukacji stosuje się sortowanie do nauczania
>> algorytmów. Poza złożonością obliczeniową sortowanie nie nadaje się
>> na przykład czegokolwiek.
>>
> Dlaczego? Mamy dane wejściowe, mamy predykat do spełnienia na wyjściu,
> mamy opis operacji, czyli algorytm. Łatwe do zrozumienia, łatwe do
> prezentacji, łatwe do sprawdzenia poprawności.
>
> 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.
Budowanie wykresu Gannta czy raczej samego przypisania może mieć
nietrywialne raguły typu "jeden z programistów, taki Edek [3], rzyga na
widok sortowania, więc niektóre zadania trzeba przypisać innej osobie".
Peephole natomiast uświadomiłoby niektórym "dzieciom Javy po studiach", że
JVM opiera się na modelu (trudne słowo przed nami, ech) procesora i że
tak, Java jest interpretowana.
Dodatkowym wnioskiem z zastosowania "constraints" jest uświadomienie sobie
różnicy pomiędzy "zawsze możliwym", "czasami możliwym"
i "niemożliwym" i odwrotności - spotkałem programistów, którzy tej logiki
w zaawansowanym umysłowo wieku jeszcze nie rozpracowało, przez co nie
rozumie zdania "to niemożliwe", albo "w niektórych przypadkach to nie
zadziała, pomimo tego że w testowanych działa", albo "do tego fragmentu
nie potrzeba unit testów, bo masz dowód" połączone z "nawet jeżeli
napisane testy przejdą, po każdej zmianie trzeba od nowa przeprowadzić
dowód". To ostatnie stosuje się m.in. do algorytmów wielowątkowych, ale
tak naprawdę takie potoczne programistyczne "rozpatrzenie wszystkich
możliwości" jak i na przykład refactoring opierają się na logice
constraints, trzeba umieć je składać, negować itd. .

Nie zaczynałbym edukacji od "zobacz, na ile możliwości można zrobić coś
tak banalnego jak sortowanie, jakie piękne metody".

[1] Gdyby ktoś mi zapodał polskie słowo będę wdzięczny,
ja mam tylko "ograniczenia". Constraints to moje ulubione podejście do
pisania programów w ogólności, _w pewnym sensie_ spełnienie wymagań,
zachowanie integralności sprzętu i inne takie oczywistości jak czas
implementacji można widzieć jako "constraints" - pisanie oprogramowania ma
je wszystkie spełniać i to jest pełna definicja jeżeli mamy dane wszystkie
"constraints".

[2] Stabilność sortowania - trywialne, w sensie mało złożone, pomijam
fakt, że algorytm może zmienić nietrywialnie

[3] Udało mi się do dziś uniknąć znajomości quick-sorta. Jak ktoś
chce z tego faktu wyciągać daleko idące wnioski na temat mojego
zrozumienia algorytmów - proszę bardzo. Po pierwsze, mi się
nie chce, po drugie, ja wciąż potrafię znaleźć szukanie O(n)
mediany znając tylko wybrane właściwości quick-sorta.

--
Edek

do góry

Dnia Sat, 13 Oct 2012 12:16:54 +0000, PK napisal:

> On 2012-10-13, Edek Pienkowski <e...@g...com> wrote:
>> Nie wiedzieć czemu w edukacji stosuje się sortowanie do nauczania
>> algorytmów. Poza złożonością obliczeniową sortowanie nie nadaje się na
>> przykład czegokolwiek.
>
> Pomijając już kwestię tego, że sortowanie oczywiście JEST dobrym tematem w
> edukacji (z wielu powodów), to jest także jednym z bardziej istotnych
> problemów praktycznych. Zatem nauczyć go i tak trzeba.

Jestem chodzącym przykładem, że nie trzeba. Ja wyłącznie używam sorta,
od czasu do czasu potrzebuję innego sorta. Jeżeli gadam z autorem
któregoś z algorytmów sortowania (od zera, nie złożenia), to "szacun".

--
Edek

do góry

W dniu 2012-10-13 14:46, Edek Pienkowski pisze:
> Dnia Sat, 13 Oct 2012 13:52:31 +0200, Michoo napisal:
>
>> On 13.10.2012 11:27, Edek Pienkowski wrote:
>>> Dnia Fri, 12 Oct 2012 21:08:36 +0200, Michoo napisal:
>>>
>>>> Nie wiedzieć czemu w edukacji stosuje się bąble do nauczania na samym
>>>> poczatku, mimo, że zasada działania jest świetnym przykładem "jak nie
>>>> projektować algorytmów". A potem licealiści/studenci na pytanie o
>>>> najprostszy algorytm sortowania odpowiadają "bąbelki"...
>>>
>>> Nie wiedzieć czemu w edukacji stosuje się sortowanie do nauczania
>>> algorytmów. Poza złożonością obliczeniową sortowanie nie nadaje się
>>> na przykład czegokolwiek.
>>>
>> Dlaczego? Mamy dane wejściowe, mamy predykat do spełnienia na wyjściu,
>> mamy opis operacji, czyli algorytm. Łatwe do zrozumienia, łatwe do
>> prezentacji, łatwe do sprawdzenia poprawności.
>>
>> 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.
> Budowanie wykresu Gannta czy raczej samego przypisania może mieć
> nietrywialne raguły typu

Weekend jest i pewnie z t ej okazji nic nie rozumiem:)
Pytanie było, jakie algorytmy dałbyś na początek nauki.

pzdr
bartekltg


> [1] Gdyby ktoś mi zapodał polskie słowo będę wdzięczny,
> ja mam tylko "ograniczenia".

'Ograniczenia' jest ok, poza tym 'więzy', albo zwyczajnie
warunki do spełnienia.

do góry

On 2012-10-13, Edek Pienkowski <e...@g...com> wrote:
> Jestem chodzącym przykładem, że nie trzeba. Ja wyłącznie używam sorta,

Tu chyba nie chodzi o to, kto jest czego przykładem.
Chodzi o statystykę. Sortowanie jest pewnie drugą (po wyszukiwaniu)
najczęściej wykorzystywaną rodziną algorytmów.

> od czasu do czasu potrzebuję innego sorta. Jeżeli gadam z autorem
> któregoś z algorytmów sortowania (od zera, nie złożenia), to "szacun".

Nie wiem co to znaczy "któregoś", bo takich rzeczy jeszcze nie
publikowałem, ale tak: miałem kilka razy w życiu przyjemność (powiedzmy)
wyklepania sortowania od zera. Podobnie jak miałem kilka razy w życiu
jeszcze większą przyjemność (znowu: powiedzmy) pisania własnych RNG,
własnych bardzo złożonych struktur, własnych bibliotek do obliczeń itp
itd. Ale oczywiście nie będę tego używał jako argumentu "za" nauką
sortowania, bo to by było przynajmniej niepoważne :).

Ale studentów nie męczy się agorytmiką po to, żeby pisali własne
sortowania, generatory, drzewa itp. Po prostu trzeba ich nauczyć
poprawnego wykorzystywania gotowych algorytmów, bo błędy na tym
poziomie potrafią uwalić cały projekt (np. publikację naukową -
pełno jest cudownych "odkryć" wynikających z tego, że poważny
naukowiec pisał w C++ i użył rand() niczym 14-latek na sprawdzianie).

pozdrawiam,
PK

do góry

>
> 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
>
> }
>
>
>
>
no moge rzucic okiem, ale pozniej - ostatnio pisalem asembler/kompilator b, i jestem
zdeczko
zmeczony
(pominawszy znowu koszmarne sampoczucioe zdrowotne (w zwiazku z paskudnymi bolami rak
po kleszczu i reszta (tj zatruciem bebechow syfiastymi lekami i zatruciem ukl
oddechowego -
czuje sie troche zbyt beznadziejnie by teraz
rzucic okiem)

do góry

Dnia Sat, 13 Oct 2012 13:13:26 +0000, PK napisal:

> Ale studentów nie męczy się agorytmiką po to, żeby pisali własne
> sortowania, generatory, drzewa itp. Po prostu trzeba ich nauczyć
> poprawnego wykorzystywania gotowych algorytmów, bo błędy na tym poziomie
> potrafią uwalić cały projekt (np. publikację naukową -
> pełno jest cudownych "odkryć" wynikających z tego, że poważny naukowiec
> pisał w C++ i użył rand() niczym 14-latek na sprawdzianie).

Ja od zawsze uważam, że jeżeli studentów można mniej męczyć ucząc nawet
tyle samo, to od tego będą umieli więcej a nie mniej. Nie rozumiem
usprawiedliwiania "męczenia" czymkolwiek. Jak się da studentowi
odpowiednio trudny temat, to sam będzie się musiał namęczyć. Czyli:
"podstępem go!" ;)

Z resztą się zgadzam, ale sortowanie != algorytmika (odwróć nierówność a
będzie jasne). No i taki rand() ma właściwości matematyczne,
z algorytmiką ma to wprost mało wspólnego.

--
Edek

do góry

Dnia Sat, 13 Oct 2012 15:13:24 +0200, bartekltg napisal:

> W dniu 2012-10-13 14:46, Edek Pienkowski pisze:
>> 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.
>> Budowanie wykresu Gannta czy raczej samego przypisania może mieć
>> nietrywialne raguły typu
>
> Weekend jest i pewnie z t ej okazji nic nie rozumiem:)
> Pytanie było, jakie algorytmy dałbyś na początek nauki.

Podkreślić powyżej dwa przykłady ;)?

> > [1] Gdyby ktoś mi zapodał polskie słowo będę wdzięczny,
> > ja mam tylko "ograniczenia".
>
> 'Ograniczenia' jest ok, poza tym 'więzy', albo zwyczajnie
> warunki do spełnienia.

To ostatnie jakoś brzmi, o ile nie mówi się o "constraints",
które mają być naruszone - warunki do niespełnienia?

--
Edek

do góry