haskell - 递归列表 zipWith 的空间泄漏

Question

我的空间泄漏发生在我的一个个人项目中。但我不希望有人在我的项目中解决它。我想了解它。

我通过制作这个算法重现了我的空间泄漏:

u 是由以下定义的序列:

u(0) = 1

u(1) = 2

u(2) = 1

u(4) = 3

…

u(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 能够解决 fibonnacci ，但不适用于我编造的序列？
我做错了什么？
你将如何在 Haskell 中实现这个算法？

Answer 1

嗯，这是堆栈溢出，但你也有空间泄漏，这更容易用几句话来解释。

当您执行索引 u !! n , u好像

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

然后你提取最后一个 <go thunk> ，索引为 n 的那个在列表中 u .此时每 <go thunk>引用了 u 的早期元素，所以(几乎)整个 u必须保留在内存中(实际上不需要前五个左右的元素)。

堆栈溢出是为了评估 u 的第 9999999 个元素，您首先必须评估第 9999994 个元素，并且为了评估您首先必须评估第 9999989 个元素，等等。为了完成对第 9999999 个元素的评估，第 9999994 个元素进入堆栈，并且您的堆栈溢出(我想这也是一种空间泄漏)。

这两个问题都可以通过强制列表 u 的元素来解决。无论是在构建它还是在遍历它时。既然您说您不希望有人解决空间泄漏问题，我将把这部分留作练习，尽管有一种特别巧妙且可能不明显的方法来做到这一点。

编辑添加:我想到的光滑但可能过于聪明的修复只是将最后一行更改为

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

可能理解它是如何工作的本身就是一个足够的练习。

更直接的方法是在 max taldykin 的回答中，或者编写一个自定义索引函数，强制它在丢弃它们之前跳过的元素。