Функциональное программирование - дороговизна неизменности?
Вопрос состоит из двух частей. Первое концептуально. Далее более конкретно рассматривается тот же вопрос в Scala.
- Делает ли использование только неизменяемых структур данных в языке программирования практической реализацией определенных алгоритмов / логики по вычислительной стоимости? Это привлекает тот факт, что неизменность является основным принципом чисто функциональных языков. Есть ли другие факторы, которые влияют на это?
- Давайте рассмотрим более конкретный пример. Быстрая сортировка обычно изучается и реализуется с помощью изменяемых операций над структурой данных в памяти. Как реализовать такую вещь функциональным способом PURE с сопоставимыми затратами на вычисления и хранение с изменяемой версией. Конкретно в Скале. Я включил некоторые грубые тесты ниже.
Больше деталей:
Я пришел из опыта программирования (C++, Java). Я изучал функциональное программирование, в частности, Scala.
Некоторые из основных принципов чисто функционального программирования:
- Функции являются гражданами первого класса.
- Функции не имеют побочных эффектов и, следовательно, объекты / структуры данных являются неизменными.
Несмотря на то, что современные JVM чрезвычайно эффективны при создании объектов, а сборка мусора очень недорога для недолговечных объектов, вероятно, все же лучше минимизировать создание объектов, верно? По крайней мере, в однопоточном приложении, где параллелизм и блокировка не являются проблемой. Поскольку Scala является гибридной парадигмой, при необходимости можно написать императивный код с изменяемыми объектами. Но, как тот, кто провел много лет, пытаясь повторно использовать объекты и минимизировать распределение. Мне бы хотелось хорошее понимание школы мысли, которая бы этого даже не допустила.
Как частный случай, я был немного удивлен этим фрагментом кода в этом уроке 6. Он имеет Java-версию Quicksort, за которой следует аккуратная Scala-реализация.
Вот моя попытка сравнить реализации. Я не сделал детальное профилирование. Но я предполагаю, что версия Scala медленнее, потому что количество выделенных объектов является линейным (по одному на каждый вызов рекурсии). Есть ли какой-то шанс, что в игру могут вступить оптимизации хвостового вызова? Если я прав, Scala поддерживает оптимизацию хвостовых вызовов для рекурсивных вызовов. Так что, это должно только помочь. Я использую Scala 2.8.
Версия Java
public class QuickSortJ {
public static void sort(int[] xs) {
sort(xs, 0, xs.length -1 );
}
static void sort(int[] xs, int l, int r) {
if (r >= l) return;
int pivot = xs[l];
int a = l; int b = r;
while (a <= b){
while (xs[a] <= pivot) a++;
while (xs[b] > pivot) b--;
if (a < b) swap(xs, a, b);
}
sort(xs, l, b);
sort(xs, a, r);
}
static void swap(int[] arr, int i, int j) {
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}
Scala версия
object QuickSortS {
def sort(xs: Array[Int]): Array[Int] =
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(
sort(xs filter (pivot >)),
xs filter (pivot ==),
sort(xs filter (pivot <)))
}
}
Scala Code для сравнения реализаций
import java.util.Date
import scala.testing.Benchmark
class BenchSort(sortfn: (Array[Int]) => Unit, name:String) extends Benchmark {
val ints = new Array[Int](100000);
override def prefix = name
override def setUp = {
val ran = new java.util.Random(5);
for (i <- 0 to ints.length - 1)
ints(i) = ran.nextInt();
}
override def run = sortfn(ints)
}
val benchImmut = new BenchSort( QuickSortS.sort , "Immutable/Functional/Scala" )
val benchMut = new BenchSort( QuickSortJ.sort , "Mutable/Imperative/Java " )
benchImmut.main( Array("5"))
benchMut.main( Array("5"))
Результаты
Время в миллисекундах для пяти последовательных прогонов
Immutable/Functional/Scala 467 178 184 187 183
Mutable/Imperative/Java 51 14 12 12 12
9 ответов
Так как здесь есть несколько заблуждений, я хотел бы уточнить некоторые моменты.
Быстрая сортировка "на месте" на самом деле не на месте (а быстрая сортировка по определению не на месте). Для рекурсивного шага требуется дополнительное хранилище в виде стекового пространства, которое в лучшем случае имеет порядок O (log n), а в худшем - O(n).
Реализация функционального варианта быстрой сортировки, работающего с массивами, побеждает цель. Массивы никогда не являются неизменяемыми.
"Правильная" функциональная реализация быстрой сортировки использует неизменяемые списки. Это, конечно, не на месте, но у него та же асимптотическая среда выполнения в худшем случае (O(n^ 2)) и пространственная сложность (O(n)), что и у процедурной версии на месте.
В среднем время его работывсе еще находится на одном уровне с вариантом на месте (O (n logn)). Его пространственная сложность, однако, все еще O(n).
Естьдва очевидных недостатка функциональной реализации быстрой сортировки. Далее давайте рассмотрим эту эталонную реализацию на Haskell (я не знаю Scala …) из введения на Haskell:
qsort [] = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
where lesser = (filter (< x) xs)
greater = (filter (>= x) xs)
Первый недостаток - выбор поворотного элемента, который очень негибкий. Сила современных реализаций быстрой сортировки в значительной степени зависит от разумного выбора стержня (сравните "Разработка функции сортировки" Бентли и др.). Вышеупомянутый алгоритм плох в этом отношении, что значительно ухудшает среднюю производительность.
Во-вторых, этот алгоритм использует конкатенацию списка (вместо построения списка), которая является операцией O(n). Это не влияет на асимптотическую сложность, но это измеримый фактор.
Третий недостаток несколько скрыт: в отличие от варианта "на месте", эта реализация постоянно запрашивает память из кучи для cons-ячеек списка и потенциально разбрасывает память повсюду. В результате этот алгоритм имеет очень плохую локальность кэша. Я не знаю, могут ли интеллектуальные распределители в современных языках функционального программирования смягчить это - но на современных машинах ошибки кэширования стали основным фактором снижения производительности.
Какой вывод? В отличие от других, я бы не сказал, что быстрая сортировка по своей сути обязательна, и поэтому она плохо работает в среде FP. Наоборот, я бы сказал, что быстрая сортировка является прекрасным примером функционального алгоритма: он плавно переходит в неизменяемую среду, его асимптотическое время выполнения и сложность пространства находятся на одном уровне с процедурной реализацией, и даже его процедурная реализация использует рекурсию.
Но этот алгоритм все еще работает хуже, когда ограничен неизменной областью. Причина этого заключается в том, что алгоритм обладает особым свойством извлекать выгоду из большой (иногда низкоуровневой) тонкой настройки, которая может быть эффективно выполнена только для массивов. Наивное описание быстрой сортировки пропускает все эти тонкости (как в функциональном, так и в процедурном варианте).
После прочтения "Разработка функции сортировки" я больше не могу считать быструю сортировку элегантным алгоритмом. Реализовано эффективно, это неуклюжий беспорядок, работа инженера, а не художника (не для того, чтобы обесценить инженерию! У этого есть своя эстетика).
Но я также хотел бы отметить, что этот момент характерен для быстрой сортировки. Не каждый алгоритм поддается одинаковой низкоуровневой настройке. Многие алгоритмы и структуры данных действительно могут быть выражены без потери производительности в неизменной среде.
А неизменяемость может даже снизить затраты на производительность, устраняя необходимость в дорогостоящих копиях или межпотоковой синхронизации.
Итак, чтобы ответить на оригинальный вопрос: "Стоит ли неизменность?- В конкретном случае быстрой сортировки есть стоимость, которая действительно является результатом неизменности. Но в целом нет.
С этим как с эталоном функционального программирования связано не так много вещей. Основные моменты включают в себя:
- Вы используете примитивы, которые могут быть упакованы / распакованы. Вы не пытаетесь проверить накладные расходы на обертывание примитивных объектов, вы пытаетесь проверить неизменность.
- Вы выбрали алгоритм, в котором операция на месте необычайно эффективна (и доказуемо такова). Если вы хотите показать, что существуют алгоритмы, которые быстрее, когда они реализованы изменчиво, то это хороший выбор; в противном случае это может ввести в заблуждение.
- Вы используете неправильную функцию синхронизации. использование
System.nanoTime, - Тест слишком короткий, чтобы вы могли быть уверены, что JIT-компиляция не будет существенной частью измеренного времени.
- Массив не разделен эффективным способом.
- Массивы являются изменяемыми, поэтому использование их с FP в любом случае является странным сравнением.
Таким образом, это сравнение является отличной иллюстрацией того, что вы должны подробно понимать свой язык (и алгоритм), чтобы писать высокопроизводительный код. Но это не очень хорошее сравнение FP и non-FP. Если вы хотите, посмотрите Haskell vs. C++ в игре "Тестирование компьютерных языков". Главное, что здесь говорится, что штраф обычно составляет не более 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
}
}
Обратите внимание на модификацию функциональной быстрой сортировки, поэтому она проходит через данные только один раз, если это вообще возможно, и сравнение со встроенной сортировкой. Когда мы запускаем его, мы получаем что-то вроде:
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, который возвращает три массива: те, которые меньше, те, которые равны, и те, которые больше, чем пивот. Это может немного ускорить процесс.)
Я не думаю, что версия Scala на самом деле является хвостовой рекурсивной, так как вы используете Array.concat,
Кроме того, то, что это идиоматический код Scala, не означает, что это лучший способ сделать это.
Лучший способ сделать это - использовать одну из встроенных функций сортировки Scala. Таким образом, вы получаете гарантию неизменности и знаете, что у вас быстрый алгоритм.
См. Вопрос переполнения стека. Как отсортировать массив в Scala? для примера.
Неизменность не дорогая. Конечно, это может быть дорого, если вы измеряете небольшое подмножество задач, которые должна выполнить программа, и выбираете решение, основанное на изменчивости для загрузки, например, измерение быстрой сортировки.
Проще говоря, вы не будете быстро сортировать при использовании чисто функциональных языков.
Давайте рассмотрим это с другой стороны. Давайте рассмотрим эти две функции:
// 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 заключается в том, что вы можете использовать изменчивость и неизменность по своему усмотрению. Недостатком является то, что если вы сделаете это неправильно, вы не получите преимуществ неизменности.
Сортировка массива - самая насущная задача во вселенной. Неудивительно, что многие элегантные "неизменные" стратегии / реализации плохо терпят неудачу в микробенчмарке "сортировать массив". Это, однако, не означает, что неизменность является дорогостоящей "в целом". Существует много задач, в которых неизменяемые реализации будут выполнять сравнимо с изменяемыми, но сортировка массивов часто не входит в их число.
Известно, что быстрая сортировка выполняется быстрее на месте, поэтому вряд ли это справедливое сравнение!
Сказав это... Array.concat? Если ничего другого, вы показываете, как тип коллекции, оптимизированный для императивного программирования, особенно медленный, когда вы пытаетесь использовать его в функциональном алгоритме; почти любой другой выбор будет быстрее!
Еще один очень важный момент, который следует учитывать, возможно, наиболее важный вопрос при сравнении двух подходов: "насколько хорошо это масштабируется до нескольких узлов / ядер?"
Скорее всего, если вы ищете неизменяемую быструю сортировку, то вы делаете это, потому что вы действительно хотите параллельную быструю сортировку. В Википедии есть несколько цитат на эту тему: http://en.wikipedia.org/wiki/Quicksort.
Scala-версия может просто разветвляться перед повторным использованием функции, что позволяет ей очень быстро отсортировать список, содержащий миллиарды записей, если у вас достаточно ядер.
Прямо сейчас, графический процессор в моей системе имеет 128 ядер, которые мне доступны, если бы я мог просто запустить на нем код Scala, и это на простой настольной системе на два года меньше, чем у нынешнего поколения.
Интересно, как бы это сложилось против однопоточного императивного подхода?
Возможно, поэтому более важный вопрос:
"Учитывая, что отдельные ядра не будут работать быстрее, а синхронизация / блокировка представляет собой реальную проблему для распараллеливания, дорогая изменчивость?"
Если вы просто переписываете свои императивные алгоритмы и структуры данных на функциональный язык, это действительно будет дорого и бесполезно. Чтобы все было блестяще, вы должны использовать функции, доступные только в функциональном программировании: постоянство структур данных, ленивые вычисления и т. Д.
Говорят, что ОО-программирование использует абстракцию, чтобы скрыть сложность, а функциональное программирование использует неизменность, чтобы убрать сложность. В гибридном мире Scala мы можем использовать ОО, чтобы скрыть императивный код, не оставляя код приложения более мудрым. Действительно, библиотеки коллекций используют много императивного кода, но это не значит, что мы не должны их использовать. Как уже говорили другие, используя осторожно, вы действительно получите лучшее из обоих миров здесь.