Ludzie pragną czasami się rozstawać, żeby móc tęsknić, czekać i cieszyć się z powrotem.
4.
Upraszczanie kodu za pomoc$ technik synchronizowania operacji
123
i posortowanej listy wi(kszej od elementu dziel'cego. Przyk!ad sortowania listy dziesi(ciu
liczb ca!kowitych wed!ug opisanego schematu pokazano na rysunku 4.2. Na listingu 4.12
pokazano sekwencyjn' implementacj( tego algorytmu opracowan' zgodnie z zasadami
programowania funkcyjnego; funkcja sequential_quick_sort() otrzymuje list( i zwraca
jej posortowan' kopi( przez warto$% (zamiast sortowa% list( przekazan' przez referen-
cj(, jak w przypadku funkcji std::sort()).
Rysunek 4.2. Rekurencyjne sortowanie w modelu programowania funkcyjnego
Listing 4.12. Sekwencyjna implementacja algorytmu sortowania szybkiego
template<typename T>
std::list<T> sequential_quick_sort(std::list<T> input)
{
if(input.empty())
{
return input;
}
std::list<T> result;
result.splice(result.begin(),input,input.begin());
T const& pivot=*result.begin();
auto divide_point=std::partition(input.begin(),input.end(),
[&](T const& t){return t<pivot;});
std::list<T> lower_part;
lower_part.splice(lower_part.end(),input,input.begin(),
divide_point);
auto new_lower(
sequential_quick_sort(std::move(lower_part)));
auto new_higher(
sequential_quick_sort(std::move(input)));
result.splice(result.end(),new_higher);
result.splice(result.begin(),new_lower);
return result;
}
Kup ksiąĪkĊ
Poleü ksiąĪkĊ
124
ROZDZIA 4. Synchronizacja wspó bie%nych operacji
Mimo "e zewn(trzny interfejs tej implementacji jest zgodny z regu!ami programowania
funkcyjnego, wewn(trzne mechanizmy zaimplementowano w „tradycyjny” sposób,
poniewa" konsekwentne stosowanie modelu funkcyjnego wymaga!oby wielu dodatko-
wych operacji kopiowania. W roli elementu dziel'cego jest wybierany pierwszy element,
który jest wyodr(bniany z listy za pomoc' funkcji splice() . Chocia" sortowanie na
bazie tak wybranego elementu dziel'cego mo"e nie by% optymalne (liczba operacji
porównania i wymiany mo"e by% wi(ksza, ni" to konieczne), pozosta!e operacje na
strukturze typu std::list b(d' wykonywane szybciej dzi(ki efektywnemu przeszu-
kiwaniu listy. Wiadomo, "e wyodr(bniony element dziel'cy musi si( znaleI% na li$cie
wynikowej, zatem jest od razu umieszczany w odpowiedniej strukturze. Poniewa"
element dziel'cy b(dzie teraz porównywany z pozosta!ymi elementami, przekazujemy
referencj( do tego elementu, aby unikn'% wielokrotnego kopiowania . Mo"emy nast(p-
nie u"y% funkcji std::partition do podzielenia sekwencji na warto$ci mniejsze od elementu dziel'cego i warto$ci nie mniejsze od tego elementu . Najprostszym sposobem okre$lenia kryterium podzia!u jest u"ycie funkcji lambda — aby unikn'% kopio-
wania warto$ci elementu dziel'cego, zastosowano tutaj technik( przechwytywania refe-
rencji (wi(cej informacji na temat funkcji lambda mo"na znaleI% w cz($ci A.5 dodatku A).
Funkcja std::partition() przetwarza przekazan' list( i zwraca iterator wskazuj'cy
pierwszy element, który nie jest mniejszy od warto$ci elementu dziel'cego. Kompletny
typ iteratora mo"e by% do$% d!ugi, zatem w powy"szym kodzie u"yto mechanizmu auto-matycznej identyfikacji typów, aby to kompilator automatycznie okre$li! odpowiedni
typ (patrz cz($% A.7 dodatku A).
Poniewa" analizowana implementacja udost(pnia interfejs zgodny z zasadami pro-
gramowania funkcyjnego, warunkiem rekurencyjnego posortowania obu „po!ówek” listy
jest utworzenie dwóch odr(bnych list. Do tego celu mo"emy ponownie u"y% funkcji
splice(), aby skopiowa% warto$ci z listy wej$ciowej (do elementu divide_point) i umie-
$ci% na nowej li$cie: lower_part . Reszta warto$ci pozostanie na li$cie wej$ciowej.
Obie listy mo"na nast(pnie posortowa% za pomoc' rekurencyjnych wywo!a& funkcji
sequential_quick_sort() . U"ycie funkcji std::move() podczas przekazywania
list na wej$ciu rekurencyjnych wywo!a& pozwala unikn'% kopiowania tych struktur
(wyniki obu wywo!a& s' kopiowane automatycznie). I wreszcie mo"emy ponownie u"y%
funkcji splice() w celu uporz'dkowania list reprezentuj'cych podzbiory elementów
oryginalnej struktury. Warto$ci z listy new_higher trafiaj' na koniec listy wynikowej
(za element dziel'cy), natomiast warto$ci z listy new_lower s' umieszczane na pocz'tku
listy (przed elementem dziel'cym).
SZYBKIE SORTOWANIE RÓWNOLEG E W MODELU PROGRAMOWANIA FUNKCYJNEGO
Poniewa" ju" w poprzednim przyk!adzie zastosowano regu!y programowania funkcyj-
nego, konwersja tego algorytmu na wersj( równoleg!' (korzystaj'c' z obiektów przy-
sz!o$ci) nie jest specjalnie trudna (patrz listing 4.13). Zbiór operacji jest taki sam jak