Функциональное программирование - неизлечимо дорогостоящее?

Ответ 1

Так как здесь есть несколько заблуждений, Id хотел бы прояснить некоторые моменты.

• Быстрая сортировка "на месте" на самом деле не на месте (и quicksort не по определению на месте). Он требует дополнительного хранения в виде пространства стека для рекурсивного шага, который в лучшем случае находится в порядке O (log n), но O (n) в худшем случае.

• Реализация функционального варианта quicksort, который работает на массивах, поражает цель. Массивы никогда не являются неизменными.

• "Правильная" функциональная реализация quicksort использует неизменные списки. Это, конечно, не на месте, но у него есть такое же наихудшее асимптотическое время выполнения (O (n ^ 2)) и пространственная сложность (O ( n)), как процедурная версия на месте.

  В среднем, его время работы по-прежнему совпадает с временем выполнения варианта (O (n log n)). Однако его пространственная сложность по-прежнему равна O ( n).

Существует два очевидных недостатка функциональной реализации quicksort. В следующем примере рассмотрим эту ссылочную реализацию в Haskell (я не знаю Scala...) из Введение Haskell:

qsort []     = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
    where lesser  = (filter (< x) xs)
          greater = (filter (>= x) xs)

• Первым недостатком является выбор поворотного элемента, который является очень негибким. Сила современных реализаций быстрой сортировки в значительной степени зависит от умного выбора точки поворота (сравните "Инженерная функция сортировки" Bentley и др.). Вышеупомянутый алгоритм в этом отношении является плохим, что значительно ухудшает среднюю производительность.

• Во-вторых, этот алгоритм использует конкатенацию списков (вместо построения списка), которая является операцией O (n). Это не влияет на асимптотическую сложность, а на ее измеримый фактор.

Третий недостаток несколько скрыт: в отличие от варианта "на месте", эта реализация постоянно запрашивает память из кучи для cons-элементов списка и потенциально рассеивает память повсюду. В результате этот алгоритм имеет очень низкую локальность кэша. Я не знаю, могут ли умные распределители в современных языках функционального программирования смягчить это, но на современных машинах промахи промахов стали крупным производителем.

Какой вывод? В отличие от других, я бы не сказал, что quicksort по своей сути является императивом, и поэтому он плохо работает в среде FP. Напротив, я бы сказал, что quicksort является прекрасным примером функционального алгоритма: он легко трансформируется в неизменяемую среду, его асимптотическое время работы и сложность пространства совпадают с процедурной реализацией, и даже в его процедурной реализации используется рекурсия.

Но этот алгоритм все еще хуже, когда он привязан к неизменяемому домену. Причиной этого является то, что алгоритм обладает своеобразным свойством извлекать выгоду из множества (иногда низкоуровневых) тонкой настройки, которые могут быть эффективно реализованы только на массивах. Наивное описание quicksort пропускает все эти тонкости (как в функциональном, так и в процедурном варианте).

После прочтения "Инженерная функция сортировки" я больше не могу рассматривать quicksort элегантный алгоритм. Реализовано эффективно, это неуклюжий беспорядок, работа инженера, а не художники (не девальвировать инженерное дело, это имеет свою собственную эстетику).

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

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

Итак, чтобы ответить на исходный вопрос: " - неизменяемость дорогостоящая?". В частном случае quicksort есть стоимость, которая действительно является результатом неизменности. Но в целом нет.

Ответ 2

С этим связано множество ошибок, которые являются эталоном функционального программирования. Основные моменты:

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

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

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

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

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

Как бы это сложилось против однопоточного императивного подхода? Интересно...

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

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

Ответ 7

Стоимость неизменности в 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 заключается в том, что вы можете использовать изменчивость и неизменность по своему усмотрению. Недостатком является то, что если вы сделаете это неправильно, вы действительно не получите преимущества неизменности.

Ответ 8

Неизменность не дорогая. Конечно, это может быть дорого, если вы измеряете небольшое подмножество задач, которые должна выполнить программа, и выберите решение, основанное на изменчивости для загрузки, например, измерение 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)
}

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

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

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

Ответ 9

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