Утечка пространства с рекурсивным списком zipWith

Question

Моя космическая утечка происходит в одном из моих личных проектов. Но я не хочу, чтобы кто-то решал это в моем проекте. Я хочу это понять.

Я воспроизвел свою утечку пространства, составив этот алгоритм:

u - последовательность, определяемая как:

• и (0) = 1
• и (1) = 2
• и (2) = 1
• и (4) = 3
• ...
• и (19) = 11

после этого определяется u: u(n) = u(n-5) + u(n-10) - u(n-15)

Легко реализовать в haskell, верно?

import System.Environment (getArgs)

u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11]
        ++ zipWith3 go u' u'' u'''
    where u' = drop 15 u
          u'' = drop 10 u
          u''' = drop 5 u
          go a b c = a + b - c

main = do
    args <- getArgs
    let n = read $ args !! 0
    putStrLn $ show $ u !! n

К сожалению, это пространство утечки:

$ time ./algo 9999999
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
1.17user 0.19system 0:01.37elapsed 100%CPU (0avgtext+0avgdata 865124maxresident)k
0inputs+0outputs (0major+215695minor)pagefaults 0swaps

Похоже, что haskell кэширует весь список, где, как я хочу, кэшируются только 20 последних элементов.

Например, вот моя реализация в C:

#include <stdint.h>
#include <stdio.h>

int main(int argc, char **argv)
{
    size_t cursor;
    int64_t buffer[20] = {1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11};
    int n = atoi(argv[1]);

    for (cursor = 20; cursor <= n; cursor++) {
        buffer[cursor%20] = buffer[(cursor+20-5)%20] + buffer[(cursor+20-10)%20] - buffer[(cursor+20-15)%20];
    }

    printf("%d\n", buffer[n%20]);
    return 0;

}

$ ./a.out 9999999
5000001

Моя реализация C использует O(n) время и O(1) пространство. Но похоже, что моя реализация на haskell использует пространство O(n).

Почему Хаскелл может понять это по фибоннакам, а не по моей выдуманной последовательности? Что я сделал не так? Как бы вы реализовали этот алгоритм в Haskell?

Answer 1

Хорошо, это переполнение стека, но у вас также есть утечка пространства, которую легче объяснить несколькими словами.

Когда вы выполняете индексацию u !! n, u похоже

1 : 2 : 1 : ... : 11 : <go thunk> : ... : <go thunk> : <zipWith3 thunk>

и вы извлекаете последний <go thunk>тот, что в индексе n в списке u, На данный момент каждый <go thunk> имеет ссылки на более ранние элементы uтак (почти) u должен быть сохранен в памяти (первые пять или около того элементов фактически не нужны).

Переполнение стека состоит в том, что для оценки 9999999-го элемента u сначала необходимо оценить 9999994-й элемент, а для оценки - сначала 9999989-й элемент и т. Д. Что делать после, скажем, оценки 9999994-й элемент для того, чтобы завершить оценку 9999999-го элемента, попадает в стек, и возникает переполнение вашего стека (что также является своего рода утечкой пространства, я полагаю).

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

---

Отредактировано, чтобы добавить: гладкое, но, возможно, слишком умное исправление, которое я имел в виду, состояло в том, чтобы просто изменить последнюю строку на

    putStrLn $ show $ foldr ((:) $!) [] u !! n

Вероятно, понимание того, как это работает, само по себе является достаточным упражнением.

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

Answer 2

Вот код, который следует за ответом Рейда Бартона:

{-# LANGUAGE BangPatterns #-}
import System.Environment (getArgs)

u :: [Int]
u = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 1, 10, 1, 11]
        ++ go u' u'' u'''
    where u' = drop 15 u
          u'' = drop 10 u
          u''' = drop 5 u
          go ((!a):as) ((!b):bs) ((!c):cs)
            = a + b - c
            : go as bs cs

Он использует расширение BangPatterns для принудительной оценки thunks. (Я также добавил аннотацию типа для использования Intс вместо Integerс который немного быстрее.)

Вы можете видеть, что он работает в постоянном пространстве (1M in use является важной частью вывода):

$ ./xx 99999999 +RTS -t
50000001
<<ghc: 8000065016 bytes, 15319 GCs, 36596/44312 avg/max bytes residency (2 samples), 1M in use, 0.00 INIT (0.00 elapsed), 2.82 MUT (2.78 elapsed), 0.01 GC (0.06 elapsed) :ghc>>