🚀 go-pugleaf

Dnia Fri, 11 Jan 2008 14:25:21 +0100, Sebastian Kaliszewski skrobie:
> Sektor van Skijlen wrote:
> >>Uniwersalny stable sort:
> >>template <class iterator>
> >>void my_sort(iterator from, iterator to) {
> >>        typename iterator::difference_type distance = std::distance(from, 
> >>to);
> >>        typename iterator::value_type *refs = new typename 
> >>iterator::value_type[distance];
> >>        std::copy(from, to, refs);
> >>        std::stable_sort(&refs[0], &refs[distance]);
> >>        std::copy(&refs[0], &refs[distance], from);
> >>        delete[] refs;
> >>}
> > 
> > 
> >>Problem - kopiuje wszystko do osobnej tablicy
> > 
> > 
> > To jest akurat żaden problem. Prawdziwy problem jest w pierwszej linijce.
> > std::distance dla zbiorników dwukierunkowych posiada liniowy koszt w długość
> > ciągu.

> No i co z tego? Wołane jest tylko raz.

> N  <  N log2 N

To może i prawda, ale jeśli dokładamy do tego distance jeszcze kopiowanie
elementów, to zaczyna się nam owszem czas liniowy, ale trochę za bardzo.

Złożoność obliczeniowa w notacji O(n) określa nam jedynie proporcje
zmieniającego się czasu wykonania wraz ze wzrostem ilości danych. Nie ma tam
żadnej informacji o jednostkowym czasie wykonania w stosunku do tego, ile z
teo czasu wykonania idzie "na rozkurz". A w tym akurat rozwiązaniu na rozkurz
idzie całkiem sporo i fakt, że złożoność wciąż pozostaje N*log2(N) nic nie
znaczy.

Poza tym po drobnych przemyśleniach doszedłem do kilku innych ciekawych
wniosków na temat sortowania w STL.

W ogólności w algorytmach sortowania możemy wyróżnić jeszcze grupy skupiające
algorytmy o określonych wymaganiach co do źródłowego zbiornika, w którym są te
dane trzymane. Otóż tak się akurat składa, że większość "sensownych" (mówię,
żeby pominąć bąbelkowe i insertion sort) algorytmów sortowania wymaga pracy na
zbiorniku swobodnego dostępu, gdyż wymagają możliwości wycinania fragmentów
zbiornika, zamieniania elementów, przeskakiwania o kilka elementów, wszystko w
stałym czasie, bo w przeciwnym razie nasza piękna złożoność N*log(N) weźmie w
łeb.

No i poza tym znam jeszcze merge sort, który nie wymaga zbiornika swobodnego
dostępu, ale wymaga zbiornika o elementach łańcuchowo wiązanych.

Być może istnieją też jakieś algorytmy sortowania (w ogólności już mówię
teraz), które mogą pracować na strumieniu danych, ale one zwykle potrzebują
jeszcze dodatkowego zbiornika, żeby wstawić posortowane dane. Być może można
by kombinować na tej zasadzie z algorytmem sort_copy() (dokładnie to
partial_sort_copy(), bo sort_copy nie ma). Tam akurat dane czytane są z
InputIterator, a zapisywane do RandomAccessIterator.

Ale wracając na ziemię, mamy tylko dwie grupy sensownych algorytmów
sortowania, które mogą pracować na zbiorniku "w miejscu": albo zbiornik
swobodnego dostępu, albo zbiornik z elementami wiązanymi łańcuchowo.

Zbiorniki swobodnego dostępu mamy załatwione.

Co ewentualnie możemy jeszcze zrobić dla ułatwienia życia użytkownikowi, to
dostarczyć sortowanie dla listy, bo jest to jedyny zbiornik o BUDOWIE
pozwalającej na użycie merge sort.

I teraz: w jakiej formie? Możemy teoretycznie zrobić to nawet na upartego jako
funkcję zewnętrzną o identycznym interfejsie, jak std::sort. Ale to ma
następujące konsekwencje:

 - ponieważ chcemy implementację oprzeć o szczególność budowy tego zbiornika,
   musimy określić to jako koncepcję

Czyli musimy zrobić coś w stylu koncepcji LinkedListContainer. Może ona być
pochodną BidirectionalContainer, choć tutaj nie stawiałbym tego za pewnik
(pamiętaj, że do oryginalnej STL należy jeszcze slist, która jest jedynie
ForwardCointainer, a też jest listą wiązaną).

 - dla tej jednej koncepcji tworzymy wymaganie posiadania metody iteratora
   tego zbiornika, która pozwala na "wypięcie" go z listy bez utraty
   informacji o pozycji

I dobrze, niech tak nawet będzie. Jakie są jednak tego konsekwencje:

1. Dostajemy dodatkową koncepcję, która posiada jedną, no dobrze na upartego
dwie metody realizacji, która zostaje i tak już dostarczona do biblioteki w
postaci zbiornika std::list

2. Komplikujemy interfejs LinkedListIterator

Efektywnie: dostarczamy użytkownikowi generyzm w postaci: ok, masz tutaj
koncepcję LinkedListContainer, możesz sobie zrobić wedle niej zbiornik, masz
dostarczony algorytm sortowania, który będzie pracował również na tego typu
zbiornikach.

Biorąc pod uwagę, że std::list i tak ma już wystarczająco wąskie zastosowanie,
nie uważasz, że robienie z tego jeszcze dodatkowej koncepcji po to tylko, żeby
sort() miał wspólny interfejs z ogólnym sortem (zastosowanie tego tricku jest
również wątpliwe), to zlekka przerost formy nad treścią?

Ja wiem, że istnieją koncepcje trzymania się zasad raz na zawsze i do końca,
ale wybacz, nie mają one wiele wspólnego z praktyką. I C++ nie jest żadnym
wyjątkiem pod tym względem. Te, w których stawiano na dotrzymanie zasad, a nie
na maksymalną użyteczność dla użytkownika, przepadły.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"Java is answer for a question that has never been stated"