¿Por qué Big Data necesita ser funcional?

Comencé a trabajar en un nuevo proyecto relacionado recientemente con Big Data para mi pasantía. Mis gerentes recomendaron comenzar a aprender programación funcional (recomendaron Scala). Tuve una experiencia humilde con F #, pero no pude ver la importancia de usar este paradigma de programación, ya que es costoso en algunos casos.

Dean dio una charla interesante sobre este tema y compartió sus pensamientos sobre por qué "Big Data" aquí: http://www.youtube.com/watch?v=DFAdLCqDbLQ Pero no fue muy conveniente ya que Big Data no significa solo Hadoop.

Como BigData es un concepto muy vago. Lo olvido por un tiempo. Traté de encontrar un ejemplo simple para comparar entre los diferentes aspectos cuando tratamos con datos, para ver si la forma funcional es costosa o no. Si la programación funcional es costosa y consume mucha memoria para datos pequeños, ¿por qué la necesitamos para Big Data?

Lejos de las herramientas sofisticadas, traté de construir una solución para un problema específico y popular usando tres enfoques: forma imperativa y forma funcional (recursividad, usando colecciones). Comparé tiempo y complejidad, para comparar entre los tres enfoques.

Usé Scala para escribir estas funciones, ya que es la mejor herramienta para escribir un algoritmo usando tres paradigmas

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))
}

Forma funcional:

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))(_ + _)
}

Manera recursiva:

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

Forma imperativa:

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
}

¡Noté que la programación funcional es pesada! lleva más tiempo y consume más espacio en la memoria. Estoy confundido, cada vez que leo un artículo o veo una charla, dicen que deberíamos usar programación funcional en ciencia de datos. Es cierto que es más fácil y más productivo, especialmente en el mundo de los datos. pero lleva más tiempo y más espacio de memoria.

Entonces, ¿por qué necesitamos usar la programación funcional en Big Data? ¿Cuáles son las mejores prácticas para usar la programación funcional (Scala) para Big Data?

Así es como lo veo:

• Ignoremos las palabras "big data" por un tiempo, ya que son una noción bastante vaga

• Mencionaste a Hadoop. Hadoop hace 2 cosas: le permite tener una especie de unidad "virtual" que se distribuye en varias máquinas, con redundancia, a la que se puede acceder a través de la API de Hadoop como si fuera una única unidad unitaria. Se llama HDFS como en el Sistema de archivos distribuidos de Hadoop . La otra cosa que Hadoop hace es permitirle ejecutar trabajos Map-Reduce (es un marco para Map-Reduce). Si miramos la página de Wikipedia de MapReduce , vemos que:

MapReduce es un modelo de programación para procesar grandes conjuntos de datos con un algoritmo distribuido paralelo en un clúster.

...

Un programa MapReduce se compone de un procedimiento Map () que realiza el filtrado y la clasificación (como ordenar a los estudiantes por nombre en colas, una cola para cada nombre) y un procedimiento Reduce () que realiza una operación de resumen (como contar el número de estudiantes en cada cola, produciendo frecuencias de nombre)

...

'MapReduce' es un marco para procesar problemas paralelizables a través de grandes conjuntos de datos utilizando una gran cantidad de computadoras

También en esta página, Hadoop se describe como

Hadoop, la implementación gratuita y de código abierto de Apache de MapReduce.

Ahora, Hadoop está escrito en Java, que no es un lenguaje funcional. Además, si miramos en la página de Hadoop, también encontramos un ejemplo de cómo crear un trabajo de MapReduce en Java e implementarlo en un clúster de Hadoop .

Aquí hay un ejemplo de Java de un trabajo de Fibonnaci MapReduce para Hadoop.

Espero que esto responda a su pregunta, es decir, que BigData, y en particular un trabajo MapReduce que crea Fibonacci no "necesita" ser funcional, también puede implementarlo en idiomas OO si lo desea (por ejemplo).

Por supuesto, eso tampoco significa que BigData "necesita" ser solo OO. Puede usar un lenguaje funcional para implementar un trabajo similar a MapReduce. Puede, por ejemplo, usar Scala con Hadoop si lo desea, a través de Scalding .

Otros puntos que creo son dignos de mención.

Al hacer recursividad en Scala, si su código lo permite, Scala hará la optimización de la cola de llamadas . Sin embargo, dado que la JVM (todavía) no admite la optimización de llamadas de cola , Scala logra esto reemplazando, en tiempo de compilación, sus llamadas recursivas con código equivalente a bucles, como se explica aquí . Lo que esto básicamente significa es que hacer puntos de referencia de código recursivo vs no recursivo usando Scala no tiene sentido, ya que ambos terminan haciendo lo mismo en tiempo de ejecución.

Siempre que pueda ejecutarlo en una sola máquina, no es "Big Data". Su problema de ejemplo es completamente inapropiado para demostrar algo al respecto.

Big Data significa que los tamaños del problema son tan grandes que distribuir el procesamiento no es una optimización sino un requisito fundamental. Y la programación funcional hace que sea mucho más fácil escribir código distribuido correcto y eficiente debido a las estructuras de datos inmutables y la apatridia.

No conozco scala y, por lo tanto, no puedo comentar sobre su enfoque funcional, pero su código parece excesivo.

Su función recursiva, por otro lado, es ineficiente. Debido a que la función se llama a sí misma dos veces, es del orden 2 ^ n, lo cual es altamente ineficiente. Si desea comparar los tres enfoques, debe comparar tres implementaciones óptimas.

La función de Fibonacci se puede implementar de forma recursiva llamando a la función solo una vez. Tomemos una definición más generalizada:

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

El caso especial estándar es:

f0 = 0
f1 = 1

La función recursiva general es:

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);
}

Si la programación funcional es costosa y consume mucha memoria para datos pequeños, ¿por qué la necesitamos para Big Data?

Específicamente, ya puedo ver algunas aplicaciones donde esto es extremadamente útil. ex. Estadísticas, es decir, calcular una función gaussiana sobre la marcha con diferentes parámetros o un conjunto de parámetros para el análisis de datos. También hay interpolación para análisis numérico, etc.

¿Cuáles son las mejores prácticas para usar la programación funcional (Scala) para Big Data?

Para responder sobre la eficiencia, también hay técnicas para ayudarlo a aumentar su eficiencia en el espacio o el tiempo, específicamente la recursividad, la recursividad de la cola , el estilo de paso de continuación , las funciones de orden superior , etc. Algunos idiomas tienen sus pros y sus contras (por ejemplo, perezoso vs ansioso). algo simple como la secuencia de Fibonnacci, podría usar la forma imperativa, ya que a veces algunos de mis compañeros de trabajo son reacios y pueden no sentirse tan cómodos con la programación funcional y, por lo tanto, requieren más tiempo de desarrollo ... (Todavía prefiero uso la programación funcional cuando puedo [aplicaciones de las que estoy a cargo]) ya que me parece un código rápido, limpio y "fácil de leer" (aunque me parece subjetivo).

Wikipedia tiene una versión "rápida" de la secuencia de fibonnacci publicada. 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)
}

Usando streams / hof

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