Эффективность чисто функционального программирования

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

Разъяснение из комментария itowlson: есть ли проблема, для которой самый известный неразрушающий алгоритм асимптотически хуже, чем самый известный разрушительный алгоритм, и если да, то насколько?

Источник

6 ответов

Решение

Согласно Pippenger [1996], при сравнении системы Lisp, которая является чисто функциональной (и имеет строгую семантику оценки, а не ленивую), с системой, которая может изменять данные, алгоритм, написанный для нечистого Lisp, который работает в O (n), может быть переведен к алгоритму на чистом Лиспе, который выполняется за O (n log n) времени (на основе работы Бен-Амрама и Галиля [1992] о моделировании оперативной памяти с использованием только указателей). Пиппенгер также устанавливает, что существуют алгоритмы, для которых это лучшее, что вы можете сделать; Есть проблемы, которые являются O (n) в нечистой системе, которые являются Ω (n log n) в чистой системе.

Есть несколько предостережений об этой статье. Наиболее важным является то, что он не предназначен для ленивых функциональных языков, таких как Haskell. Берд, Джонс и Де Моор [1997] демонстрируют, что проблема, построенная Пиппенгером, может быть решена на ленивом функциональном языке за O (n) время, но они не устанавливают (и, насколько я знаю, никто не знает), не ленивый функциональный язык может решить все проблемы за то же самое асимптотическое время выполнения, что и язык с мутацией.

Задача, построенная Пиппенгером, требует, чтобы Ω (n log n) была специально построена для достижения этого результата, и она не обязательно отражает практические проблемы реального мира. Есть несколько ограничений на проблему, которые немного неожиданны, но необходимы для доказательства; в частности, проблема требует, чтобы результаты вычислялись в режиме онлайн без возможности доступа к будущим входным данным и чтобы этот вход состоял из последовательности атомов из неограниченного набора возможных атомов, а не из набора фиксированного размера. И статья только устанавливает (нижняя граница) результаты для нечистого алгоритма линейного времени работы; для задач, которые требуют большего времени выполнения, возможно, что дополнительный коэффициент O (log n), наблюдаемый в линейной задаче, может быть "поглощен" в процессе дополнительных операций, необходимых для алгоритмов с большим временем выполнения. Эти уточнения и открытые вопросы кратко исследованы Бен-Амрамом [1996].

На практике многие алгоритмы могут быть реализованы на чисто функциональном языке с той же эффективностью, что и на языке с изменяемыми структурами данных. Хороший справочник по методам, которые следует использовать для эффективной реализации чисто функциональных структур данных, см. В "Чисто функциональных структурах данных" Криса Окасаки [Okasaki 1998] (которая является расширенной версией его диссертации [Okasaki 1996]).

Любой, кому нужно реализовать алгоритмы на чисто функциональных структурах данных, должен прочитать Okasaki. В худшем случае вы всегда можете получить замедление O (log n) для каждой операции, моделируя изменяемую память с помощью сбалансированного двоичного дерева, но во многих случаях вы можете добиться значительно большего, чем это, и Окасаки описывает множество полезных методов, от амортизированных до реальных. время те, которые делают амортизированную работу постепенно. С чисто функциональными структурами данных может быть немного сложно работать и анализировать, но они предоставляют много преимуществ, таких как ссылочная прозрачность, которые полезны при оптимизации компилятора, в параллельных и распределенных вычислениях, а также в реализации таких функций, как управление версиями, отмена и откат.

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

Рекомендации

Источник

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

  • Вышеупомянутый союз-находка
  • Хеш-таблицы
  • Массивы
  • Некоторые графовые алгоритмы
  • ...

Тем не менее, мы предполагаем, что в "императивных" языках доступ к памяти равен O(1), тогда как в теории это не может быть асимптотически (т.е. для неограниченных размеров задач), а доступ к памяти в огромном наборе данных всегда равен O (log n), который можно эмулировать на функциональном языке.

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

Источник

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

Тот факт, что другие ответы утверждают, что никогда не может быть никакой разницы и что, например, единственный "недостаток" чисто функционального кода заключается в том, что его можно распараллелить, дает вам представление об информированности / объективности сообщества функционального программирования по этим вопросам.,

РЕДАКТИРОВАТЬ:

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

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

Если строгая функция имеет сложность O(f(n)) на строгом языке, то она имеет сложность O(f(n)) и на ленивом языке. Зачем парится?:)

Источник

С фиксированной верхней границей использования памяти не должно быть никакой разницы.

Эскиз доказательства: учитывая фиксированную верхнюю границу использования памяти, нужно иметь возможность писать виртуальную машину, которая выполняет набор обязательных инструкций с той же асимптотической сложностью, как если бы вы фактически выполняли на этой машине. Это так, потому что вы можете управлять изменяемой памятью как постоянной структурой данных, предоставляя O(log(n)) для чтения и записи, но с фиксированной верхней границей использования памяти, вы можете иметь фиксированный объем памяти, заставляя их распад на O(1). Таким образом, функциональная реализация может быть обязательной версией, выполняемой в функциональной реализации ВМ, и поэтому они оба должны иметь одинаковую асимптотическую сложность.

Источник

Я бы посоветовал прочитать о производительности Haskell, а затем взглянуть на тесты производительности игры для функциональных языков по сравнению с процедурными /OO.

Источник

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

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

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

Функции как типы первого класса

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

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

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

Монады

Это тонкий, но очень мощный конструкт. Это так же эффективно, как ключевое слово yield, используемое для создания классов IEnumerable в C#. По сути, он строит для вас конечный автомат, но ваша логика выглядит линейной.

Ленивая оценка и рекурсия

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

S-выражение

Думаю, я не уверен, куда это поместить, но способность обрабатывать не скомпилированный код как объект (и проверять / изменять его), такой как Lisp S-Expressions или LINQ Expressions, в некотором смысле самый мощный инструмент функционального программирования. Большинство новых.NET "свободно" интерфейсов и DSL используют комбинацию лямбда-синтаксиса и выражений LINQ для создания очень лаконичных API. Не говоря уже о Linq2Sql/Linq2Nhibernate, где ваш код C# "магически" выполняется как SQL, а не как код C#.

Источник
Другие вопросы по тегам