Почему большие данные должны быть функциональными?

Я начал работать над новым проектом, связанным с большими данными, для моей стажировки. Мои менеджеры рекомендовали начать изучать функциональное программирование (они настоятельно рекомендовали Scala). У меня был скромный опыт использования F #, но я не мог понять, насколько важно использовать эту парадигму программирования, поскольку в некоторых случаях это дорого.

Дин выступил с интересной лекцией на эту тему и поделился своими мыслями о том, почему «Большие данные» здесь: http://www.youtube.com/watch?v=DFAdLCqDbLQ Но это было не очень удобно, поскольку большие данные не означают только Hadoop.

Как BigData это очень расплывчатое понятие. Я забыл это на некоторое время. Я попытался придумать один простой пример для сравнения различных аспектов, когда мы имеем дело с данными, чтобы увидеть, дорогой ли функциональный способ или нет. Если функциональное программирование дорого и занимает много памяти для небольших данных, зачем нам оно для больших данных?

Вдали от причудливых инструментов я пытался создать решение для одной конкретной и популярной проблемы, используя три подхода: императивный и функциональный (рекурсия, использование коллекций). Я сравнил время и сложность, чтобы сравнить три подхода.

Я использовал Scala для написания этих функций, так как это лучший инструмент для написания алгоритма с использованием трех парадигм

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

Функциональный способ:

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

Рекурсивный способ:

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

Повелительный путь:

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
}

Я заметил, что функциональное программирование тяжело! это занимает больше времени и занимает больше места в памяти. Я смущен, когда я читаю статью или смотрю доклад, они говорят, что мы должны использовать функциональное программирование в науке о данных. Правда, это проще и продуктивнее, особенно в мире данных. но это занимает больше времени и больше памяти.

Итак, почему мы должны использовать функциональное программирование в больших данных? Каковы лучшие практики использования функционального программирования (Scala) для больших данных?

Вот как я это вижу:

• Давайте на время проигнорируем слова «большие данные», так как это довольно смутное понятие

• Вы упомянули Hadoop. Hadoop выполняет две функции: позволяет вам иметь своего рода «виртуальный» диск, который распределен по нескольким машинам с избыточностью, к которому можно получить доступ через API Hadoop, как если бы это был один унитарный диск. Он называется HDFS, как в распределенной файловой системе Hadoop . Другая вещь, которую делает Hadoop, - это позволяет вам выполнять задания Map-Reduce (это основа для Map-Reduce). Если мы заглянем на страницу MapReduce в Википедии , мы увидим, что:

MapReduce - это модель программирования для обработки больших наборов данных с параллельным распределенным алгоритмом в кластере.

...

Программа MapReduce состоит из процедуры Map (), которая выполняет фильтрацию и сортировку (например, сортировку учащихся по имени по очереди, по одной очереди для каждого имени) и процедуру Reduce (), которая выполняет сводную операцию (например, подсчет числа студентов в каждой очереди, давая имена частот)

...

MapReduce - это платформа для обработки распараллеливаемых задач в огромных наборах данных с использованием большого количества компьютеров.

Также на этой странице Hadoop описывается как

Hadoop, бесплатная и открытая реализация Apache MapReduce.

Теперь Hadoop написан на Java, который не является функциональным языком. Также, если мы посмотрим на страницу Hadoop, мы также найдем пример того, как создать задание MapReduce в Java и развернуть его в кластере Hadoop .

Вот Java-пример задания Fibonnaci MapReduce для Hadoop.

Я надеюсь, что это ответит на ваш вопрос, а именно, что BigData и, в частности, задача MapReduce, создающая Фибоначчи, «не нуждается» в функциональности, иначе вы можете реализовать ее на языках OO, если хотите (например).

Конечно, это не означает, что BigData «должен» быть только OO. Вы можете очень хорошо использовать функциональный язык для реализации работы, подобной MapReduce. Вы можете, например, использовать Scala с Hadoop, если хотите, через Scalding .

Я думаю, стоит упомянуть и другие моменты.

При выполнении рекурсии в Scala, если ваш код позволяет это сделать, Scala выполнит хвостовую оптимизацию . Однако, поскольку JVM (пока) не поддерживает оптимизацию хвостовых вызовов , Scala достигает этого, заменяя во время компиляции ваши рекурсивные вызовы кодом, эквивалентным циклам, как описано здесь . По сути, это означает, что делать рекурсивные и нерекурсивные тесты кода с использованием Scala бессмысленно, так как они оба в конечном итоге делают одно и то же во время выполнения.

Пока вы можете запустить его на одной машине, это не «большие данные». Ваша проблема с примером совершенно неуместна, чтобы что-то демонстрировать.

Большие данные означают, что размеры проблем настолько велики, что распределение обработки - это не оптимизация, а фундаментальное требование. А функциональное программирование значительно облегчает написание правильного и эффективного распределенного кода благодаря неизменным структурам данных и отсутствию состояния.

Я не знаю scala и поэтому не могу прокомментировать ваш функциональный подход, но ваш код выглядит излишним.

Ваша рекурсивная функция с другой стороны неэффективна. Поскольку функция вызывает себя дважды, она имеет порядок 2 ^ n, что крайне неэффективно. Если вы хотите сравнить три подхода, вам нужно сравнить три оптимальные реализации.

Функция Фибоначчи может быть реализована рекурсивно с вызовом функции только один раз. Давайте возьмем более обобщенное определение:

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

Стандартный особый случай:

f0 = 0
f1 = 1

Общая рекурсивная функция:

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

Если функциональное программирование дорого и занимает много памяти для небольших данных, зачем нам оно для больших данных?

В частности, я уже вижу несколько приложений, где это чрезвычайно полезно. ех. Статистика, то есть вычисление функции Гаусса на лету с различными параметрами или набором параметров для анализа данных. Существует также интерполяция для численного анализа и т. Д.

Каковы лучшие практики использования функционального программирования (Scala) для больших данных?

Чтобы ответить на вопрос об эффективности, существуют также методы, помогающие повысить эффективность в пространстве или времени, в частности рекурсия, хвостовая рекурсия , стиль передачи продолжения , функции высшего порядка и т. Д. У некоторых языков есть свои плюсы и минусы (например, «ленивый» или «нетерпеливый»). что-то простое, такое как последовательность Фибоначчи, я мог бы просто использовать императивный способ, поскольку иногда я обнаружил, что некоторые из моих коллег неохотны и могут не чувствовать себя так комфортно с функциональным программированием и поэтому занимают больше времени на разработку ... (Я все еще предпочитаю используйте функциональное программирование, когда я могу [приложения, за которые я отвечаю]), так как я нахожу это быстрым, чистым и «легким для чтения» (хотя я нахожу это субъективным) кодом.

В Википедии опубликована «быстрая» версия последовательности Фибоначчи. 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)
}

Использование потоков / hof

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