czwartek, 7 stycznia 2010

F# - sortowanie przez scalanie

Większość P.T. Czytelników nie jest crazy na punkcie F#, ale ja się nie poddaje :P

W końcu rozwiązanie ostatniego ćwiczenia z http://wojtek-m.blogspot.com/2009/10/f-i-gimnastyka-umysu.html ;)

*3. Sortowanie listy przez scalanie (merge sort). Pamiętaj o złożoności O(nlogn) i stabilności. Pierwszym argumentem sortowania powinna być funkcja porównująca, np. dla int byłaby to funkcja (<).

Dla przypomnienia merge sort wygląda tak:

0. Lista jednoelementowa i lista pusta są posortowane.
1. Podziel listę na 2 części (równe sobie lub jedna o element dłuższa)
2. Posortuj uzyskane 2 listy merge sortem.
3. Scal dwie posortowane listy w jedną.

OK... Jak widać potrzebujemy dwóch funkcji:
split : 'a list -> 'a list * 'a list
merge : 'a list * 'a list -> 'a list

Zacznijmy od split. Funkcja musi zwracać listy z elementami w takim porządku, w jakim je dostała - inaczej ciężko zachować stabilność sortowania. Chodzi o to, że jeżeli lista wejściowa zawiera elementy A oraz B i A znajduje się w niej przed to B, to jeżeli A i B znajdą się w tej samej liście wynikowej, to w niej też A będzie przed B


Pierwszy pomysł, czyli podział listy w jej środku nie jest najlepszy - trzeba policzyć długość listy (n operacji) i potem dojść do jej środka odczepiając elementy do listy lewej (0.5n), a potem odwrócić listę lewą (0.5n).

Drugi pomysł to odczepiamy po dwa elementy od listy wejściowej i doczepiamy do list wynikowych, które potem odwracamy. Stworzenie tych list to 0.5n (odczepiamy po 2 elementy), ich odwrócenie to 2 razy 0.5n.

let split l =
  let rec split l left right =
    match l with
    | [] -> List.rev left, List.rev right
    | [a] -> List.rev (a::left), List.rev right
    | a::b::t -> split t (a::left) (b::right)
  in
    split l [] []


Kolejny pomysł jest zasadniczo podobny do pierwszego, tylko tym razem nie potrzebujemy zliczać długości listy - sama lista posłuży nam za licznik!
Lewą listę inicjujemy listą pustą, prawą - listą wejściową. Zdejmujemy po dwa elementy z listy wejściowej (0.5n), jednocześnie doczepiając głowę listy prawej do listy lewej - dzięki temu potrzebne będzie odwrócenie tylko listy lewej (0.5n).

let split l =
  let rec split l left right =
    match l, right with
    | [], _ -> List.rev left, right
    | [_], _ -> List.rev left, right
    | _::_::t, h::right_t -> split t (h::left) right_t
    | _ -> failwith "Error"
  in
    split l [] l



Ok, to teraz merge.

Najpierw napiszmy prostą pomocniczą funkcję, która szybciej wykonuje operację:
List.append (List.rev a) b - oryginalnie jest to 2n (n na odwrócenie a, n na doczepienie b) - połączyć te operacje można w czasie n:

let rec rev_add a b =
  match a with
    | [] -> b
    | h::t -> rev_add t (h::b)


Idea funkcji merge jest następująca:
1. Lista scalana z listą pustą zwracana jest bez zmian
2. Kiedy scalamy dwie listy (lewą i prawą), to jedna z głów trafi do listy wynikowej:
a) jeżeli prawa głowa jest mniejsza od lewej, to ona trafi na początek wyniku
b) jeżeli lewa głowa jest mniejsza lub równa prawej, to ona trafi na początek wyniku. Ten punkt jest najważniejszy z punktu widzenia stabilności sortowania - jeżeli głowy są równe, to pierwsza do wyniku trafia lewa. Porównań dokonujemy funkcją cmp : 'a 'a -> bool, która działa tak samo jak operator (<).
Listę wynikową oczywiście odwracamy przed zwróceniem.

Przekuwamy to na kod:

let merge cmp left right =
  let rec merge cmp left right acc =
    match left, right with
    | [], l -> rev_add acc l
    | l, [] -> rev_add acc l
    | left_h::left_t, right_h::right_t ->
        if cmp right_h left_h then
          merge cmp left right_t (right_h::acc)
        else
          merge cmp left_t right (left_h::acc)
  in
    merge cmp left right []



Mając split oraz merge merge sort to już niby łatwizna:

let rec merge_sort cmp l =
  match split l with
  | [], h1 -> h1
  | h1, [] -> h1
  | l1, l2 -> merge cmp merge_sort cmp l1 merge_sort cmp l2


Pogrubione linijki powyżej to te, która potrafią sprawić kłopoty. Trzeba pamiętać, że split wywołane dla listy jedno-elementowej przeniesie ten element do prawej lub lewej listy wynikowej - zależy to od wersji funkcji split, którą wybierzemy ;) Jeżeli zapomnimy o jednej z tych linii i użyjemy nieodpowiedniej wersji, to się nam zapętli ;)

Przy okazji pisania tego posta wyszło na jaw, że moja implementacja merge sort w OCamlu była błędna ;) Ciiii :)

