Pytanie składa się z dwóch części. Pierwsza jest koncepcyjna. Następny dotyczy tego samego pytania bardziej konkretnie w Scali.
- Czy używanie tylko niezmiennych struktur danych w języku programowania powoduje, że implementacja niektórych algorytmów / logiki jest z natury bardziej kosztowna obliczeniowo w praktyce? Wynika to z faktu, że niezmienność jest podstawowym założeniem języków czysto funkcjonalnych. Czy są inne czynniki, które mają na to wpływ?
- Weźmy bardziej konkretny przykład. Quicksort jest generalnie nauczany i implementowany przy użyciu operacji mutowalnych na strukturze danych w pamięci. Jak zaimplementować coś takiego w funkcjonalny sposób PURE z porównywalnym narzutem obliczeniowym i pamięci masowej do wersji mutowalnej. Szczególnie w Scali. Poniżej zamieściłem kilka prostych testów porównawczych.
Więcej szczegółów:
Pochodzę z imperatywnego doświadczenia w programowaniu (C ++, Java). Eksplorowałem programowanie funkcjonalne, w szczególności Scala.
Niektóre z podstawowych zasad czystego programowania funkcyjnego:
- Funkcje są obywatelami pierwszej kategorii.
- Funkcje nie mają skutków ubocznych, dlatego obiekty / struktury danych są niezmienne .
Chociaż nowoczesne maszyny JVM są niezwykle wydajne w tworzeniu obiektów, a usuwanie elementów bezużytecznych jest bardzo niedrogie w przypadku obiektów krótkotrwałych, prawdopodobnie nadal lepiej jest zminimalizować tworzenie obiektów, prawda? Przynajmniej w aplikacji jednowątkowej, w której współbieżność i blokowanie nie stanowią problemu. Ponieważ Scala jest paradygmatem hybrydowym, w razie potrzeby można napisać kod imperatywny ze zmiennymi obiektami. Ale jako ktoś, kto spędził wiele lat na próbach ponownego wykorzystania obiektów i zminimalizowania alokacji. Chciałbym dobrze zrozumieć szkołę myślenia, która by na to nawet nie pozwoliła.
W konkretnym przypadku byłem trochę zaskoczony tym fragmentem kodu w tym samouczku 6 . Ma wersję Java Quicksort, po której następuje ładnie wyglądająca implementacja Scala tego samego.
Oto moja próba porównania wdrożeń. Nie wykonałem szczegółowego profilowania. Ale przypuszczam, że wersja Scala jest wolniejsza, ponieważ liczba przydzielonych obiektów jest liniowa (jeden na wywołanie rekurencji). Czy jest jakaś szansa, że w grę wchodzą optymalizacje połączeń końcowych? Jeśli mam rację, Scala obsługuje optymalizację wywołań końcowych dla wywołań samorekurencyjnych. Powinien więc tylko pomagać. Używam Scala 2.8.
Wersja Java
public class QuickSortJ {
public static void sort(int[] xs) {
sort(xs, 0, xs.length -1 );
}
static void sort(int[] xs, int l, int r) {
if (r >= l) return;
int pivot = xs[l];
int a = l; int b = r;
while (a <= b){
while (xs[a] <= pivot) a++;
while (xs[b] > pivot) b--;
if (a < b) swap(xs, a, b);
}
sort(xs, l, b);
sort(xs, a, r);
}
static void swap(int[] arr, int i, int j) {
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}Wersja Scala
object QuickSortS {
def sort(xs: Array[Int]): Array[Int] =
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}Kod Scala do porównywania implementacji
import java.util.Date
import scala.testing.Benchmark
class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark {
val ints = new Array[Int](100000);
override def prefix = name
override def setUp = {
val ran = new java.util.Random(5);
for (i <- 0 to ints.length - 1)
ints(i) = ran.nextInt();
}
override def run = sortfn(ints)
}
val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" )
val benchMut = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java " )
benchImmut.main( Array("5"))
benchMut.main( Array("5"))Wyniki
Czas w milisekundach dla pięciu kolejnych przebiegów
Immutable/Functional/Scala 467 178 184 187 183
Mutable/Imperative/Java 51 14 12 12 12
O(n)list. Jest jednak krótszy niż wersja pseudokodowa;)