4

如果我在 GHCi 中加载以下列表，则该列表的计算速度很慢，直到程序最终在计算 3524578（列表中的第 33 项）之后关闭。

fibonacci :: (Integral a) => [a]
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

如果我删除第一行并加载以下内容，则该列表的计算速度非常快，并且 GHCi 不会关闭。

fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

为什么多态列表比Integer列表慢很多？为什么 GHCi 关闭？

4

2 回答 2

3

在您的第一个版本中，虽然它看起来像一个值，但实际上您编写了一个函数（一个比 Haskell 本身级别更低的函数）。

要理解这一点，请考虑一下您的定义可能出现的以下代码：

main = println (fibonacci !! 17 :: Int, fibonacci !! 19 :: Integer)

当然，17 和 19 完全是任意的。关键是第一个元组元素需要将斐波那契计算为 的列表Int，而第二个假设它是 的列表Integers。正如您可能知道的那样，Haskell 中没有这样的列表是半途而废Int的Integer- 列表要么是要么[Int]（[Integer]或完全不同的东西）。

因为是这样，我们可以在纯粹的逻辑基础上得出结论，无需深入了解 Haskell 的运行时系统，这fibonacci既不是其他东西的列表，也不是其他东西Int的列表，Integer也不是其他东西的列表——它只是构建这样一个列表的秘诀根据要求。

话虽如此，只要您执行以下操作：

take 10 fibonacci

它应该没那么重要（斐波那契只计算一次最多10个元素）。

但是当你说

map (fibonacci !!) [1..10]

斐波那契很有可能会为每个索引重新计算。显然，指数越高，所需的时间就越长。

于 2013-10-01T14:41:15.330 回答
1

这看起来很可疑，所以我做了一些调查。首先我做了两个模块：

-- fib0.hs
fibonacci :: (Integral a) => [a]
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)
main = print $ take 10000 $ fibonacci

-- fib1.hs
main = print $ take 10000 $ fibonacci
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)

然后编译如下：（ghc -O2 -prof -auto-all fib0.hs & ghc -O2 -prof -auto-all fib1.hs注：&适用于Windows，*nix用于;分隔一行中的多个命令）。并用fib0 +RTS -p & fib1 +RTS -p. 这将同时运行 fibs，并且标志+RTS -p会生成一个文件名 fib0/1.prof，其中包含有关您的程序的运行时信息。这样做，我看到他们都花费了完全相同的时间！（准确地说是 0.70 秒 - 你的机器上可能需要更长时间，如果你不能忍受等待那么久，那么减少 10000 个元素）。

你会注意到我用-O2. 这会将优化设置为“级别”2。共有三个级别 - 0、1 和 2。GHCi 默认使用O0. 所以然后我尝试ghc -O0 -prof -auto-all fib0.hs & ghc -O0 -prof -auto-all fib1.hs了（ghc 将默认为-O1，因此您必须手动设置级别 0）。难道你不知道吗，当我运行它们时，fib0 崩溃并出现内存不足异常，并且 fib0 完成得很好（虽然非常缓慢。我不得不减少take 10000到take 100- 但这显然是意料之中的）。

这将是一种正常的行为。优化消除了糟糕的编程错误——比如在使用单一类型有益时手动强制执行多态性——除非你必须这样做，否则不要这样做！

如果你想了解更多，可以试试ghc -O0 -f-ext-core fib0.hs & ghc -O0 -f-ext-core fib1.hs。这将为两个程序生成“核心”文件。核心是开始制作目标文件之前 GHC 编译的最后一个阶段。它生成纯文本 .hcr 文件。这些可能很难阅读，所以让我为您强调一些要点。

fib0.hcr 包含以下内容：

...
base:GHCziNum.fromInteger @ ac zddNumazzzz
...

基本上，您调用fromInteger序列中的每个数字，从 0 和 1 开始。为什么要这样做？您已经告诉它，“斐波那契的类型必须是任何数字类型”。它将 0 和 1 创建为Integers，然后用于fromInteger创建类型的值Num a => a（这是创建多态文字的唯一方法）。所有这些调用都会fromInteger建立非常昂贵的 thunk - 所以你会出现内存不足异常。

看看 fib1.hcr。它不包含任何地方fromInteger。让 GHC 来推断斐波那契的类型让它只使用Integer，这意味着没有 thunk。

为什么优化会消除这个问题？GHC 注意到您只使用斐波那契来打印数字。你不需要这种多态性。所以它优化了它！请注意，它还执行其他使斐波那契变得更快的事情，例如内联。

于 2013-10-01T22:01:03.367 回答