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

397

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

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

выбирать
источник
6
Так же, как при программировании обязательно, что бы это ни было.
Р. Мартиньо Фернандес
3
@jldupont: чтобы вернуть результат вычисления, конечно. Существует множество бесплатных программ с побочными эффектами. Они просто не могут делать ничего, кроме вычислений на их входе. Но это все еще полезно.
2010 года
24
Я могу сделать это так плохо, как вам захочется, плохо написав свой функциональный код! * ухмыляется * Я думаю, что вы спрашиваете: «Есть ли проблема, для которой самый известный неразрушающий алгоритм асимптотически хуже, чем самый известный разрушительный алгоритм, и если да, то насколько?» ... это верно? ?
Itowlson
2
Не могли бы вы привести пример типа замедления, который вас интересует. Ваш вопрос немного расплывчатый.
Питер Рекор
5
Пользователь удалил свой ответ, но он утверждал, что функциональная версия задачи с 8 ферзями работала более чем за минуту при n = 13. Он признал, что она написана не очень хорошо, поэтому я решил написать свою собственную версию 8 королев в F #: pastebin.com/ffa8d4c4 . Излишне говорить, что моя чисто функциональная программа вычисляет n = 20 всего за секунду.
Джульетта

Ответы:

531

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

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

Ссылки

Брайан Кэмпбелл
источник
50
Пиппингер является бесспорным авторитетом в этом вопросе. Но следует подчеркнуть, что его результаты теоретические , а не практические. Когда дело доходит до того, чтобы сделать функциональные структуры данных практичными и эффективными, вы не можете добиться большего успеха, чем Окасаки.
Норман Рэмси
6
itowlson: Я должен признать, что я не читал достаточно Пиппенгера, чтобы ответить на ваш вопрос; он был опубликован в рецензируемом журнале, цитируемом Окасаки, и я прочитал его достаточно, чтобы определить, что его утверждения относятся к этому вопросу, но недостаточно, чтобы понять доказательства. Непосредственные навынос , что я получаю для реальных последствий является то , что она тривиальна для преобразования O ( п алгоритма) нечистого в O ( N журнал N ) чистые один, просто имитируя изменяемые памяти , используя сбалансированное бинарное дерево. Есть проблемы, которые не могут быть лучше, чем это; Я не знаю, являются ли они чисто теоретическими.
Брайан Кэмпбелл
3
Результат Пиппенгера делает два важных допущения, ограничивающих его область: он учитывает «оперативные» или «реактивные» вычисления (а не обычную модель вычислений, отображающих конечные входные данные на один выход) и «символические» вычисления, где входные данные представляют собой последовательности атомы, которые можно проверить только на равенство (т. е. интерпретация входных данных чрезвычайно примитивна).
Крис Конвей
2
Очень хороший ответ; Я хотел бы добавить, что для чисто функциональных языков не существует универсально согласованной модели сложности вычислений, в то время как в нечистом мире машина ОЗУ с единичной стоимостью является относительно стандартной (так что это затрудняет сравнение). Также обратите внимание, что верхнюю границу разницы Lg (N) в чистом / нечистом можно очень легко объяснить, если взглянуть на реализацию массивов на чистом языке (это стоит lg (n) за операцию (и вы получаете историю)) ,
user51568
4
Важный момент: тщательный перевод чисто функциональной спецификации в более сложную, эффективную, чисто функциональную реализацию не принесет особой пользы, если вы собираетесь в конечном итоге - автоматически или вручную - перевести ее в еще более эффективный нечистый код. Примесь не имеет большого значения, если вы можете держать ее в клетке, например, запирая ее в функции без внешних побочных эффектов.
Робин Грин
44

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

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

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

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

jkff
источник
3
Если набор данных помещается в физическую память, доступ к нему осуществляется через O (1), поскольку можно найти абсолютную верхнюю границу количества времени для чтения любого элемента. Если набор данных этого не делает, вы говорите о вводе-выводе, и это, безусловно, будет доминирующим фактором, однако программа написана.
Donal Fellows
Ну, конечно, я говорю о O (log n) операциях доступа к внешней памяти. Однако в любом случае я говорил о bs: внешняя память также может быть O (1) -адресуемой ...
jkff
2
Я думаю, что одна из самых важных вещей, которую императивное программирование приобретает в сравнении с функциональным программированием, - это способность хранить ссылки на многие различные аспекты одного состояния и генерировать новое состояние так, чтобы все эти ссылки указывали на соответствующие аспекты нового состояния. Использование функционального программирования потребует замены операций прямой разыменования на операции поиска, чтобы найти соответствующий аспект конкретной версии текущего общего состояния.
Суперкат
Даже модель указателя (O (log n) доступ к памяти, грубо говоря) не является физически реалистичной в чрезвычайно больших масштабах. Скорость света ограничивает то, как быстро различные части вычислительного оборудования могут связываться друг с другом, в то время как в настоящее время считается, что максимальный объем информации, который может храниться в данной области, ограничен ее площадью поверхности.
Dfeuer
36

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

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

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

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

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

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

Паскаль Куок
источник
4

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

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

Брайан
источник
6
Фиксированная верхняя граница использования памяти - это не то, как люди анализируют подобные вещи; вы предполагаете сколь угодно большую, но конечную память. При реализации алгоритма меня интересует, как он будет масштабироваться от самого простого ввода до любого произвольного размера ввода. Если вы устанавливаете фиксированную верхнюю границу использования памяти, почему бы вам не установить фиксированную верхнюю границу того, как долго вы будете выполнять вычисления, и сказать, что все равно O (1)?
Брайан Кэмпбелл
@ Брайан Кэмпбелл: это правда. Я просто предполагаю, что если вы хотите, вы можете игнорировать разницу в постоянном факторе во многих случаях на практике. При компромиссе между памятью и временем все равно нужно помнить о разнице, чтобы убедиться, что использование в m раз больше памяти сокращает время выполнения по крайней мере на коэффициент log (m).
Брайан