Dlaczego duże zbiory danych muszą być funkcjonalne?

Rozpocząłem ostatnio pracę nad nowym projektem związanym z Big Data na mój staż. Moi menedżerowie zalecili rozpoczęcie nauki programowania funkcjonalnego (gorąco polecili Scalę). Miałem skromne doświadczenie w korzystaniu z F #, ale nie widziałem, jak ważne jest stosowanie tego paradygmatu programowania, ponieważ w niektórych przypadkach jest on drogi.

Dean wygłosił interesującą rozmowę na ten temat i podzielił się przemyśleniami na temat tego, dlaczego „Big Data” tutaj: http://www.youtube.com/watch?v=DFAdLCqDbLQ Ale to nie było zbyt wygodne, ponieważ Big Data nie oznacza tylko Hadoop.

Ponieważ BigData jest bardzo niejasną koncepcją. Zapominam o tym na chwilę. Próbowałem wymyślić jeden prosty przykład, aby porównać różne aspekty, kiedy mamy do czynienia z danymi, aby sprawdzić, czy funkcjonalny sposób jest drogi, czy nie. Jeśli programowanie funkcjonalne jest drogie i zajmuje mało pamięci dla małych danych, dlaczego potrzebujemy go dla Big Data?

Daleki od wymyślnych narzędzi, próbowałem zbudować rozwiązanie dla jednego konkretnego i popularnego problemu, stosując trzy podejścia: imperatywny i funkcjonalny (rekurencja, korzystanie ze zbiorów). Porównałem czas i złożoność, aby porównać trzy podejścia.

Użyłem Scali do napisania tych funkcji, ponieważ jest to najlepsze narzędzie do pisania algorytmu przy użyciu trzech paradygmatów

def main(args: Array[String]) {
    val start = System.currentTimeMillis()
    // Fibonacci_P
    val s = Fibonacci_P(400000000)
    val end = System.currentTimeMillis()
    println("Functional way: \n the Fibonacci sequence whose values do not exceed four million : %d \n Time : %d ".format(s, end - start))
    val start2 = System.currentTimeMillis()

    // Fibonacci_I
    val s2 = Fibonacci_I(40000000 0)
    val end2 = System.currentTimeMillis();
    println("Imperative way: \n the Fibonacci sequence whose values do not exceed four million : %d \n Time : %d ".format(s2, end2 - start2))
}

Funkcjonalny sposób:

def Fibonacci_P(max: BigInt): BigInt = {
    //http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.Stream
    //lazy val Fibonaccis: Stream[Long] = 0 #:: 1 #:: Fibonaccis.zip(Fibonaccis.tail).map { case (a, b) => a + b }
    lazy val fibs: Stream[BigInt] = BigInt(0)#::BigInt(1)#::fibs.zip(fibs.tail).map {
        n = > n._1 + n._2
    }
    // println(fibs.takeWhile(p => p < max).toList)
    fibs.takeWhile(p = > p < max).foldLeft(BigInt(0))(_ + _)
}

Sposób rekurencyjny:

def Fibonacci_R(n: Int): BigInt = n match {
    case 1 | 2 = > 1
    case _ = > Fibonacci_R(n - 1) + Fibonacci_R(n - 2)
}

Tryb rozkazujący:

def Fibonacci_I(max: BigInt): BigInt = {
    var first_element: BigInt = 0
    var second_element: BigInt = 1
    var sum: BigInt = 0

    while (second_element < max) {
        sum += second_element

        second_element = first_element + second_element
        first_element = second_element - first_element
    }

    //Return 
    sum
}

Zauważyłem, że programowanie funkcjonalne jest ciężkie! zajmuje więcej czasu i zajmuje więcej miejsca w pamięci. Jestem zdezorientowany, ilekroć czytam artykuł lub oglądam rozmowę, mówią, że powinniśmy używać programowania funkcjonalnego w informatyce. To prawda, że ​​jest łatwiej i wydajniej, szczególnie w świecie danych. ale zajmuje więcej czasu i więcej pamięci.

Dlaczego więc musimy korzystać z programowania funkcjonalnego w Big Data? Jakie są najlepsze praktyki korzystania z programowania funkcjonalnego (Scala) dla Big Data?

Oto jak to widzę:

• Zignorujmy na chwilę słowa „duże zbiory danych”, ponieważ są one dość mglistym pojęciem

• Wspomniałeś o Hadoop. Hadoop robi 2 rzeczy: pozwala mieć coś w rodzaju „wirtualnego” dysku, który jest dystrybuowany na wielu komputerach, z redundancją, do którego można uzyskać dostęp za pośrednictwem interfejsu API Hadoop, tak jakby był to pojedynczy, jednolity dysk. Nazywa się HDFS jak w Hadoop Distributed File System . Inną rzeczą, jaką robi Hadoop, jest wykonywanie zadań Map-Reduce (jest to framework do Map-Reduce). Jeśli sprawdzimy stronę Wikipedii MapReduce , zobaczymy, że:

MapReduce to model programowania do przetwarzania dużych zbiorów danych z równoległym, rozproszonym algorytmem w klastrze.

...

Program MapReduce składa się z procedury Map (), która wykonuje filtrowanie i sortowanie (np. Sortowanie studentów według imienia do kolejek, jedna kolejka dla każdej nazwy) oraz procedury Reduce (), która wykonuje operację podsumowania (np. Zliczanie liczby uczniów w każdej kolejce, podając częstotliwości nazw)

...

