Dnia Sun, 14 Oct 2012 02:06:31 +0200, Michoo napisal:

> Możemy rozważyć mergesort na 10 procesorach - wykona trochę więcej
> porównań niż Twoje "optimum", ale za to zakończy pracę prawie 2 razy
> szybciej

Możemy też rozważyć użycie GPU. Stawiam, że ograniczeniem
karty będzie wczytywanie i zapisywanie, bo porównać to karta
da radę szybciej mając całe 20 w on-chip i to robiąc jakieś
100 zestawów jednocześnie. Albo inaczej, robiąc blok
porównujący tyle zestawów dowolnym algorytmem, gdzie jeden
wątek liczy jeden zestaw, z narzutem. W on-chip zmieści
się jakieś 400 zestawów 8-bajtowych liczb.

--
Edek

do góry

W dniu 2012-10-14 02:21, Michoo pisze:
> On 13.10.2012 14:27, PK wrote:
>> 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 :).
> Uczyń stabilnym algorytm zaproponowany w punkcie Example
> http://www.sgi.com/tech/stl/next_permutation.html

Z listy robimy listę par, gdzie pierwszym elementem
jest oryginalny element, drugi numer na liście.
Porównaniem będzie porównanie leksykograficzne.
Teraz nie ma elementów równych.

Sortujemy....

dalej sortujemy....

Posortowaną listę par kastrujemy z drugich elementów.


:)

pzdr
bartekltg

do góry

W dniu 2012-10-14 02:18, M.M. pisze:
> W dniu niedziela, 14 października 2012 01:33:48 UTC+2 użytkownik bartekltg napisał:
>> Teoretycznie to ja rysuję drzewo i nie muszę tego
>> implementować;)
>> Sprzętowe sortowanie za pomocą pełnego drzewa decyzyjnego
>> dla 20 liczb? Jaja sobie robisz? ;) Oszczedza się kompa,
>> ale trzeba tone krzemu.
> Jak duze musi byc pelne drzewo decyzyjne? Poczatkowo mamy N! mozliwych
> permutacji. Pierwsza instrukcja IF powoduje ze mam pewnosc co do
> kolejnosci dwoch elementow. Jesli N==20, to po pierwszym IF nie
> wiemy nic o 18tu elementach. Daje to 18! ciagow. Pozostale dwa elementy
> moga byc wplecione w te 18 na 19*19 sposobow. 20! / ( 18! * 19^2 ) = 1.0526.
> Po pierwszym IFie ilosc permutacji spadla o okolo 5%. O ile spadnie z
> kazdym nastepnym ifem?

Każdy if to pojście w prawo lub w lewo w drzewie decyzyjny.
To jest drzewo binarne o 20! liściach. Czyli o wysokości
ceil[log_2 (20!)] = 62 (PK już o tym pisał).
To teraz wszystkie rozmiary w każdym kroku znasz.

Pamiętaj, że w różnych gałęziach 'te same' ify mogą
porównywać zupełnie inne obiekty. Zerknij na potworka
poniżej. A to tylko 3 elementy.

[pseudokod pod podpisem]

Za to ile by się uprościło dopuszczając swapa po
pierwszym porównaniu. Wtedy taki algorym rozgałęzia
się tylko po 'topologicznie różnych' wynikach
(oczywiste jest, że po 2 porównaniach możemy mieć
linię albo V). Nadal ich liczba rośnie jednak wykładniczo.

pzdr
bartekltg


a,b,c

if (a>b)
{
if (b>c)
{
return {a,b,c};
}
else //a,c>b
{
if (a>c)
{
return {a,c,b};
}else
{
return {c,a,b};
}
}
}
else //b>a
{
if (a>c)
{
return {b,a,c};
}
else //b,c>a
{
if (b>c)
{
return {b,c,a};
}else
{
return {c,b,a};
}
}

}

do góry

Dnia Sun, 14 Oct 2012 02:29:16 +0200, bartekltg napisal:

