Существует ли для каждого императивного алгоритма чистый функциональный эквивалент в пределах одного и того же класса сложности пространства и времени?

Question

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

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

Answer 1

Короткий ответ - да. Функциональные структуры данных менее эффективны:

• Map и Set являются деревьями и полагаются на сравнение, а не на хеш-код. Отсюда log(n)
• List предоставляет вам тот же API, что и изменяемый массив, но это связанный список. Следовательно log(n) для произвольного доступа.

Тем не менее, это известный компромисс между неизменяемостью - дешевле «заменить» 1 элемент в неизменяемом связанном списке, так как вам нужно обновить только 1 элемент и повторно использовать оставшуюся часть, а если вы хотите неизменный массив, вам придется полностью скопировать его.

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

Поскольку вы отметили его, F# является хорошим языком для этого, поскольку он имеет хорошую поддержку как для FP, так и для ООП.