我的空间泄漏发生在我的个人项目中。但我不希望有人在我的项目中解决它。我想要理解它。
我通过编写以下算法来复现我的空间泄漏:
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 能够在 斐波那契数列 中找到答案,但在我的自定义序列中却不能?我做错了什么?你会如何在 Haskell 中实现这个算法?
-O2
编译了吗?另外,由于它是 GHC 喜欢保留的顶级值,尝试在main
中使用where
定义它。 - bheklilr-O2
,在顶层/main函数闭包中,在这四种情况下,它都不会改变任何东西:(。 - Antoine Catton