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