9

I started working on a new project lately related to Big Data for my internship. My managers recommended to start learning functional programming (They highly recommended Scala). I had a humbled experience using F#, but I couldn't see the the important of using this paradigm of programming as it's expensive in some cases.

Dean gave an interesting talk about this topic, and shared his thoughts on why "Big Data" here : http://www.youtube.com/watch?v=DFAdLCqDbLQ But it wasn't very convenient as Big Data doesn't mean only Hadoop.

As BigData is very vague concept. I forget it for a while. I tried to come-up with one simple example to compare between the different aspects when we deal with data, to see if functional way is expensive or no. If functional programming is expensive and memory-consuming for small data, why do we need it for Big Data ?

Far from fancy tools, I tried to build a solution for one specific and popular problem using three approaches: Imperative way and functional way (recursion, using collections). I compared time and complexity,to compare between the three approaches.

I used Scala to write these functions as it's the best tool to write an algorithm using three paradigms

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

Functional way :

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

Recursive way:

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

Imperative way:

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
}

I noticed that Functional programming is heavy! it takes longer time and consume more space in memory. I am confused, whenever I read an article or watch a talk, they say that we should use functional programming in data science. True, it 's easier and more productive, specially in data world. but it takes more time and more memory space .

So, why do we need to use Functional programming in Big Data ? What are the best practices to use functional programming (Scala) for Big Data ?

  • 5
    Functional programming makes it easier to parallelize your code, so even if a single operation may take more time to run in one thread, the overall performance can be better due to parallelism. – Giorgio Dec 7 '13 at 12:05
  • @Giorgio : There are different paradigms as Actor Modeling to get the best performance to parallelism. Don't think so ? – user3047512 Dec 7 '13 at 12:13
  • 2
    I guess its simply because the map/reduce approach from hadoop is an idea from functional programming. – Doc Brown Dec 7 '13 at 12:28
  • 1
    @user3047512: For example, Erlang uses the actor model and is for the most part functional. – Giorgio Dec 7 '13 at 12:38
  • 2
    The connection between "big data" fad and FP is not that straightforward. In "Big data", a so called map-reduce approach is fashionable, which, in turn, had been somewhat inspired by the functional programming ethos. This is where similarity ends, I cannot see any further connection between these two worlds. – SK-logic Dec 7 '13 at 16:18
13

