Функциональное программирование-дорого ли стоит неизменность? [закрытый]

есть куча вещей неправильно с этим в качестве эталона функционального программирования. Основные моменты включают в себя:

• вы используете примитивы,которые могут быть упакованы/распакованы. Вы не пытаетесь проверить накладные расходы на обертывание примитивных объектов, вы пытаетесь проверить неизменность.
• вы выбрали алгоритм, в котором работа на месте необычайно эффективна (и доказуемо). Если вы хотите показать, что существуют алгоритмы, которые быстрее, когда реализовано изменчиво, то это хороший выбор; в противном случае, это, вероятно, будет вводить в заблуждение.
• вы используете неправильную функцию синхронизации. Используйте System.nanoTime.
• тест слишком короток для вас, чтобы быть уверенным, что компиляция JIT не будет значительной частью измеренного времени.
• массив не разбивается эффективным образом.
• массивы изменчивы,поэтому их использование с FP-это странное сравнение.

Так, это сравнение является отличной иллюстрацией того, что вы должны понимать свой язык (и алгоритм) в деталях, чтобы написать высокопроизводительный код. Но это не очень хорошее сравнение FP против non-FP. Если вы хотите этого, проверьте Haskell против C++ в тестовой игре компьютерных языков. Сообщение take-home заключается в том, что штраф обычно не превышает 2 или 3 или около того, но это действительно зависит. (Нет обещаний, что люди Haskell написали самые быстрые алгоритмы возможно, но, по крайней мере, некоторые из них, вероятно, пытались! Опять же, некоторые из Haskell вызывает библиотеки C....)

Теперь предположим, что вам нужен более разумный тест Quicksort, признавая, что это, вероятно, один из худших случаев для FP против изменяемых алгоритмов и игнорируя проблему структуры данных (т. е. делая вид, что у нас может быть неизменяемый массив):

object QSortExample {
  // Imperative mutable quicksort
  def swap(xs: Array[String])(a: Int, b: Int) {
    val t = xs(a); xs(a) = xs(b); xs(b) = t
  }
  def muQSort(xs: Array[String])(l: Int = 0, r: Int = xs.length-1) {
    val pivot = xs((l+r)/2)
    var a = l
    var b = r
    while (a <= b) {
      while (xs(a) < pivot) a += 1
      while (xs(b) > pivot) b -= 1
      if (a <= b) {
        swap(xs)(a,b)
        a += 1
        b -= 1
      }
    }
    if (l<b) muQSort(xs)(l, b)
    if (b<r) muQSort(xs)(a, r)
  }

  // Functional quicksort
  def fpSort(xs: Array[String]): Array[String] = {
    if (xs.length <= 1) xs
    else {
      val pivot = xs(xs.length/2)
      val (small,big) = xs.partition(_ < pivot)
      if (small.length == 0) {
        val (bigger,same) = big.partition(_ > pivot)
        same ++ fpSort(bigger)
      }
      else fpSort(small) ++ fpSort(big)
    }
  }

  // Utility function to repeat something n times
  def repeat[A](n: Int, f: => A): A = {
    if (n <= 1) f else { f; repeat(n-1,f) }
  }

  // This runs the benchmark
  def bench(n: Int, xs: Array[String], silent: Boolean = false) {
    // Utility to report how long something took
    def ptime[A](f: => A) = {
      val t0 = System.nanoTime
      val ans = f
      if (!silent) printf("elapsed: %.3f sec\n",(System.nanoTime-t0)*1e-9)
      ans
    }

    if (!silent) print("Scala builtin ")
    ptime { repeat(n, {
      val ys = xs.clone
      ys.sorted
    }) }
    if (!silent) print("Mutable ")
    ptime { repeat(n, {
      val ys = xs.clone
      muQSort(ys)()
      ys
    }) }
    if (!silent) print("Immutable ")
    ptime { repeat(n, {
      fpSort(xs)
    }) }
  }

  def main(args: Array[String]) {
    val letters = (1 to 500000).map(_ => scala.util.Random.nextPrintableChar)
    val unsorted = letters.grouped(5).map(_.mkString).toList.toArray

    repeat(3,bench(1,unsorted,silent=true))  // Warmup
    repeat(3,bench(10,unsorted))     // Actual benchmark
  }
}

обратите внимание на изменение функциональной Quicksort, так что он проходит только через данные один раз, если вообще возможно и сравнение со встроенной сортировкой. Когда мы запускаем его, мы получаем что-то вроде:

Scala builtin elapsed: 0.349 sec
Mutable elapsed: 0.445 sec
Immutable elapsed: 1.373 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.441 sec
Immutable elapsed: 1.374 sec
Scala builtin elapsed: 0.343 sec
Mutable elapsed: 0.442 sec
Immutable elapsed: 1.383 sec

Итак, помимо изучения того, что попытка написать свой собственный вид-плохая идея, мы обнаруживаем, что существует штраф ~3x для неизменного quicksort, если последний реализуется несколько осторожно. (Вы также можете написать метод trisect, который возвращает три массива: те, которые меньше, те, которые равны, и те, которые больше, чем pivot. Это может ускорить процесс немного больше.)

