¿Por qué Big Data necesita ser funcional?

9

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?

usuario3047512
fuente
55
La programación funcional facilita la paralelización de su código, por lo que incluso si una sola operación puede tardar más tiempo en ejecutarse en un hilo, el rendimiento general puede ser mejor debido al paralelismo.
Giorgio
@Giorgio: Existen diferentes paradigmas como Actor Modeling para obtener el mejor rendimiento al paralelismo. No lo creo?
user3047512
2
Supongo que es simplemente porque el enfoque de mapa / reducción de hadoop es una idea de la programación funcional.
Doc Brown
1
@ user3047512: Por ejemplo, Erlang usa el modelo de actor y en su mayor parte es funcional.
Giorgio
2
La conexión entre la moda "big data" y FP no es tan sencilla. En "Big data", un enfoque llamado reducción de mapas está de moda, que, a su vez, se había inspirado un tanto en el espíritu de programación funcional. Aquí es donde termina la similitud, no puedo ver ninguna conexión adicional entre estos dos mundos.
SK-logic

Respuestas:

13

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.

Shivan Dragon
fuente
2
Usted hace un excelente comentario acerca de que la JVM no admite la optimización de llamadas de cola que socava los puntos de referencia propuestos por el OP. Esta es una respuesta muy informativa, gracias.
maple_shaft
1
Gracias por tu respuesta, sí! tail-call-optimization es una de las características ocultas de scala. stackoverflow.com/questions/1025181/hidden-features-of-scala/… . Uno de los problemas de "Big Data" es que cada compañía está tratando de construir una nueva tecnología de manera diferente. Pero hay principalmente dos: tecnología Hadoop y otros. Como dijiste, es subjetivo y está relacionado con los problemas en sí mismo, también deberíamos elegir el paradigma de programación adecuado en función de nuestra experiencia. Por ejemplo: los modelos predictivos en tiempo real no funcionan muy bien en las plataformas Hadoop.
user3047512
9

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.

Michael Borgwardt
fuente
"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". - No entiendo qué tipo de problema NO PUEDE resolverse en absoluto usando una máquina, y requiere al menos N donde N> 1 ...
Shivan Dragon
66
@ShivanDragon: el tipo de problema que incluye requisitos de rendimiento que son completamente imposibles de satisfacer en un solo sistema. O donde el tamaño de los datos es tan grande que ningún sistema solo puede almacenarlo todo.
Michael Borgwardt
Lo siento, veo tu punto ahora. ¿Es correcto decir que a lo que te refieres es, más específicamente, a MapReduce que vive bajo el paraguas de BigData?
Shivan Dragon
Gracias por su aporte, estoy de acuerdo. Tal vez no pude encontrar un buen ejemplo simple para demostrar mi punto de vista. "Big Data" sigue siendo una forma en que los desarrolladores usan los datos para resolver nuestros problemas diarios teniendo en cuenta la definición de 3V. Olvidaré el 3V por un tiempo y hablaré sobre el aspecto muy simple, tratar con datos. Si vemos que analizar datos de manera funcional es costoso, ¿por qué decimos que "Big Data" debe ser funcional? Este es mi punto.
user3047512
44
@ShivanDragon, por ejemplo, LHC está produciendo varios gigabytes de datos por segundo . No estoy seguro de que una sola máquina pueda manejar tal rendimiento.
SK-logic
4

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);
}
Lorenz Meyer
fuente
¡Gracias! Has planteado un buen punto, pero no hay una forma eficiente de hacerlo de forma iterativa. Este es un problema muy común (conjunto de Fibonacci). y este es el punto de abordar el mismo problema usando tres formas. ¿Puede sugerir una mejor manera de resolver este problema usando cualquier lenguaje de programación, puedo volver a escribir eso usando scala y hacer las mismas pruebas?
user3047512
@ user3047512 Para un lenguaje que admita la recursividad de cola, puede escribirlo con un acumulador. Ejemplos
toasted_flakes del
Scala también apoyan la recursión de cola como característica oculta oldfashionedsoftware.com/2008/09/27/...
user3047512
1
@ user3047512 Debido a que la solución recursiva es una función pura (la salida depende únicamente de los argumentos de la función y nada más ), la memorización es una buena solución. En pocas palabras, cada vez que devolvería un valor, almacenaría los argumentos y daría como resultado un hash de clave / valor, y cada vez que se ejecute la función, mire allí primero. Esta es una de las ventajas de las funciones puras: una llamada futura a esta función encontrará el valor hash preexistente y hará cálculos cero , porque sabemos que el resultado no habrá cambiado.
Izkata
@ user3047512 La versión iterativa también parece una función pura en este caso, pero eso no siempre es cierto: en un lenguaje funcional, creo que el lenguaje lo aplica mejor ...
Izkata
0

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 }
LxsScarredCrest
fuente