„MapReduce” to platforma do przetwarzania problemów możliwych do zrównoleglenia w ogromnych zestawach danych przy użyciu dużej liczby komputerów

Również na tej stronie Hadoop jest opisany jako

Hadoop, darmowa i otwarta implementacja MapReduce firmy Apache.

Teraz Hadoop jest napisany w Javie, która nie jest językiem funkcjonalnym. Ponadto, jeśli spojrzymy na stronę Hadoop, znajdujemy również przykład, jak utworzyć zadanie MapReduce w Javie i wdrożyć je w klastrze Hadoop .

Oto przykład Java zadania Fibonnaci MapReduce dla Hadoop.

Mam nadzieję, że odpowiem na twoje pytanie, a mianowicie, że BigData, a w szczególności zadanie MapReduce do tworzenia Fibonacciego, nie musi „działać”, tzn. Możesz je zaimplementować w językach OO, jeśli chcesz (na przykład).

Oczywiście nie oznacza to, że BigData „musi” również być OO. Możesz bardzo dobrze użyć funkcjonalnego języka do implementacji zadania podobnego do MapReduce. Możesz na przykład użyć Scali z Hadoop, jeśli chcesz, za pomocą Scalding .

Warto wspomnieć o innych kwestiach.

Podczas wykonywania rekurencji w Scali, jeśli twój kod na to pozwala, Scala przeprowadzi optymalizację wywołania ogona . Ponieważ jednak JVM nie obsługuje (jeszcze) optymalizacji połączeń ogonowych , Scala osiąga to, zastępując w czasie kompilacji wywołania rekurencyjne kodem równoważnym pętlom, jak wyjaśniono tutaj . Zasadniczo oznacza to, że wykonywanie testów porównawczych kodu rekurencyjnego i nierekurencyjnego przy użyciu Scali jest bezcelowe, ponieważ oba kończą w czasie wykonywania to samo.

Tak długo, jak można go uruchomić na jednym komputerze, nie jest to „Big Data”. Twój przykładowy problem jest całkowicie nieodpowiedni, aby coś o tym zademonstrować.

Big Data oznacza, że ​​rozmiary problemów są tak duże, że dystrybucja przetwarzania nie jest optymalizacją, lecz podstawowym wymogiem. A programowanie funkcjonalne znacznie ułatwia pisanie poprawnego i wydajnego kodu rozproszonego ze względu na niezmienne struktury danych i bezpaństwowość.

Nie znam scali i dlatego nie mogę komentować twojego podejścia funkcjonalnego, ale twój kod wygląda jak przesada.

Z drugiej strony twoja funkcja rekurencyjna jest nieefektywna. Ponieważ funkcja wywołuje się dwukrotnie, jest rzędu 2 ^ n, co jest wysoce nieefektywne. Jeśli chcesz porównać trzy podejścia, musisz porównać trzy optymalne implementacje.

Funkcję Fibonacciego można zaimplementować rekurencyjnie, wywołując funkcję tylko raz. Przyjmijmy bardziej ogólną definicję:

F(0) = f0
F(1) = f1
F(n) = F(n-1) + F(n-2)

Standardowy przypadek specjalny to:

f0 = 0
f1 = 1

Ogólna funkcja rekurencyjna to:

function fibonacci($f0, $f1, $n){
    if($n < 0 || !isInt($n)) return false;
    if($n = 0) return $f0;
    if($n = 1) return $f1;
    return fibonacci($f1, $f0 + $f1, $n - 1);
}

Jeśli programowanie funkcjonalne jest drogie i zajmuje mało pamięci dla małych danych, dlaczego potrzebujemy go dla Big Data?

W szczególności widzę już kilka aplikacji, w których jest to niezwykle przydatne. dawny. Statystyka, tj. Obliczanie funkcji Gaussa w locie z różnymi parametrami lub zestawem parametrów do analizy danych. Istnieje również interpolacja do analizy numerycznej itp.

Jakie są najlepsze praktyki korzystania z programowania funkcjonalnego (Scala) dla Big Data?

Aby odpowiedzieć na temat wydajności, istnieją również techniki, które pomagają zwiększyć efektywność w czasie lub przestrzeni, w szczególności rekurencja, rekurencja ogona , styl przekazywania kontynuacji , funkcje wyższego rzędu itp. Niektóre języki mają swoje zalety i wady (na przykład leniwy kontra chętny.) coś prostego, jak sekwencja Fibonnacciego, mógłbym po prostu użyć trybu rozkazującego, ponieważ czasami niektórzy moi współpracownicy są niechętni i mogą nie czuć się tak komfortowo z programowaniem funkcjonalnym, a zatem zajmują więcej czasu na rozwój ... (nadal wolę używam programowania funkcjonalnego, kiedy mogę [aplikacje, którymi się kieruję]), ponieważ uważam, że jest to szybki, czysty i „łatwy do odczytania” (choć uważam ten subiektywny) kod.

Wikipedia opublikowała „szybką” wersję sekwencji fibonnacci. https://en.wikipedia.org/wiki/Functional_programming#Scala

def fibTailRec(n: Int): Int = {
  @tailrec def f(a: Int, b: Int, c: Int): Int = if (a == 0) 0 else if(a < 2) c else f(a-1, c, b + c)
  f(n, 0, 1)
}

Korzystanie ze strumieni / hof

val fibStream:Stream[Int] = 0 #:: 1 #:: (fibStream zip fibStream.tail).map{ t => t._1 + t._2 }