> W dniu 2012-10-14 02:01, Edek Pienkowski pisze:
>
>>> Zawsze myslalem o tym, jako o nauce projektowania algorytmów.
>>> Ale nie mikroptymalizacji, tylko takim bardziej ogolnym.
>>
>> Po pierwsze, kompilatory robią masę "mikrooptymalizacji".
>> Implementuje się je raz.
>
> Ale pisanie kompilatora to zdecydowanie nie jest to, czym
> się student pierwszego roku powinien zajmować:)

Na MIT zajmowali się tym na pierwszym roku. Ale oni to
truskawki cukrem, prawda?

>> No i to są algorytmy, niektóre dość proste, więc to jest
>> wstęp do algorytmiki, jeden z możliwych. Uczy wszystkich
>> podstawowych elementów dorzucając model procesora, którego
>> trzeba użyć. RAMu i cache może nie mieć, ze dwa rejestry
>> i proste fikcyjne ALU, pełny minimalizm.
>
> To tu się po prostu nie zgadzamy. Zwykłym potrzeba
> znaczniej bardziej tego sortowania niż babrania się
> w asm. Zwłaszcza na początku.

Nikt nie mówi o babraniu się w asm, tylko w języku
funkcyjnym z modelem asm, takim że pięciolatek by
zrozumiał. To czego 5-latek by nie zrozumiał to język,
sekwencyjność, przekształcenie nie naruszające kodu
w żadnym z dośc nieograniczonej liczby przypadków,
struktur danych opartych o parę (Scheme...) i parę innych
tego typu rzeczy. Sam fikcyjny asm to akurat pikuś.

> Znam paru dobrych informatyków siedzących 'w przemyśle',
> znam paru, ktorzy poszli w teorię. Na takim przedmiocie
> JAJO, gdzie to właśnie mieli bawic się asm i bebechami
> systemu poradzili sobie. Ale assembler jest im w codziennej
> pracy niepotrzebny. Wiedza wyniesiona z analizy sortowania
> - tak.

Nie wiem jaką wiedzę się z tego wynosi, ale na MIT uważali
bardzo długo, że właściwą na wstęp. Jedyne co bym w tym
zmienił kopiując rozwiązanie to dostosował poziom trudności.

>> A moim zdaniem musi go spróbować zaimplementować sam wcześniej.
>> Albo coś podobnego. Ucz małpę niezmienników ;)
>
> A co to za rożnica? Nie wymyślisz sam większośći algorytmów.
> Często trzeba podsunać pomysł.
>
> BTW, ja też przed studiami 'programowałem'. Bawilem sie pascalem,
> C, C++. 16 bitoiwym assemblerem. Nawet na olimpiade
> informatyczną się w liceum przejechałem.
>
> A na studiach przeszedłem się po sąsiedzku na parę semestrów
> różnych 'metod programowania' czy ASD i zrozumiałem,
> jaką kaszanę odwalałem;)

Ja tak czasami mam do dzisiaj. Przyzwyczaiłem się i niech się
nic nie zmienia w tym względzie, lubię nawyki ;)

