Zupełnie innym podejściem jest programowanie deklaratywne. W tym przypadku nie pisze się, co po kolei program ma robić, tylko jaką wartość chce się uzyskać. Czyli program deklaratywny nie jest zbiorem instrukcji, tylko zbiorem deklaracji właściwości obiektu, który chcemy uzyskać na wyjściu.
Wśród powszechnie używanych języków generalnego zastosowania jest niewiele języków czysto deklaratywnych (czyli takich, w których nie ma instrukcji ani skutków ubocznych). Jedynym, jaki ja znam jest Haskell. Niemniej jednak jest cała masa języków prawie :-) deklaratywnych, które preferują deklaracje wartości nad instrukcjami, ale pozostawiają w swojej składni instrukcje np. żeby uprościć operacje I/O. Do takich języków należy cała "rodzina" ML (czyli m.in. OCaml i F#) a także kompilowana do JVM Scala.
Język C# był na początku czysto imperatywny. Na szczęście, w każdej kolejnej wersji nabierał coraz więcej możliwości programowania funkcjonalnego (czyli deklaratywnego). Programując w najnowszej wersji (C# 4.0) często stoimy przed wyborem, czy zaimplementować coś imperatywnie, czy deklaratywnie.
Jakiś czas temu zastanawiałem się, jak te dwa style przekładają się na wydajność programu i postanowiłem trochę poeksperymentować...
Postanowiłem zaimplementować w miarę prosty algorytm na dwa sposoby, a następnie porównać czasy wykonania. Do implementacji wybrałem funkcję, która bierze na wejściu dwie listy i zwraca informację, czy druga lista jest podzbiorem pierwszej.
Najprostsza implementacja imperatywna byłaby następująca:
public bool IsSubset<T>(List<T> first, List<T> second) { foreach(T elem in second) { if(!first.Contains(elem)) return false; } return true; }
Powyższe rozwiązanie ma złożoność kwadratową (a w zasadzie: prostokątną :-) ). Jeśli pierwsza lista będzie miała 100 000 elementów, a druga będzie jej 10 000-elementowym podzbiorem, to na moim komputerze taka metoda wykona się w czasie ok. 39 sekund. Typowy, średnio lubiący swoją pracę programista nawet nie będzie się zastanawiał, czy można to napisać lepiej, bo:
- "terminy gonią",
- "nie chce mi się",
- "czas procesora jest tańszy niż czas programisty",
- ...
Trochę lepszy programista pomyśli, że da się napisać implementację działającą w czasie n * log n:
public bool IsSubsetBinarySearch<T>(List<T> first, List<T> second) where T: IComparable<T> { var array = new T[first.Count]; first.CopyTo(array); Array.Sort(array); foreach (var elem in second) { if(Array.BinarySearch(array, elem) < 0) return false; } return true; }
Powyższe rozwiązanie dla tych samych danych "wypluje" wynik po czasie ok. 3,14 sekund. Mało kto szukałby w takiej sytuacji lepszego algorytmu, bo:
a. "terminy gonią",
b. ...
z. "klientowi nic się nie stanie, jak poczeka kilka sekund"
Nie jest to jednak rozwiązanie optymalne, bo istnieje lepsza, liniowa implementacja:
public bool IsSubsetHashSet<T>(List<T> first, List<T> second) { var hs = new HashSet<T>(first); foreach (var elem in second) { if(!hs.Contains(elem)) return false; } return true; }
Kod, który znajduje się powyżej to są już granice moich imperatywnych zdolności :-) Zaimplementowana w taki sposób metoda zakończyła działanie po 0,047 sekundy.
Teraz przejdźmy do wersji deklaratywnej (używającej Linq to Objects):
public bool IsSubsetLinq<T>(List<T> first, List<T> second) { return second .Except(first) .Count() == 0; }
Powyższa metoda jest wręcz matematyczną definicją problemu, jaki sobie postawiłem. Jest krótsza, prostsza i czytelniejsza nawet od najbardziej naiwnej wersji imperatywnej. A działa zaskakująco dobrze: kończy działanie po 0,063 sekundy! Co prawda, jest to troszkę więcej niż w przypadku optymalnej implementacji imperatywnej, ale:
- wygląda na to, że asymptotyczny czas działania jest taki sam (nieznaczna różnica),
- czas poświęcony na napisanie kodu był bardzo krótki,
- taki kod jest na tyle prosty, że może go napisać nawet słaby programista.
Ten ostatni argument jest według mnie, szczególnie istotny. Programowanie funkcyjne jest, po przełamaniu początkowych trudności, po prostu łatwiejsze. Jeśli z niego zrezygnujemy na rzecz wyżyłowanych imperatywnych implementacji, to się chyba przejedziemy... Praktyka pokazuje (takie mam wrażenie), że łatwiej jest znaleźć dziewicę w akademiku niż optymalną implementację w dużym, imperatywnie napisanym systemie informatycznym :-)
