时间戳

首页 > 解决方案 > 为什么在 Haskell 中 memoized 函数会消耗这么多内存？

haskell - 为什么在 Haskell 中 memoized 函数会消耗这么多内存？

问题描述

我写了一段 Haskell 代码来计算Collat​​z 链的长度。给定一个数 n，如果 n 是偶数，则序列中的下一个数是 n/2；如果 n 是奇数，则为 3*n+1。序列在收敛到 1 时结束。我想从低于某个输入数字的任何数字开始找到最长链的长度。

我尝试使用记忆函数来实现长度计算，因为我预计需要从一些数字开始的链长度。因此，从 726 开始的链的长度将只是 1 + 从 363 开始的链的长度，这已经计算过了。我的代码如下所示。

collatz :: Int -> Int
collatz n
    | even n = n `div` 2
    | otherwise = 3 * n + 1

collatzLength :: Int -> Int
collatzLength = (fmap len [0 ..] !!)
    where len 0 = 0
          len 1 = 1
          len n = 1 + (collatzLength . collatz $ n)

maxLengthBelow :: Int -> Int
maxLengthBelow = foldl1 max . fmap collatzLength . enumFromTo 1

main :: IO()
main = print $ maxLengthBelow 10000

此代码有效，但占用大量内存。在分析它时，main以 10000 的输入运行，len只调用了 21664 次，正如预期的那样，但程序需要 16 秒和 4.5Gb 的内存！是什么占用了所有的内存？我本来希望 memoized 函数能够产生快速、低内存的解决方案。

标签： haskell

解决方案

使 Collat​​z 序列如此有趣的一件事是，有一些小的起始种子会带你一路，在通往 1 的路上进入大气层。特别是，9663 在它崩溃之前一直延伸到 27114424 - 这是一个很长的记忆列表！

而且，就其价值而言，我希望您的记忆列表每个元素使用三个机器字：一个用于 上的I#构造函数Int，一个用于包含的数字，一个用于(:)构造函数。让我们问一下存储 27114424 个元素需要多少空间，然后：

> 27114424 * (64*3) / 1024 {-Kb-} / 1024 {-Mb-} / 1024 {-Gb-}
4.8484368324279785

所以 4.5Gb 听起来差不多，甚至可能有点低。

推荐阅读