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.

pozdrawiam,
PK

do góry

W dniu sobota, 13 października 2012 23:56:38 UTC+2 użytkownik PK napisał:
> 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.
>
>

a jaki to jest ? ;-)

do góry

W dniu 2012-10-13 22:05, Michoo pisze:
> On 13.10.2012 14:14, bartekltg wrote:

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

Chyba Pasja c++. Próbowałem przekartkować i odszukać
ten kwiatek, ale na szybko nie widzę.


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


Ale standardowym w jakiej sytuacji? Ja mówię o odcięciu
gałęzi rekurencji i walnięciu tam n^2.
_Wydaje_ mi się, że ty mówisz o odpaleniu heapsorta,
gdy qsort dokonuje złych podziałów.
http://www.sgi.com/tech/stl/sort.html //notes[2]
http://en.wikipedia.org/wiki/Introsort

Po co używać n^2 zamiast nlogn?
Bo to n^2 jest szybsze, gdy n jest małe.

I wydajne biblioteczne implementacje robią to tak,
że jak qsort dochodzi do rekurencyjnego wywołania
na tablicy np 20, odpala n^2.


Jak nadal nie wierzysz, zerknij do STLa;)
http://www.sgi.com/tech/stl/download.html
plik stl_algo.h

linijka ~1466, sort.
odpalamy insertionsort (__introsort_loop 1423) z zadanym limitem.
Jest to qsort, z jedną odnoga rekurencji wykonywaną w pętli.
I teraz dwie specjalne zmienne.

Po pierwsze, bada głębokość rekurencji. Jeśli jest większa,
niż zadana, przerzuca na partialsort(first,last,last),
który to jest zaimplementowany kopcem.

Jest to cześć, o której mówisz.

Ale jeśli głębokość nie przekroczy wyznaczonej granicy,
leci qsort. Aż do momentu, gdy
(__last - __first > __stl_threshold)
Wtedy wychodzimy z introsort!
Sprząta, czyli sortuje te odcinku insertionsort
odpalany w sort zaraz po introsort.

To jest usprawnienie, o którym mówiłem.

>> q_med to qsort z medianą z ilu wartości? Wszystkich z przedziału?
> z 3 losowych

Hmm, spory narzut dało:/



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

A dopiero co pisałeś 'nie ma co dyskutować' ;)

Przewaga stała na skali logarytmicznej. Czyli
stale 'a razy szybszy'. Ale znacznie mniejsza przewaga
niż u mnie. Jakbyś gdzieś odkopał kod, chętnie bym zobaczył.


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

Różni się jednym 'szczegółem'. Bąbelek robi mnóstwo swapów,
insertionsort zapisuje sobie 'bąbelka' na boku i robiąc
na niego miejsce operuje tylko na przesuwanych obiektach.

Nie mówiąc już o tym, że naiwnie napisany bąbelek zaczyna
od dołu, zamiast z najbliższego miejsca nieposortowanej
tablicy i leci do samego końca, nawet, gdy nie trzeba już
nic poprawiać.

Ale podobieństwo oczywiście jest

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


Hmm, a jak porównywałeś?
Jeśli niedużo, to obstawiam korzyści z zera:)
Kompilator sobie odwraca i zamiast porownywać
z n porównuje z n?

Podgląd asm tego nie potwierdza. Różnica była
dla małych n<100. Przekazanie trzeciego parametru?

Po przerobieniu tego na wersję z początkiem i końcem
void selection2(int * data,int first,int n)
{
for(int i=first,p=first;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]);
}
}
z dokładnością do szumu jest to samo.


pzdr
bartekltg

do góry

W dniu 2012-10-13 22:53, M.M. pisze:
> 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

Wydaje mi sie, żę fir ma na myśli sortowanieprzez zliczanie
(countingsort), jest szcególnym przypadkiem sortowania
pozycyjnego (radix sort).
Przechodzisz raz tablicę, zliczasz, ile masz jakich wartości
(for... h[ tab[i] ]++; h[n] to ilość elementow w tam o wartości n),
następnie przebiegasz drugi raz i ustawiasz, bo wiesz, którą
wartość gdzie wstawić.

