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

Быть ленивым, я не проверяет это, но не должен эту работу

private int FindClosest(IEnumerable<int> numbers, int x)
{
    return
        numbers.Aggregate((r,n) => Math.Abs(r-x) > Math.Abs(n-x) ? n
                                 : Math.Abs(r-x) < Math.Abs(n-x) ? r
                                 : r < x ? n : r);
}

согласно Pippengenge [1996] , при сравнении системы LISP, которая является чисто Функциональный (и имеет строгую оценочную семантику, не лень) к тому, что может мутировать данные, алгоритм, написанный для нечистого LISP, который работает в O ( N ), может быть переведен в алгоритм в чистом Lisp, который работает В O ( N log N ) Время (на основе работы Ben-Amram и Galil [1992] о моделировании памяти произвольного доступа, используя только указатели). Пиппенг также устанавливает, что есть алгоритмы, для которых это лучшее, что вы можете сделать; Существуют проблемы, которые являются o ( n ) в нечистой системе, которые являются ω ( N log n ) в чистой системе.

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

Проблема, построенная с помощью пипергенга, требует ω ( N log n ), специально построена для достижения этого результата, и не обязательно является представителем практических, реальных проблем. Существует несколько ограничений на проблему, которые немного неожиданно, но необходимо для доказательства для работы; В частности, проблема требует, чтобы результаты вычисляются в режиме онлайн, не имея возможности получить доступ к будущему вводу, и что вход состоит из последовательности атомов из неограниченного набора возможных атомов, а не набор фиксированного размера. И бумага устанавливает только (нижние связанные) результаты для нежамого алгоритма линейного времени работы; Для проблем, которые требуют большего времени эксплуатации, возможно, что дополнительный o (log n ) фактор, видимый в линейной задаче, может быть «поглощен» в процессе дополнительных операций, необходимых для алгоритмов с больше времени работы. Эти разъяснения и открытые вопросы кратко рассмотрены Ben-Amram [1996] .

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

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

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

Ссылки

• Бен-Амрам, Амир и Галиль, ЗВИ 1992. «Об указателях против адресов» журнал ACM, 39 (3), с. 617-648, июль 1992 года
• Ben-Amram, Amir 1996. «Примечания по сравнению пиппенга чистыми и нечистые Lisp» неопубликованной рукописи, Дику, Университет Копенгагена, Дания
• Птица, Ричард, Джонс, Жерание и де-Мар Oege 1997. «Больше спешности, меньшей скорости: ленивый по сравнению с нетерпением racgane Оценка» Журнал функционального программирования 7, 5 стр. 541-547, сентябрь 1997 г.
• Окасаки, Крис 1996. «Чисто функционал Структуры данных " PhD Thesis, Carnegie Mellon Университет
• Окасаки, Крис 1998. « Чисто функциональные структуры данных » Кембриджский университет, Кембридж, Великобритания
• Пиппенгер, Nicholas 1996. «Чистый против нечистого Lisp» Симпозиум ACM на принципах языков программирования, страницы 104-109, январь 1996 г.