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

Сегодня я узнал, что алгоритм анализа отличается в зависимости от вычислительной модели. Это то, о чем я никогда не думал и не слышал.

Пример, данный мне, который проиллюстрировал это далее, пользователем @chi был:

Например, рассмотрим задачу: дано вернуть . В оперативной памяти это может быть решено в так как доступ к массиву постоянен. Используя ТМ, нам нужно сканировать весь ввод, так что это $(i,x_1 ,…,x_n )$ $x_i$ $O(1)$ $O(n)$

Это заставляет меня задуматься о функциональных языках; Насколько я понимаю, «функциональные языки тесно связаны с лямбда-исчислением» (из комментария Ювала Фильмуса здесь ). Итак, если функциональные языки основаны на лямбда-исчислении, но работают на машинах, основанных на ОЗУ, каков правильный способ анализа сложности алгоритмов, реализованных с использованием чисто функциональных структур данных и языков?

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

«Массивы могут быть заменены картой или списком произвольного доступа, который допускает чисто функциональную реализацию, но время доступа и обновления является логарифмическим».

В этом случае вычислительная модель будет другой, правильно?

complexity-theory algorithm-analysis computability computation-models lambda-calculus Абдул
источник

Я определенно не эксперт по этой теме, но, полагаю, я слышал, что 1) машина, похожая на шутки (с собственной моделью затрат), может моделировать программы ОЗУ с дополнительным фактором

(это легко доказать) и 2) действительно ли этот фактор необходим, остается открытой проблемой. Кроме того, можно утверждать, что назначение стоимости O (1) для доступа к массиву в модели RAM является слишком щедрым. В аппаратном обеспечении доступ к памяти должен проходить через

вентилей, где

- размер физической памяти.

O (\log n)

$O(\log n)$

O (\log n)

$O(\log n)$

n

$n$

Чи

Также имейте в виду, что практически все реальные языки FP имеют массивы в той или иной форме с гарантированным временем доступа

(как в императивных языках). Обычно это решается добавлением их в качестве языкового примитива.

O (1)

$O(1)$

Чи

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

Курт Мюллер

@KurtMueller Обратите внимание, что мы можем получить лямбда-член размера

только после сокращения

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

O (2^{n})

$O(2^n)$

O (n)

$O(n)$

Чи

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

Эрик Липперт

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

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

adrianN
источник

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

Абдул

Да. Ваш разработчик языка должен сказать вам, что на самом деле означают вещи, которые вы можете написать на языке, прежде чем вы сможете проанализировать время выполнения алгоритма.

adrianN

«Вы не можете выполнять анализ алгоритмов на языках программирования в отдельности» - это относилось к языкам FP или к языкам в целом? Если это относится к предыдущему, то как мы можем анализировать алгоритмы в школе таким общим образом, то есть анализировать проблемы Java, C / C ++, Python? Потому что они все очень похожи? Или это потому, что базовые структуры данных и ADT одинаковы и реализованы одинаково? Или, наконец, это потому, что эти курсы просто ради образования и не обязательно должны быть строго точными?

Абдул

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

adrianN

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

Ответы: