4

我在这个页面上工作

http://www.haskell.org/haskellwiki/99_questions/Solutions/4

我理解每个函数的含义，并且很高兴看到一个函数可以以多种方式定义。但是，我刚开始想知道哪个更快。我认为它会是它所说的length那个Prelude。

length [] = 0
length (x:xs) = 1 + length xs

但是，这比length.Prelude

在我的计算机length上，Prelude返回长度为[1..10^7]0.37 秒。然而，如上定义的函数需要 15.26 秒。

我定义了自己的长度函数，它使用了一个累加器。只用了 8.99 秒。

我想知道为什么会出现这些大差异？

4

3 回答 3

7

当您说“ lengthin Preludereturn ... in 0.37 sec”时，您指的是哪个编译器？如果您使用 GHC，您可以看到，例如，here实际实现与简单的不同

length [] = 0
length (x:xs) = 1 + length xs

即，它是：

length l = len l 0#
  where
    len :: [a] -> Int# -> Int
    len []     a# = I# a#
    len (_:xs) a# = len xs (a# +# 1#)

这段代码使用了一个累加器，并且通过使用未装箱的整数来避免巨大的未计算的thunk 的问题，即这个版本是高度优化的。

为了说明“简单”版本的问题，请考虑如何length [1, 2, 3]评估：

length [1, 2, 3]
  => 1 + length [2, 3]
  => 1 + (1 + length [3])
  => 1 + (1 + (1 + length []))
  => 1 + (1 + (1 + 0))

直到真正需要它的结果时才会计算总和，因此您会看到，当输入是一个巨大的列表时，您将首先在内存中创建一个巨大的总和，然后仅在真正需要其结果时才对其进行评估。

相比之下，优化版本的评估如下：

length [1, 2, 3]
  => len [1, 2, 3] 0#
  => len [2, 3] (1#)
  => len [3] (2#)
  => len [] (3#)
  => 3

即，“+1”立即完成。

于 2013-04-25T02:05:00.710 回答
4

您应该注意的两个步骤是：

  • 你是在运行编译的代码而不是在 ghci 中吗？
  • 您是否使用 -O2 标志

以下基准是在标准中完成的，并使用以下功能以及前奏曲的长度，这需要MagicHashpragma 和 importing GHC.Base：

myLength1 :: [a] -> Int                                                          
myLength1 [] = 0                                                                 
myLength1 (x:xs) = 1 + myLength1 xs                                              

myLength2 :: [a] -> Int                                                          
myLength2 lst = len lst 0                                                        
  where                                                                          
    len :: [a] -> Int -> Int                                                     
    len [] n = n                                                                 
    len (_:xs) n = len xs (n+1)                                                  

myLength3                  :: [a] -> Int                                         
myLength3 l                =  len l 0#                                           
  where                                                                          
    len :: [a] -> Int# -> Int                                                    
    len []     a# = I# a#                                                        
    len (_:xs) a# = len xs (a# +# 1#)

基准测试的结果，在最后找到完整的，没有使用 teh-O2标志是：

              mean
length    :   5.4818 ms
myLength1 : 202.1552 ms
myLength2 : 236.3042 ms
myLength3 :   5.3630 ms

现在让我们-02在编译时使用标志

              mean
length    :   5.2597 ms
myLength1 :   12.882 ms
myLength2 :   5.2026 ms
myLength3 :   5.6393 ms,

请注意，长度myLength3没有变化，但其余两个变化很大。天真的方法在 3 个不同的因子之内，myLength2现在通过模拟前奏长度，但使用拆箱，现在可以与内置长度相媲美。

另外值得注意的是，将 Int 拆箱的 myLength3 变化不大，并且在 ghci 中的性能可能比 myLength 1 或 2 好得多。

完整代码在：https ://gist.github.com/Davorak/5457105

编辑：一些不适合评论的进一步信息：

带有字母的 ghc 标志-O2表示“应用所有非危险优化，即使这意味着编译时间显着延长。”如果这涉及一些数据类型的拆箱，我不会感到惊讶。您可以在此处找到不同标志的进一步解释。这里是带有更多ghc 7.6.2 标志列表的链接，但是解释可能简短而神秘。

我对拆箱和原始操作并不十分熟悉，它们的后果是GHC 手册的第三个链接，其中涵盖了拆箱类型。您偶尔会在优化教程中发现它们。大多数情况下，除非您真的需要每一克的性能，否则您不应该打扰它们，因为正如我们上面所说，它们通常只会在使用其他优化标志后产生持续的差异。

于 2013-04-25T02:34:23.137 回答
0

前奏只是语义规范；它不限制实施。来自http://www.haskell.org/onlinereport/haskell2010/haskellch9.html#x16-1710009：

它构成了 Prelude 的规范。许多定义是为了清晰而不是效率而编写的，并且不需要按照此处所示实施规范。

在 GHC 的情况下，实际length功能是高度优化的。

于 2013-04-25T02:04:00.587 回答