Kubełkowe działa nieco inaczej. Dzielisz zakres danych
na przedziały, każdemu przedziałowi odpowiada kontener.
Przelatujesz tablicę, wrzucasz do odpowiedniego kontenera.
Sortujesz wewnątrz kontenerów i gotowe.

Wszytko to standardowe algorytmy, więc wątpię:


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

Wątpię, by była to prawda.

W szczególności dlatego, że komisja podczas większości
takich konkursów (PA, olimpiada informatyczna, dolnośląskie
zespolowe cośtam cośtam) nie zagląda do kodu. Liczą się wyniki
na danych testowych.

To może i ja rzucę anegdotę. Olimpiada informatyczna (etap okręgowy)
jakieś 10 lat temu. Jedno z zadanek było dość koszmarne.
Coś z grafami, mało istotne.
Nikt go nie zrobił, gdy nam pokazali, jak, to trwało to godzinę,
mimo braku kawałka implementacji;)
Ale jedna osoba dostała ze wstępnych testów parę punktów. Więc
proszą, aby pokazała. Chłopak zaczyna się wykręcać.
-Ale ja tak tylko taką heurystykę zastosowałem, nie warto...
W końcu namówiony przyznał się.
Zwracał logartym (liczby węzłów) + 1;)

Ale punktów za testy, które program przechodził, nikt mu nie odbierał.


pzdr
bartekltg

do góry

W dniu sobota, 13 października 2012 23:56:38 UTC+2 użytkownik PK napisał:
> Jeśli trzeba posortować miliard razy 20 liczb, to lepiej napisać
> optymalny sort dla 20 liczb.
Moim zdaniem cos w okolicach insertion/selection bedzie wlasnie
optymalnym algorytmem.

W programowaniu gier dwuosobowych (szachy,warcaby,go,itd) spotykamy
sie z bardzo podobnym problemem do wielokrotnego sortowania malej
ilosci elementow. Powszechnie stosuje sie ten algorytm z wyborem
maksymalnego elementu.

Pozdrawiam

do góry

W dniu 2012-10-13 20:06, Edek Pienkowski pisze:
> Dnia Sat, 13 Oct 2012 10:50:01 -0700, kenobi napisal:
>
>>>
>>> No to już brzmi fajnie. A co to było to C, która wartość to ma być?
>>>
>>> Poza tym, czy swapów nie miało być jak najmniej?
>>>
>>>
>> C to dowolna wartosc z tablicy najlepiej gdyby to byla taka ktora podzieli
>> tablice na dwa zblizone wielkoscia kawalki, mozna wylosowac dowolna np ze
>> srodka przedzialu, wazne tylko by nie miec wielkiego pecha w wielce
>> dlugiej serii - bo wtedy stos sie wywali - ale taki pech jest malo
>> prawdopodobny
>
> Dowolna, czy się ją jakoś wybiera? Nie można robiąc te swapy na lewo
> i prawo policzyć sobie średniej przy okazji?


Oj, to wyższa filozofia;)

Można wybierać z prawej, z lewej, ze środka,
losowy element, medianę z końców i środka...
Jak ktoś chce, może zawsze brać element 7
(o ile tablica odpowiednio duża).


BTW, algorytm dzielenia proponowany przez fira nie jest najlepszy.
Raczej się robi to w ten sposób, że jedzie od początku w górę
jednym indeksem, aż napotka się element za duży. Potem od końca
w dół drugim indeksem, aż napotka się element za mały
(mniejszy od elementu dzielącego). następnie zamienia się
te elementy i wszytko powtarza, póki się indeksy nie spotkają.

Do testów (i by sprawdzić, ile pamiętam, zajmuję się zupelnie
innymi rzeczami) machnąłęm coś takiego:

