Кто-нибудь знает, что является наихудшим из возможных асимптотических замедлений, которые могут произойти, если программирование является чисто функциональным, а не императивным (т.е. допускающим побочные эффекты)?
Пояснение из комментария itowlson : есть ли проблема, для которой самый известный неразрушающий алгоритм асимптотически хуже, чем самый известный разрушительный алгоритм, и если да, то насколько?
Ответы:
Согласно 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 (log (n)) для чтения и записи, но с фиксированной верхней границей использования памяти, вы можете иметь фиксированный объем памяти, заставляя их распад на O (1). Таким образом, функциональная реализация может быть обязательной версией, выполняемой в функциональной реализации ВМ, и поэтому они оба должны иметь одинаковую асимптотическую сложность.
источник
Я бы посоветовал прочитать о производительности Haskell , а затем взглянуть на тесты производительности игры для функциональных языков по сравнению с процедурными / OO.
источник