Я не думаю, что версия Scala на самом деле хвост рекурсивной, так как вы используете Array.concat.

кроме того, только потому, что это идиоматический код Scala, это не означает, что это лучший способ сделать это.

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

см. вопрос переполнения стека как отсортировать массив в Скала? для примера.

неизменность не дорого. Конечно, это может быть дорого, если вы измеряете небольшое подмножество задач, которые должна выполнять программа, и выбираете решение, основанное на изменчивости для загрузки, например, измерение quicksort.

проще говоря, вы не quicksort при использовании чисто функциональных языков.

давайте рассмотрим это с другой стороны. Рассмотрим эти две функции:

// Version using mutable data structures
def tailFrom[T : ClassManifest](arr: Array[T], p: T => Boolean): Array[T] = {
  def posIndex(i: Int): Int = {
    if (i < arr.length) {
      if (p(arr(i)))
        i
      else
        posIndex(i + 1)
    } else {
      -1
    }
  }

  var index = posIndex(0)

  if (index < 0) Array.empty
  else {
    var result = new Array[T](arr.length - index)
    Array.copy(arr, index, result, 0, arr.length - index)
    result
  }
}

// Immutable data structure:

def tailFrom[T](list: List[T], p: T => Boolean): List[T] = {
  def recurse(sublist: List[T]): List[T] = {
    if (sublist.isEmpty) sublist
    else if (p(sublist.head)) sublist
    else recurse(sublist.tail)
  }
  recurse(list)
}

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

когда вы программируете с неизменяемыми структурами данных, вы структурируете свой код, чтобы использовать его сильные стороны. Это не просто тип данных или даже отдельные алгоритмы. Программа будет предназначен по-другому.

который является, почему бенчмаркинг-это, как правило, бессмысленно. Либо вы выбираете алгоритмов естественно для того или иного стиля, и этот стиль выигрывает, или вы оцениваете все приложение, что часто непрактично.

сортировка массива-это, например, самая важная задача во Вселенной. Неудивительно, что многие элегантные "неизменяемые" стратегии/реализации плохо работают на микрочипе "сортировать массив". Однако это не означает, что неизменность стоит дорого "вообще". Существует много задач, где неизменяемые реализации будут выполняться сопоставимо с изменяемыми, но сортировка массива часто не является одной из них.

Если вы просто переписываете свои императивные алгоритмы и структуры данных на функциональный язык, это действительно будет дорого и бесполезно. Чтобы вещи сияли, вы должны использовать функции, доступные только в функциональном программировании: сохранение структур данных, ленивые оценки и т. д.

стоимость неизменности в Scala

вот версия, которая почти так же быстро, как Java один. ;)

object QuickSortS {
  def sort(xs: Array[Int]): Array[Int] = {
    val res = new Array[Int](xs.size)
    xs.copyToArray(res)
    (new QuickSortJ).sort(res)
    res
  }
}

эта версия создает копию массива, сортирует его на месте с помощью версии Java и возвращает копию. Scala не заставляет вас использовать неизменяемую структуру внутри.

таким образом, преимущество Scala заключается в том, что вы можете использовать изменчивость и неизменность по своему усмотрению. Недостатком является то, что если вы делаете это неправильно вы на самом деле вы не получаете преимущества неизменности.

QuickSort, как известно, быстрее, когда делается на месте, так что это вряд ли справедливое сравнение!

сказав, что... Матрица.функция concat? Если ничего другого, вы показываете, как тип коллекции, оптимизированный для императивного программирования, особенно медленный, когда вы пытаетесь использовать его в функциональном алгоритме; почти любой другой выбор будет быстрее!

---

другое очень важный момент для рассмотрения, возможно the самый важный вопрос, когда сравнение двух подходов: "насколько хорошо это масштабируется до нескольких узлов / ядер?"

скорее всего, если вы ищете неизменный quicksort, то вы делаете это, потому что вы на самом деле хотите параллельный quicksort. В Википедии есть несколько цитат на эту тему:http://en.wikipedia.org/wiki/Quicksort#Parallelizations

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

прямо сейчас GPU в моей системе имеет 128 ядер, доступных мне, если бы я мог просто запустить код Scala на нем, и это на простой настольной системе на два года отстает от текущего поколения.

Как это будет складываться против однопоточного императивного подхода, мне интересно...

возможно, поэтому более важный вопрос:

"учитывая, что отдельные ядра не будет быстрее, и синхронизация / блокировка представляет реальную проблему для распараллеливания, является ли изменчивость дорогой?"

было сказано, что OO-Программирование использует абстракцию, чтобы скрыть сложность, а функциональное программирование использует неизменность для удаления сложности. В гибридном мире Scala мы можем использовать OO, чтобы скрыть императивный код, оставляя код приложения не более мудрым. Действительно, библиотеки коллекций используют много императивного кода, но это не значит, что мы не должны их использовать. Как уже сказали, использовать с осторожностью, вы действительно получаете лучшее из обоих миров здесь.