Here's how I see it:

  • Let's ignore the words "big data" for a while, as they are a pretty vague notion

  • You mentioned Hadoop. Hadoop does 2 things: allows you to have a sort of "virtual" drive which is distributed on multiple machines, with redundancy, that can be accessed via Hadoop's API as if it were a single, unitary, drive. It's called HDFS as in Hadoop Distributed File System. The other thing Hadoop does is allow you to execute Map-Reduce jobs (it's a framework for Map-Reduce). If we check out MapReduce's Wikipedia page, we see that:

MapReduce is a programming model for processing large data sets with a parallel, distributed algorithm on a cluster.

...

A MapReduce program is composed of a Map() procedure that performs filtering and sorting (such as sorting students by first name into queues, one queue for each name) and a Reduce() procedure that performs a summary operation (such as counting the number of students in each queue, yielding name frequencies)

...

'MapReduce' is a framework for processing parallelizable problems across huge datasets using a large number of computers

Also on this page, Hadoop is described as

Hadoop, Apache's free and open source implementation of MapReduce.

Now, Hadoop is written in Java, which is not a functional language. Also, if we look on Hadoop's page, we also find an example of how to create a MapReduce job in Java and deploy it in a Hadoop cluster.

Here's a Java example of a Fibonnaci MapReduce job for Hadoop.

I hope this answer your question, namely that BigData, and in particular a Fibonacci-creating MapReduce job doesn't "need" to be functional, aka you can implement it in OO languages if you want to (for example).

Of course that doesn't mean BigData "needs" to be OO-only either. You can very well use a functional language to implement a MapReduce like job. You can, for example, use Scala with Hadoop if you want to, via Scalding.

Other points I think are worth mentioning.

When doing recursion in Scala, if your code allows for it, Scala will do tail-call-optimization. However, since the JVM doesn't (yet) support tail-call-optimization, Scala achieves this by replacing, at compile time, your recursive calls with code equivalent to loops, as explained here. What this basically means is that doing recursive vs non-recursive code benchmarks using Scala is pointless, as they both end up doing the same thing at run time.

  • 2
    You make an excellent point about the JVM not supporting tail call optimization which undermines the benchmarks proposed by the OP. This is a very informative answer, thank you. – maple_shaft Dec 7 '13 at 15:37
  • 1
    Thank you for your answer, Yes ! tail-call-optimization is one of the hidden scala features. stackoverflow.com/questions/1025181/hidden-features-of-scala/… . One of the problems of "Big Data" is that every company is trying to build a new technology in different way. But there are mainly two: Hadoop tech and others. As you said, it's subjective and related to the problems it self, we should pick the right programming paradigm based on our expertise as well. For example: Real-time Predictive models doesn't work very well on Hadoop Platforms. – user3047512 Dec 7 '13 at 16:00
9

As long as you can run it on a single machine, it's not "Big Data". Your example problem is completely inappropriate to demonstrate anything about it.

Big Data means that the problem sizes are so big that distributing the processing is not an optimization but a fundamental requirement. And functional programming makes it much easier to write correct and efficient distributed code due to immutable data structures and statelessness.

  • "Big Data means that the problem sizes are so big that distributing the processing is not an optimization but a fundamental requirement." - I don't understand what kind of problem can't AT ALL be resolved using one machine, and requires at least N where N > 1... – Shivan Dragon Dec 7 '13 at 14:31
  • 6
    @ShivanDragon: The kind of problem that includes performance requirements that are utterly impossible to satisfy on a single system. Or where the data size is so big that no single system can even store it all. – Michael Borgwardt Dec 7 '13 at 14:42
  • I'm sorry, I see your point now. Is it correct to say that what you're referring to is, more specifically, MapReduce which lives under the umbrella of BigData ? – Shivan Dragon Dec 7 '13 at 15:12
  • Thank you for your input, I agree. Maybe I couldn't find a good simple example to demonstrate my point of view. "Big Data" still a way that developers use data to solve our daily problems taking in consideration the 3Vs definition. I will forget the 3V for a while and talk about the very simple aspect, dealing with Data. If we see that analyzing data in a functional way is expensive, why do we say that "Big Data" needs to be functional ? This is my point . – user3047512 Dec 7 '13 at 15:54
  • 4
    @ShivanDragon, for example, LHC is producing several gigabytes of data per second. Not sure a single machine can even handle such a throughput. – SK-logic Dec 7 '13 at 16:21
4

I don't know scala and therefore I cannot comment on your functional approach, but your code looks like overkill.

Your recursive function on the other hand is inefficient. Because the function calls itself twice, it is of order 2^n, which is highly inefficient. If you want to compare the three approaches, you need to compare three optimal implementations.

The Fibonacci function can be implemented recursively with calling the function only once. Let's take a more generalized definition :

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

The standard special case is :

f0 = 0
f1 = 1

The general recursive function is :

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);
}
  • Thanks! You raised a good point, but There is no efficient way to do it in iterative way. This is a very common prob (Fibonacci suite ). and this is the point out of tackling the same problem using three ways. Can you suggest better way to solve this prob using any programming language, I can re-write that using scala and do the same tests ? – user3047512 Dec 7 '13 at 15:48
  • @user3047512 For a language that supports tail recursion, you can write it with an accumulator. Examples – toasted_flakes Dec 7 '13 at 16:14
  • Scala also support tail recursion as hidden feature oldfashionedsoftware.com/2008/09/27/… – user3047512 Dec 7 '13 at 16:23
  • 1
    @user3047512 Because the recursive solution is a pure function (output depends solely on function args and nothing else), memoization is a good solution. Put simply, every time it would return a value, store the args and result in a key/value hash, and every time the function is run, look there first. This is one of the advantages of pure functions - a future call to this function will find the preexisting hashed value and do zero calculations, because we know the result will not have changed. – Izkata Dec 7 '13 at 18:28
  • @user3047512 The iterative version also looks like a pure function in this case, but that's not always true - in a functional language, I believe it's better enforced by the language... – Izkata Dec 7 '13 at 18:31
0

If functional programming is expensive and memory-consuming for small data, why do we need it for Big Data ?

Specifically I can already see a few applications where this is extremely useful. ex. Statistics, ie calculating a Gaussian function on the fly with different parameters or a set of parameters for data analytics. There is also interpolation for numerical analysis, etc.

What are the best practices to use functional programming (Scala) for Big Data ?

To answer on efficiency there are also techniques to help increase your efficiency in space or time, specifically recursion, tail recursion, continuation passing style, higher-order functions, etc. Some languages have their pros and cons (example lazy vs eager.) For something simple like the Fibonnacci sequence I might just use the imperative way as I find at times some of my co-workers are reluctant and may not be as comfortable with functional programming and hence take up more development time... (I still prefer to use functional programming when I can[applications that I am in charge of]) since I find it quick, clean and "easy to read" (although I find this subjective) code.

Wikipedia has a "fast" version of the fibonnacci sequence posted. 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)
}

Using streams/hof

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

protected by gnat Dec 1 '17 at 19:21

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.