0

考虑这个简单的“基准”：

n :: Int
n = 1000
main = do
    print $ length [(a,b,c) | a<-[1..n],b<-[1..n],c<-[1..n],a^2+b^2==c^2]

和适当的C版本：

#include <stdio.h>

int main(void)
{
    int a,b,c, N=1000;
    int cnt = 0;

    for (a=1;a<=N;a++)
        for (b=1;b<=N;b++)
            for (c=1;c<=N;c++)
                if (a*a+b*b==c*c) cnt++;
    printf("%d\n", cnt);
}

汇编：

  • Haskell 版本编译为：ghc -O2 triangle.hs(ghc 7.4.1)
  • C版本编译为：gcc -O2 -o triangle-c triangle.c(gcc 4.6.3)

运行时间：

  • Haskell：4.308s 真实
  • C: 1.145s 实数

即使对于 Haskell 几乎慢 4 倍这样简单且可优化的程序，它的行为是否正常？Haskell 在哪里浪费时间？

4

3 回答 3

8

Haskell 版本浪费时间分配盒装整数和元组。

您可以通过例如运行带有 flags 的 haskell 程序来验证这一点+RTS -s。对我来说，输出的统计数据包括：

  80,371,600 bytes allocated in the heap

C 版本的直接编码更快，因为编译器可以使用未装箱的整数并跳过分配元组：

n :: Int
n = 1000
main = do
  print $ f n

f :: Int -> Int
f max = go 0 1 1 1
  where go cnt a b c
          | a > max = cnt
          | b > max = go cnt (a+1) 1 1
          | c > max = go cnt a (b+1) 1
          | a^2+b^2==c^2 = go (cnt+1) a b (c+1)
          | otherwise = go cnt a b (c+1)

看：

  51,728 bytes allocated in the heap

此版本的运行时间1.920s与1.212sC 版本相比。

于 2012-09-05T11:03:44.130 回答
4

我不知道你的“板凳”有多大意义。我同意列表理解语法“很好”使用，但如果你想比较两种语言的性能，你应该在更公平的测试中比较它们。我的意思是，创建一个可能包含很多元素的列表，然后计算它的长度与在（三重循环）中增加一个计数器完全不同。

所以也许haskell有一些很好的优化可以检测你在做什么并且从不创建列表，但我不会依赖它来编写代码，你可能也不应该这样做。

如果您需要快速计数，我认为您不会这样编写程序，那么为什么要为这个板凳编写代码呢？

于 2012-09-05T10:20:06.123 回答
3

Haskell可以很好地优化——但是你需要适当的技术，并且你需要知道你在做什么。

这种列表理解语法很优雅，但也很浪费。您应该阅读RealWorldHaskell 的相应章节，以了解有关您的分析机会的更多信息。Int在这种确切的情况下，您毫无理由地创建了很多列表脊椎和装箱。看这里：基准的类型配置文件

你绝对应该为此做点什么。编辑：@opqdonut 刚刚发布了一个关于如何加快速度的好答案。

请记住下次在比较任何基准之前分析您的应用程序。Haskell 使编写惯用代码变得容易，但它也隐藏了很多复杂性。

于 2012-09-05T11:04:02.663 回答