Блог

Главная - Вопросы по программированию - Сложность двух функций кумулятивной суммы (cumsum) в Haskell

Сложность двух функций кумулятивной суммы (cumsum) в Haskell

#haskell #complexity-theory #ghci #cumulative-sum

#haskell #сложность-теория #ghci #кумулятивная сумма

Вопрос:

Рассмотрим следующие две функции кумулятивной суммы (cumsum):

 cumsum :: Num a => [a] -> [a]
cumsum [] = []
cumsum [x] = [x]
cumsum (x:y:ys) = x : (cumsum $ (x y) : ys)

и

 cumsum' :: Num a => [a] -> [a]
cumsum' x = [sum $ take k x | k <- [1..length x]]

Конечно, я предпочитаю определение cumsum cumsum' и я понимаю, что первое имеет линейную сложность.

Но почему cumsum' также имеет линейную сложность? take сама по себе имеет линейную сложность по длине своего аргумента и k выполняется от 1 до length x . Поэтому я ожидал бы квадратичной сложности для cumsum' .

Более того, константа cumsum' меньше, чем у cumsum . Связано ли это с рекурсивным добавлением последней в список?

ПРИМЕЧАНИЕ: приветствуется любое разумное определение кумулятивной суммы.

РЕДАКТИРОВАТЬ: я измеряю время выполнения с помощью (после включения :set s в GHCi):

 last $ cumsum [1..n]

Комментарии:

1. Я подозреваю, что вы ошибаетесь в своих измерениях — я не вижу, как cumsum' может быть линейная сложность.

2. FWIW, scanl ( ) 0

3. Я только что измерил это сам, и это определенно квадратично. Вы сделали что-то слишком ленивое, чтобы избежать распечатки выходных данных?

4. Это действительно слишком лениво. Он не будет вычислять промежуточные суммы. Я использовал max вместо last .

5. x -> [take k x | k <- [1..length x]] является tail . inits , за исключением того, что последняя не вычисляет длину и не начинает заново создавать каждый подсписок. Ваша функция map sum . tail . inits

Ответ №1:

Это ошибка измерения, вызванная ленью.

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

Определение last выглядит примерно так:

 last [x] = x
last (x:xs) = last xs

Таким образом, когда last применяется к результату cumsum' , он рекурсивно проверяет понимание списка, но только настолько, чтобы отследить последнюю запись. Это не приводит к принудительному вводу ни одной из записей, но возвращает последнюю.

Когда эта последняя запись печатается в ghci или любом другом, выполняется принудительное выполнение, что, как и ожидалось, занимает линейное время. Но другие записи никогда не вычисляются, поэтому мы не видим «ожидаемого» квадратичного поведения.

Использование maximum вместо last демонстрирует, что cumnorm' является квадратичным, тогда как cumnorm является линейным.

[Примечание: это объяснение несколько размыто от руки: на самом деле оценка полностью определяется тем, что необходимо для конечного результата, поэтому even last вычисляется вообще только потому, что необходим его результат. Найдите такие вещи, как «Порядок оценки Haskell» и «Нормальная форма слабой головки», чтобы получить более точное объяснение.]