void qsort(int * tabl,int first, int last)
{
if (last-first>1)
{
int piv = tabl[first];//element dzielący
int i=first; //elementow first i last+1
int j=last+1; //nigdy nie dotkniemy
do
{
do i++; while ((i<=last)&&(tabl[i]<piv));
do j--; while (tabl[j]>piv); // fajne*)
if (i<j) {std::swap(tabl[i],tabl[j])}
}while (i<j);

tabl[first]=tabl[j];
tabl[j]=piv;

qsort_insert(tabl, first, j-1);
qsort_insert(tabl, j+1, last);
}
}

Dzieki temu odpada jakaś polowa zapisów. W jednym ruchu swapa
_dwa_ elementy lądują po odpowiednich stronach podziału.

*) nie musimy sprawdzać zakresu, bo tab[first] go trzyma.
podobnie, jeśli nasza tablica jest podtablicą taką, że
tab[first-1] jest mniejsze, a tab[last+1] wieksze od kazdego
elementu naszej tablicy, nie musimy tego sprawdzać.
Zerknąłem do stla. Tam z tego korzystają i mają osobne
procedury dla prawego kranca, lewego, i podtablicy wewnetrz.

pzdr
bartekltg

do góry

W dniu niedziela, 14 października 2012 00:04:50 UTC+2 użytkownik bartekltg napisał:
> Wydaje mi sie, żę fir ma na myśli sortowanieprzez zliczanie
> (countingsort), jest szcególnym przypadkiem sortowania
> pozycyjnego (radix sort).
> Przechodzisz raz tablicę, zliczasz, ile masz jakich wartości
> (for... h[ tab[i] ]++; h[n] to ilość elementow w tam o wartości n),
> następnie przebiegasz drugi raz i ustawiasz, bo wiesz, którą
> wartość gdzie wstawić.

Tak, to mialem na mysli, ale cos nazwy mi sie myla :)
Pozdrawiam

do góry

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.

pozdrawiam,
PK

do góry

W dniu 2012-10-13 16:58, Edek Pienkowski pisze:
> Dnia Sat, 13 Oct 2012 16:13:55 +0200, bartekltg napisal:
>
>> W dniu 2012-10-13 16:13, Edek Pienkowski pisze:
>>
>>>
>>> Peephole - o ile wszyscy rozumieją przez to to samo - to zbiór drobynch
>>> optymalizacji kodu przeprowadzanych na niewielkim fragmencie kodu, stąd
>>> przynajmniej jest nazwa. Jest to optymalizacja obecna we wszystkich
>>> optymalizujących kompilatorach, niektóre robią ją kilka razy tak
>>> dla oczyszczenia, bo po to głównie jest.
>>
>> Ok, to wiem, ale... przecież to nie na temat.
>>
>> Pytamy się, co byś polecił na zapoznanie się z algorytmiką,
>> a ty odpowiadasz 'szukanie wąskich gardeł'. To jest bardzo
>> pożyteczne i rozwijające zajęcie, ale algorytmika jest o czym innym.
>
> Shite. To powiedz mi, o czym jest algorytmika.

Zawsze myslalem o tym, jako o nauce projektowania algorytmów.
Ale nie mikroptymalizacji, tylko takim bardziej ogolnym.

Obok jest dyskusja o qsorcie. Na takiej algorytmice student na dzien
dobry ląduje z qsortem. Ma załapać ideę. Robimy podział
porządkujący, i odpalamy rekurencyjnie.
Ma rozumieć, dlaczgo to prowadzi do szybkiego posortowania.

Od tego, czy będzie tam warunek sprawdzający zakres, czy
student sobie poradzi bez niego, ważniejsze będzie
zrozumienie niezmienników.


> Ten sam problem: nie wiem - jak widać - co to jest algorytmika. Przynajmniej
> ta "czysta". Nie potrafię ekstrapolować z sorta, jedynego w takim razie
> przykładu, że to algorytmika.

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


> Widziałem prace z obu tematów w kwestii rozwiązywania problemów NP-hard
> i uważałem to za algorytmikę, ale już teraz nic nie wiem.

Wiesz, ludzie pisząc prace z analizy atakują równie trudne problemy.
Ale jednak analiza na pierwszym roku to całki i różniczki.
I to całki i różniczki, czyli 200-300 letnie podstawy będą
potrzebne inżynierom, nie najnowsze wyniki w sprawie istnienia
rozwiązań równań naviera-stokesa;)

Chociaż masz trochę racji. Mówimy na to popularnie
algforytmika, a takin MIM nazywa to algorytmi
i struktury danych. Algorytmika to osobny przedmiot,
semestr później i tam robi się druga polowę Cormena
(czyli właśnie m.in wspomina o tych zawansowanych
problemach z klasami obliczalnosci).


>>> Powtarzać "dlaczego" akurat te uważam za idealne do nauki znajdziesz w
>>> poprzednim poście, i mam gdzieś, że ktoś uważa Algorytmikę przez duże A za
>>> coś innego, np. obliczenia numeryczne i nic poza tym (spotkałem się też z
>>> takim podejściem).
>>
>>
>> Nikt nie mówi, że to nie jest ważny obszar.
>> Ale nie są to za Chiny ludowe podstawy algorytmiki:)
>
> Link? Chyba że chce się pisać.

Link do tego, że moim skromnym zdaniem, na przedmiocie
o algorytmice na pierwszym/drugim roku uczyć się powinno
raczej jak budowac algorytmy (zaczynając od trywialnych
przykładów, jak sortowanie, algorytm euklidesa, drzewa
czy potęgowanie)?
Jak tylko załoze bloga, na razie będzi tekstem.


>
>> Ok, nieważne
>
> Zazwyczaj nie gadasz bzdur, więc moze czegoś się dowiem.

:)
Ale ostrzegam, ja nie jestem prawdziwym informatykiem.



> Przeczytałem wikipedię polską i angielską - poza tym, że polska mówi o
> etymologii z XIX wieku a angielska o XII w. i nadużyciu słowa w XIX - nic
> się nie dowiedziałem. Znalazłem tylko tą definicję z "... worker/solver
> moving around a problem vector space ...", taką bliską sercu.

Trochę nam chyba ucieka dyskusja. Ustalać definicji algorytmiki
się nie podejmuję. Pozostańmy przy tym, z czym zapoznać studenta
w ramach takiego przedmiotu.

Ja uważam, że powinno się ich nauczyć metod pomocnych
w atakowaniu problemów niesprowadzających się wprost
do 'wpakuj do kontnera i posortuj'.

Powiedzmy, okolice średniej trudności z tego:
http://potyczki.mimuw.edu.pl/user.phtml?op=zadania

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


pzdr
bartekltg

do góry

W dniu 2012-10-14 00:21, M.M. pisze:
> W dniu niedziela, 14 października 2012 00:04:50 UTC+2 użytkownik bartekltg napisał:
>> Wydaje mi sie, żę fir ma na myśli sortowanieprzez zliczanie
>> (countingsort), jest szcególnym przypadkiem sortowania
>> pozycyjnego (radix sort).
>> Przechodzisz raz tablicę, zliczasz, ile masz jakich wartości
>> (for... h[ tab[i] ]++; h[n] to ilość elementow w tam o wartości n),
>> następnie przebiegasz drugi raz i ustawiasz, bo wiesz, którą
>> wartość gdzie wstawić.
>
> Tak, to mialem na mysli, ale cos nazwy mi sie myla :)
> Pozdrawiam
>

Hmm, nadal nie mogę skojarzyć, o kim mówi
fir (dotarło na razie, że jakiś gośc co ksiazkę
napisał:), ale
[Countingsort...] invented by Harold H. Seward in 1954.
i komisja nie znała?

Chyba rzeczywiście, próbował tak posortować double ;)
Albo chociaż dowolną tablicę intów.

pzdr
bartekltg

do góry