>>> Myślę, że tu nie chodzi o sorta, tylko o nauczenie pewnego
>>> zestawu narzędi i sposobu myślenia _przydatnego_ przy
>>> projektowaniu algorytmów.
>>> Podstawy analizy zlozonośći, myślenie o niezmiennikach,
>>> ale też zwracanie uwagi na sytuacje krańcowe
>>> ("Z pętlą jest jak z lotem samolotem. Najtrudniejszy jest
>>> start i lądowanie. Sam lot jest stosunkowo prosty"//Diks;))
>>
>> No, nawet myśle podobnie, ale wciąż nie kumam o co chodzi
>> z tym sortem.
>
> N qsorcie łumaczysz rekurencję. 'dziel i zwyciezaj".
> Na takim insertionsorcie niezmienniki, pętle.
> Porównując oba masz ilustrację złożonośći obliczeniowej.
>
> Są to proste obrazki, przykłady do pojęć.
>
> Można to zastąpić innymi, bardizej wymyslnymi algorytmami,
> ale nijak nie da się tego zastąpić rzeźbieniem w asm
> i peepholami. To po prostu inne zagadnienia.
>
> Jedne cwiczenia na sortowanie można poswiecic.

A co na tych ćwiczeniach? Bo na próbowanie wymyslenia sorta
już jest trochę za późno, a reszta to wałkowanie danej już
wiedzy - nadaje się na utrwalenie, ale dużo więcej z tego
nie wyniknie.

>> Mi nie chodzi o to "czy uczyć całki", ale "jak uczyć całki". To samo
>> w kwestii algorytmów, czy bądźmy szczerzy: programowania.
>
> A ja mam wrażenie, że pod jak uczyć całek mówisz
> 'uczmy się algebry'. Algebry tez się trzeba nauczyć,
> ale na przedmiocie w sali obok. Teraz robimy całki.
> Rozumiesz mnie?

Nie. Ale już o tej porze średnio kojarzę, chyba się
pogubiłem w analogiach.

>>> Powiedzmy, okolice średniej trudności z tego:
>>> http://potyczki.mimuw.edu.pl/user.phtml?op=zadania
>>
>> Przejrzałem trzy. Wieże akurat nie są problemem, bo gram
>> szachy. Ten z odwiedzaniem miast ciekawszy. Ten z drzewem
>> jako "<bardzo ciekawa definicja>" też da się sprowadzić
>> do trywialnego. Wszystkie uczą rozwiązywania problemów,
>
> Już nie pamiętam. Były tam i trudne. Tzn ja nie wymeśliłem
> sprawnego sposobu, a z matmy dośc dobry jestem.

Drzewo:
Znalezienie wszystkiego, co da się zamienić jest nie takie
trudne. Potem mnoży sie ilość możliwych zamian przez siebie,
i tam jest jakieś modulo, może cos w 15 sekund mi się zgubiło
po drodze. Było jednym z ostatnich i wyglądało na zagmatwane.

>> to takie logiczne zagadki, a z narzędzi informatycznych
>> nadają się na "napisz coś co robi co wymyślisz". Niezłe,
>> ale spotkałem lepsze: durny peephole, który wielkim problemem
>> logicznym nie jest. Tak z innego poziomu: peephole uczy
>> programowania na przykładzie przekształcania programu,
>> przy okazji ucząc prostej optymalizacji (znowu: mało
>> kto będzie pisał kompilator, więc jest bardziej
>> abstrakcyjne niż te szachy).
>
> Tak, ale to są inne zagadnienia. Trzeba uczyć i jednych i
> drugich. Nie jednych zamiast drugich.

Sudoku tez rozwija i też je warto podłubać w gazetce,
a nie uczy się na tym programowania. Jedyną różnicą
pomiędzy tym linkiem a sudoku jest to, że sudoku mało kto
stosuje w celach nauczania (póxniej dopiero ktoś wykazał
jakieś właściwości sudoku zawsze prawdziwe, ale tylko
zerknąłem).

>>> No i oczywiście uświadomienie istnienia pewngo pakietu
>>> znanych algorytmów. Takie find-union czy drzewa
>>> przedziałowe przydają się czasem, a w STL ich nie ma.
>>> Pewnie są w boost, ale trzeba wiedzieć, czego szukać.
>>
>> Jak będę ich potrzebował, to będę o tym wiedział. Na dzisiaj
>
> Nie, jeśli nie jesteś świadomy istnienia czegoś, to
> znacznie utrudnia znalezienie tego.
> To pułapka wspolczesnie modnego poglądu na edukację,
> by nie uczyć faktów.

Tak poważnie, wszyscy te kilka modnych poglądów przekręcają
po swojemu. Nikt nie atakuje przekazywania wiedzy, jedynie
część wiedzy trzeba odpuścić, żeby zmieścić umiejętności.
(sorry za drukowane, ale prościej się nie da. W odpowiedzi
na post Michoo masz pełną wersję, w wersji Edziowatej).

--
Edek

do góry

W dniu niedziela, 14 października 2012 03:05:18 UTC+2 użytkownik bartekltg napisał:
> Każdy if to pojście w prawo lub w lewo w drzewie decyzyjny.
> To jest drzewo binarne o 20! liściach. Czyli o wysokości
> ceil[log_2 (20!)] = 62 (PK już o tym pisał).
> To teraz wszystkie rozmiary w każdym kroku znasz.
Kazdy if zwieksza ilosc mozliwych sciezek wykonania
programu dwa razy. Czyli tak jak napisales, okolo log(20!).

Dla tego zrodla:
http://pastebin.com/RGhkx6u6

mam takie wyniki na swoim kompie:

873 859 809 800 667 561 440 421 260 148
selection time 0.420000s
873 859 809 800 667 561 440 421 260 148
insertion time 0.710000s
873 859 809 800 667 561 440 421 260 148
boubles time 1.010000s
873 859 809 800 667 561 440 421 260 148
sort10 time 1.290000s
873 859 809 800 667 561 440 421 260 148
qsort time 1.860000s
148 260 421 440 561 667 800 809 859 873
stl::qsort time 2.140000s

Czyli nawet dla 10 danych nie oplaca sie
rozwinac petli - widac ze algorytm sort10 dziala wolniej
niz selection.

Pozdrawiam

do góry

W dniu niedziela, 14 października 2012 03:39:26 UTC+2 użytkownik M.M. napisał:
> W dniu niedziela, 14 października 2012 03:05:18 UTC+2 użytkownik bartekltg napisał:
> Czyli nawet dla 10 danych nie oplaca sie
> rozwinac petli - widac ze algorytm sort10 dziala wolniej
> niz selection.
Kurde zle zmierzylem czas :)
To sie oplaca!!
A jaki wydajny jest sort z stla...

