使用递归列表zipWith进行空间泄漏

Question

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

我通过编写这个算法来重现我的空间泄漏:

u是由以下定义的序列:

• 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能够解决fibonnacci问题,但不能解决我的编组序列？我做错了什么？你如何在Haskell中实现这个算法？

Answer 1

好吧,这是一个堆栈溢出,但你也有一个空间泄漏,这很容易用几句话来解释.

当您执行索引时u !! n,u看起来像

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

并提取列表<go thunk>中索引处的最后一个.在这一点上,每个都有对早期元素的引用,因此(几乎)必须保留在内存中(实际上不需要前五个元素).nu<go thunk>uu

堆栈溢出是为了评估u的9999999th元素,首先必须评估9999994th元素,并且为了评估您首先必须评估9999989th元素,等等.在评估之后做什么,比如评估9999994th元素为了完成评估9999999th元素进入堆栈,并且你的堆栈溢出(我想这也是一种空间泄漏).

这两个问题都可以通过在u构造列表时或在遍历列表时强制列表元素来解决.既然你说你不希望有人解决空间泄漏问题,我会将这部分留作练习,尽管有一种特别光滑且可能非常明显的方法.

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

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

可能理解它是如何工作的本身就是一个充分的练习.

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