Zostało jeszcze pokazanie, że algorytm działa w czasie O(nlogn):
1. Dzielenie listy działa w czasie O(n).
2. Scalanie list działa w czasie O(n) - zależy od długości krótszej z list.
3. Drzewo wywołań scalania ma głębokość log2n - aby dojść do list 1-elementowych (lub pustych) na każdym poziomie musimy wykonać n operacji (bo split ma złożoność O(n), a ilość elementów na każdym poziomie jest stała, są one po prostu w różnych listach)
4. Następnie log2n razy wykonujemy operację scalania listy, na każdym poziomie wykonując również n operacji - scalanie też jest O(n).

Fajniej jest to wytłumaczone tu: http://pl.wikipedia.org/wiki/Sortowanie_przez_scalanie#Z.C5.82o.C5.BCono.C5.9B.C4.87_czasowa

Ok, ja mam na razie dość gimnastyki umysłu, a Wy? :P

Cały kod znajdziecie tutaj: http://pastebin.com/dpqCx1sR.

6 komentarzy:

  1. jeżeli funkcja split musi zwracać listy z elementami w takiej kolejności, w jakiej je dostała to ten drugi pomysł gdzie odczepiamy po dwa elementy od listy wejściowej i doczepiamy do list wynikowych, które potem odwracamy

    let split l =
    let rec split l left right =
    match l with
    | [] -> List.rev left, List.rev right
    | [a] -> List.rev (a::left), List.rev right
    | a::b::t -> split t (a::left) (b::right)
    in
    split l [] []

    nie spełnia tego warunku !

    OdpowiedzUsuń
  2. OK, użyłem złego słowa - w miejscu "kolejność" powinno być "porządek". Chodzi o to, że jeżeli w liście wejściowej L_0 element A znajduje się przed elementem B, to jeżeli elementy A i B znajdują się oba w liście wynikowej L_1, to element A znajduje się w niej przed elementem B. Taki warunek funkcja split spełnia, bo np.

    split [1; 2; 3; 4; 5]

    zwróci

    ([1; 3; 5], [2; 4])

    pozdrawiam!

    PS.
    Zmieniłem już "kolejność" na "porządek".

    OdpowiedzUsuń
  3. OK, a słowa "inaczej ciężko zachować stabilność" co oznaczają według Ciebie ?, bo zachowując ten porządek o którym piszesz i robiąc podział funkcją która robi to w ten trzeci sposób, tzn. : split[1;2;3;4;5] zwraca [1;3;5], [2;4] , to przy założeniu że kolejne kroki algorytmu wykonują podane przez Ciebie funkcje merge i merge_sort, stabilności nie ma. Poza tym wywołanie w funkcji merge_sort: merge cmp (merge_sort cmp l1, merge_sort cmp l2) nie pasuje do funkcji zdefiniowanej w ten sposób: let merge cmp left right. Nie wiem jak w F# ale w Ocamlu to nie przejdzie. Badanie na stabilność zrobiłem więc modyfikując funkcje merge_sort żeby się dała skompilować w OCamlu, tzn wyglada ona tak:

    let rec merge_sort cmp l =
    let (l1,l2) = split l in
    match l1, l2 with
    | [], [] -> []
    | h1, [] -> h1
    | l1, l2 -> merge cmp (merge_sort cmp l1) (merge_sort cmp l2);;

    a test na stabilność tak:

    merge_sort (fun (x,_)(y,_) -> x <= y) [(1,"a");(2,"a");(1,"b");(2,"b");(3,"a");(2,"c");(3,"b")];

    zwraca:
    [(1, "b"); (1, "a"); (2, "b"); (2, "c"); (2, "a"); (3, "b"); (3, "a")]

    OdpowiedzUsuń
  4. 1. "inaczej ciężko zachować stabilność" - mi ciężko było wymyślić taką wersję, która by była stabilna przy innej wersji funkcji split ;) Nie oznacza to, że to jest trudne czy coś :)

    2. Tak, poprawiałem sygnatury funkcji po ich napisaniu (w sumie bez powodu) i faktycznie w ostatecznej wersji funkcji merge_sort jest taki niewielki błąd. Już poprawiony ;) W tej funkcji jednak był jeszcze inny, poważniejszy błąd, który czasami zapętlał program. Już poprawiony, uwaga o tym dopisana do posta ;)

    3. Zakładałem, że cmp to funkcja rodzaju (<) - tzn. dla dwóch takich samych argumentów zwraca false. Jest to w treści "ćwiczenia", ale nie wspominam o tym dalej w poście. Dopisałem to ;)

    Pozdrawiam i powodzenia w walce z OCamlem!

    OdpowiedzUsuń
  5. ad 2. fakt, zapętlał sie dla tego drugiego splita, ale troszkę inaczej go trzeba naprawić żeby dla pierwszego splita też się nie zapętlał :), bo w przypadku pierwszego splita wywołane dla listy jedno-elementowej przeniesie ten element do LEWEJ listy wynikowej, więc trzeba jeszcze dodać linijeczke: | h1, [] -> h1

    ad 3. dla drugiego splita i funkcji (<) takiej jak napisałeś, jest stabilny

    Dzięki za życzenia i wyjaśnienia :)

    Pozdrawiam

    OdpowiedzUsuń
  6. Racja, to dopiszę poprawkę aby działał z obiema wersjami splita :)

    też dzięki za owocne komentarze :) F# może jeszcze się na blgou pojawi, kto wie ;)

    OdpowiedzUsuń