Как моделируется сложность алгоритма для функциональных языков?

38

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

Тогда должно ли быть альтернативное моделирование сложности алгоритма для функциональных языков?

wsaleem
источник
3
Это может быть то, что вы ищете.
Аристу
1
На ваш вопрос можно ответить здесь: cs.stackexchange.com/q/18262/755 . В частности, временная сложность в чисто функциональном языке отличается от временной сложности в императивном языке не более чем на коэффициент для некоторых подходящих предположений о возможностях обоих языков. O(logn)
DW
3
GHC Haskell поддерживает изменяемые массивы и деревья и тому подобное, позволяя вам осуществлять доступ к массивам и изменять узлы дерева за O (1) времени, используя «потоки состояний» ( STмонады).
Таннер Светт
1
@BobJarvis Зависит. Является ли список абстрактным типом данных для вас, или вы специально рассматриваете связанные списки?
Рафаэль
1
Какую цель вы ищете для моделирования алгоритмической сложности? Вы ищете что-то математически чистое или практичное? Для практической ценности следует обратить внимание на такие вещи, как то, доступно ли вам запоминание или нет, но с точки зрения математического пурита возможности реализации не должны иметь значения.
Cort Ammon - Восстановить Монику

Ответы:

34

Если вы предполагаете, что калькуляция является хорошей моделью функциональных языков программирования, то можно подумать: λ- калькуляция имеет, казалось бы, простое понятие сложности времени: просто посчитайте количество шагов β- редукции ( λ x . M ) N M [ N / x ] .λλβ(λx.M)NM[N/x]

Но это хорошая мера сложности?

Чтобы ответить на этот вопрос, мы должны уточнить, что мы подразумеваем под мерой сложности в первую очередь. Один хороший ответ дает тезис Слота и Ван Эмде Боаса : любая хорошая мера сложности должна иметь полиномиальное отношение к каноническому понятию сложности времени, определенному с помощью машин Тьюринга. Другими словами, должна быть «разумная» кодировка Из терминов λ- исчисления в машины Тьюринга, например, для некоторого полинома p , это случай, когда для каждого члена M размера | М | : M сводится к значению в p ( | M |tr(.)λpM|M|Mβ- уменьшение шагов точно, когда t r ( M ) уменьшается до значения в p ( | t r ( M ) | ) шагов машины Тьюринга.p(|M|) βtr(M)p(|tr(M)|)

Долгое время было неясно, может ли это быть достигнуто в λ-исчислении. Основными проблемами являются следующие.

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

Статья Б. Аккаттоли и У. Дала Лаго « Бета-редукция является инвариантной, действительно » проясняет проблему, показывая «разумное» кодирование, которое сохраняет класс сложности P полиномиальных функций времени, предполагая, что крайние слева-крайние сокращения вызовов по имени , Ключевым моментом является то, что экспоненциальный взрыв может произойти только по «неинтересным» причинам, которые могут быть побеждены надлежащим обменом. Другими словами, класс P один и тот же, независимо от того, определяете ли вы его, считая шаги машины Тьюринга или (крайний левый-крайний) сокращения.β

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

Мартин Бергер
источник
23

Сложность алгоритма не зависит от деталей более низкого уровня.

Нет, не совсем. Мы всегда считаем элементарные операции в некоторой модели машины:

  • Ступени для машин Тьюринга.
  • Основные операции с оперативной памятью.

ΩΘOΘ

Поэтому на ваш вопрос есть простой ответ: исправить модель машины и какие «операции» рассчитывать. Это даст вам в меру. Если вы хотите, чтобы результаты были сопоставимы с нефункциональными алгоритмами, вам лучше всего скомпилировать свои программы в ОЗУ (для анализа алгоритмов) или TM (для теории сложности) и проанализировать результат. Для облегчения этого процесса могут существовать теоремы о переносе.

Рафаэль
источник
Согласовано. Примечание стороны: люди действительно часто делают много ошибок , о том, что операции «константа». Например, предполагая, что + + - O(1)это когда это действительно такO(log ab)
Пол Дрейпер,
3
@PaulDraper Это другое предположение, не обязательно ошибка. Мы можем смоделировать то, что хотим - вопрос в том, отвечает ли он на интересные вопросы. Смотрите также здесь .
Рафаэль
это звучит очень похоже на «избавиться от модели машины»
Пол Дрейпер
@PaulDraper Зависит от того, какие чувства вы относите к слову «машина». Смотрите также это обсуждение . FWIW, модель оперативной памяти - возможно, стандартная модель в алгоритме анализа! - это полезно, иначе она не была бы использована на протяжении десятилетий. Все знакомые границы для сортировки, поиска и т. Д. Основаны на этой модели. Это имеет смысл, потому что он моделирует реальные компьютеры до тех пор, пока числа вписываются в регистры.
Рафаэль
1

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

gardenhead
источник
<Discussion on what is a machine model deleted.> Let us continue this discussion in chat.
Raphael