Есть ли функциональный алгоритм, который быстрее императивного?

Question

Я ищу алгоритм (или аргумент такого алгоритма) в функциональном стиле, который быстрее, чем императивный.

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

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

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

Но есть ликакие-либо алгоритмы, которые быстрее в функциональном стиле или есть возможности для настройки аргументов такого алгоритма?

Answer 1

Простое рассуждение. Я не ручаюсь за терминологию, но, похоже, это имеет смысл.

• Функциональная программа, подлежащая выполнению, должна быть преобразована в некоторый набор машинных инструкций.
• Все машины (о которых я слышал) являются обязательными.
• Таким образом, для каждой функциональной программы существует императивная программа (грубо говоря, на языке ассемблера), эквивалентная ей.

Итак, вам, вероятно, придется довольствоваться «выразительностью», пока мы не получим «функциональные компьютеры».

Answer 2

Краткий ответ:

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

QuickSort, например, очень хорошо масштабируется при использовании с неизменяемыми коллекциями: http://en.wikipedia.org/wiki/Quicksort#Parallelization

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

Может даже случиться, что ваш язык программирования может выполнить эту оптимизацию для вас, как с плагином scalaCL, который скомпилирует код для запуска на вашем GPU. (Мне интересно, если SIMD-инструкции делают этот процессор «функциональным»)

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

Answer 3

FWIW есть Чисто функциональные структуры данных , которые выигрывают от функционального программирования.

Есть также хорошая книга Криса Окасаки Чисто функциональные структуры данных , в которой представлены структуры данных с точки зрения функциональных языков.

Еще одна интересная статья Объявление о параллельных коллекциях Intel для Haskell 0.1 , о параллельном программировании, они отмечают:

Ну, бывает, что понятие CnC шага - это чистая функция . Шаг ничего не делает, кроме чтения своих входов и производить теги и элементы в качестве вывода. это дизайн был выбран, чтобы довести CnC до этого неуловимое, но чудесное место под названием детерминированный параллелизм . Решение не имеет ничего общего с языковые предпочтения. (И действительно, первичные реализации CnC предназначены для C ++ и Java.)

И все же, какое великолепное совпадение у Haskell и CnC сделал бы! Хаскелл является единственным основным язык, на котором мы можем (1) обеспечить шаги должны быть чистыми, и (2) напрямую признать (и использовать!) факт что оба шага и граф выполнения являются чистыми.

Добавьте к этому тот факт, что Haskell удивительно расширяемый и, таким образом, CnC "библиотека" может чувствовать себя почти как предметно-ориентированный язык.

Это не говорит о производительности - они обещают обсудить некоторые детали реализации и производительность в будущих публикациях, - но Haskell с его «чистотой» прекрасно вписывается в параллельное программирование.

Answer 4

Можно утверждать, что все программы сводятся к машинному коду.

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

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

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

Answer 5

Чтобы развить ответ Ясира Арсанукаева, чисто функциональные структуры данных могут быть быстрее, чем изменяемые структуры данных, в некоторых ситуациях, потому что они разделяют части своей структуры.Таким образом, в местах, где вам может потребоваться скопировать весь массив или список на императивном языке, где вы можете избежать дробного копирования, поскольку вы можете изменить (и скопировать) только небольшую часть структуры данных.Списки на функциональных языках похожи на это - несколько списков могут иметь один и тот же хвост, поскольку ничего нельзя изменить.(Это может быть сделано на императивных языках, но обычно это не так, потому что в рамках императивной парадигмы люди обычно не говорят о неизменных данных.)

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

Answer 6

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

Я не исключаю этой возможности. :)