873 859 809 800 667 561 440 421 260 148
selection time 0.420000s
873 859 809 800 667 561 440 421 260 148
insertion time 0.310000s
873 859 809 800 667 561 440 421 260 148
boubles time 0.300000s
873 859 809 800 667 561 440 421 260 148
sort10 time 0.280000s
873 859 809 800 667 561 440 421 260 148
qsort time 0.560000s
148 260 421 440 561 667 800 809 859 873
stl::qsort time 0.280000s

Pozdrawiam

do góry

W dniu 2012-10-14 03:46, M.M. pisze:
> W dniu niedziela, 14 października 2012 03:39:26 UTC+2 użytkownik M.M. napisał:
>> W dniu niedziela, 14 października 2012 03:05:18 UTC+2 użytkownik bartekltg
napisał:
>> Czyli nawet dla 10 danych nie oplaca sie
>> rozwinac petli - widac ze algorytm sort10 dziala wolniej
>> niz selection.
> Kurde zle zmierzylem czas :)
> To sie oplaca!!
> A jaki wydajny jest sort z stla...
>
> 873 859 809 800 667 561 440 421 260 148
> selection time 0.420000s
> 873 859 809 800 667 561 440 421 260 148
> insertion time 0.310000s
> 873 859 809 800 667 561 440 421 260 148
> boubles time 0.300000s
> 873 859 809 800 667 561 440 421 260 148
> sort10 time 0.280000s
> 873 859 809 800 667 561 440 421 260 148
> qsort time 0.560000s
> 148 260 421 440 561 667 800 809 859 873
> stl::qsort time 0.280000s

>>> http://pastebin.com/RGhkx6u6

Nie bardzo rozumiem. Przecież to tylko
selectionsort w rozpisanej formie.

Co to ma wspolnego z dyskutowanym (blisko)optymalnym
(ze względu na liczbę porównań) algorytmem?

Robisz tam 1+2+..+9 = 45 porównań. A powinieneś maks 22;-)

BTW, stałą 10 wkompilowała się, czy funkcję działają
na zmiennej?


pzdr
bartekltg

do góry

Dnia Sat, 13 Oct 2012 18:46:59 -0700, M.M. napisal:

