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

Рассмотрим следующие две функции кумулятивной суммы (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]

cumulative-sum haskell complexity-theory ghci
person VH-NZZ    schedule 02.07.2014    source источник
comment
Я подозреваю, что вы ошиблись в своих измерениях - я не понимаю, как cumsum' могла иметь линейную сложность.   -  person GS - Apologise to Monica    schedule 03.07.2014
comment
FWIW, scanl (+) 0   -  person luqui    schedule 03.07.2014
comment
Я просто измерил его сам, и он определенно квадратичный. Вы сделали что-то слишком ленивое, чтобы не распечатать результат?   -  person GS - Apologise to Monica    schedule 03.07.2014
comment
@GaneshSittampalam Я измерил это с помощью last $ cumsum' [1..n]   -  person VH-NZZ    schedule 03.07.2014
comment
Это действительно слишком лениво. Он не рассчитывает промежуточные суммы. Я использовал max, а не last.   -  person GS - Apologise to Monica    schedule 03.07.2014
comment
\x -> [take k x | k <- [1..length x]] равно tail . inits, за исключением того, что последний не вычисляет длину и не начинает заново для создания каждого подсписка. Ваша функция map sum . tail . inits   -  person user2407038    schedule 03.07.2014
comment
@GaneshSittampalam Большое спасибо, я пробовал с maximum и, действительно, теперь наблюдаю квадратичную сложность. В некотором смысле я рад, потому что это заставило меня опасаться измерения, ура! Тогда возникает следующий вопрос: как в last реализована лень?   -  person VH-NZZ    schedule 03.07.2014
comment
Ничего общего с самим last, а с Хаскеллом вообще лень. last проверяет только структуру списка, поскольку это все, что ему нужно сделать, поэтому отдельные элементы не будут принудительно выполнены, и все, кроме последнего элемента, будут просто выброшены. Затем возвращаемое значение (т.е. последний элемент) принудительно распечатывается.   -  person GS - Apologise to Monica    schedule 03.07.2014
comment
@GaneshSittampalam Хорошо, я могу (вроде) смириться с тем фактом, что лень подразумевает, что пока не все элементы вытеснены (хотя все они еще нужно вычислить). Не могли бы вы обернуть свой комментарий относительно лени last в измерении времени коротким ответом, который я могу принять? Это может помочь другим, спасибо   -  person VH-NZZ    schedule 03.07.2014
comment
@luqui Или просто scanl1 (+).   -  person Ørjan Johansen    schedule 03.07.2014
comment
@okiharaherbst: на самом деле их все еще не нужно вычислять, поскольку во втором определении вычисление элемента списка не зависит от вычисления любого другого элемента списка. Таким образом, haskell будет оценивать только sum $ take (length x) x   -  person genisage    schedule 03.07.2014
comment
@genisage Да, я то и дело забываю о лени в Haskell. Так что мне следует быть осторожнее с измерениями времени.   -  person VH-NZZ    schedule 03.07.2014

Ответы (1)


arrow_upward
9
arrow_downward

Это ошибка измерения из-за лени.

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

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

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

Поэтому, когда last применяется к результату cumsum', он рекурсивно проверяет понимание списка, но достаточно только для отслеживания последней записи. Он не принудительно вводит какие-либо записи, но возвращает последнюю.

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

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

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

person GS - Apologise to Monica    schedule 02.07.2014