> W dniu niedziela, 14 października 2012 03:39:26 UTC+2 użytkownik M.M. napisał:
>> W dniu niedziela, 14 października 2012 03:05:18 UTC+2 użytkownik bartekltg
napisał:
>> Czyli nawet dla 10 danych nie oplaca sie
>> rozwinac petli - widac ze algorytm sort10 dziala wolniej
>> niz selection.
> Kurde zle zmierzylem czas :)

A zadbałeś o locality kodu? Co ;) ?
Z benchmarkami tak to już jest, łatwo coś przeoczyć.

> To sie oplaca!!
> A jaki wydajny jest sort z stla...

A przepraszam, jaką masz opinię o twórcach STLa? Albo raczej
implementacji czegoś, co ma taki sam interfejs, jak sami twierdzą?
Przecież za schrzanione kontenery i algorytmy każdy by ich zjadł.

> 873 859 809 800 667 561 440 421 260 148
> selection time 0.420000s
> 873 859 809 800 667 561 440 421 260 148
> insertion time 0.310000s
> 873 859 809 800 667 561 440 421 260 148
> boubles time 0.300000s

Ten wynik mnie trochę dziwi. (bubbles).

> 873 859 809 800 667 561 440 421 260 148
> sort10 time 0.280000s
> 873 859 809 800 667 561 440 421 260 148
> qsort time 0.560000s
> 148 260 421 440 561 667 800 809 859 873
> stl::qsort time 0.280000s

--
Edek

do góry

W dniu niedziela, 14 października 2012 04:00:56 UTC+2 użytkownik bartekltg napisał:
> Nie bardzo rozumiem. Przecież to tylko
> selectionsort w rozpisanej formie.
> Co to ma wspolnego z dyskutowanym (blisko)optymalnym
> (ze względu na liczbę porównań) algorytmem?
> Robisz tam 1+2+..+9 = 45 porównań. A powinieneś maks 22;-)
Takiego wypasionego na kolanie nie dam rady napisac :)

Ale jak sie doda instrukcje return w odpowiednim momencie,
to tylko pesymistycznie jest 45, optymistycznie 10, srednio
nie wiem ile. To tylko eksperyment z implementacja, cos
w rodzaju szeregowej sieci sortujacej.

873 859 809 800 667 561 440 421 260 148
selection time 0.420000s
873 859 809 800 667 561 440 421 260 148
insertion time 0.310000s
873 859 809 800 667 561 440 421 260 148
boubles time 0.290000s
873 859 809 800 667 561 440 421 260 148
sort10 time 0.240000s
873 859 809 800 667 561 440 421 260 148
qsort time 0.560000s
148 260 421 440 561 667 800 809 859 873
stl::qsort time 0.280000s

Tam wersja z return:
http://pastebin.com/Dmq85FP3

> BTW, stałą 10 wkompilowała się, czy funkcję działają
> na zmiennej?
Oj nie wiem, strzelam ze sie nie wkompilowala.

Pozdrawiam

do góry

W dniu niedziela, 14 października 2012 04:02:45 UTC+2 użytkownik Edek Pienkowski
napisał:
> > To sie oplaca!!
> > A jaki wydajny jest sort z stla...
> A przepraszam, jaką masz opinię o twórcach STLa? Albo raczej
> implementacji czegoś, co ma taki sam interfejs, jak sami twierdzą?
> Przecież za schrzanione kontenery i algorytmy każdy by ich zjadł.
Moze zle sie wyrazalem gdy wiele razy narzekalem na stla. Chodzilo mi
zdecydowanie o to, ze inna (a wiec o nieco mniejszej funkcjonalnosci)
implementacja moze dzialac szybciej niz stl. Ze sama w sobie biblioteka
jest zla nigdy nie twierdzilem, bo... nie wiem. Bardzo rzadko uzywam, nie
wiem czy jest dobra, czy zla. Sortowanie najwyrazniej jest bardzo wydajne :)

> > boubles time 0.300000s
> Ten wynik mnie trochę dziwi. (bubbles).
Specjalnie dalem kod, mozna szukac bledow jakby co. :)
Wlasciwie tez mnie dziwi.

Pozdrawiam

do góry