将所有数字从Haskell中的1到10亿加起来

Question

目前我正在赶上Haskell,到目前为止我印象非常深刻.作为一个超级简单的测试,我写了一个程序,计算总和直到十亿.为了避免列表创建,我编写了一个应该是尾递归的函数

summation start upto 
  | upto == 0 = start
  | otherwise = summation (start+upto) (upto-1)

main = print $ summation 0 1000000000

用-O2运行这个我在我的机器上得到大约20秒的运行时间,这让我感到惊讶,因为我认为编译器会更优化.作为比较,我写了一个简单的c ++程序

#include <iostream>

int main(int argc, char *argv[]) {
  long long result = 0;
  int upto = 1000000000;

  for (int i = 0; i < upto; i++) {
    result += i;
  }
  std::cout << result << std::end;
  return 0;
}

使用clang ++进行编译而不进行优化,运行时间为〜3秒.所以我想知道为什么我的Haskell解决方案如此之慢.有人有想法吗？

在OSX上:

clang ++ --version:

Apple LLVM version 7.0.2 (clang-700.1.81)
Target: x86_64-apple-darwin15.2.0
Thread model: posix

ghc --version:

The Glorious Glasgow Haskell Compilation System, version 7.10.3

Answer 1

添加类型签名使我的运行时间从14.35秒减少到0.27.它现在比我的机器上的C++更快.当性能很重要时,不要依赖于类型默认.例如,对于在Web应用程序中对域进行建模,Int并不是优选的,但如果您想要一个紧凑的循环,它们就很棒.

module Main where

summation :: Int -> Int -> Int
summation start upto 
  | upto == 0 = start
  | otherwise = summation (start+upto) (upto-1)

main = print $ summation 0 1000000000


[1 of 1] Compiling Main             ( code/summation.hs, code/summation.o )
Linking bin/build ...
500000000500000000
14.35user 0.06system 0:14.41elapsed 100%CPU (0avgtext+0avgdata 3992maxresident)k
0inputs+0outputs (0major+300minor)pagefaults 0swaps

Linking bin/build ...
500000000500000000
0.27user 0.00system 0:00.28elapsed 98%CPU (0avgtext+0avgdata 3428maxresident)k
0inputs+0outputs (0major+171minor)pagefaults 0swaps

Answer 2

除非您想要查看未优化(非-O2)视图,否则请跳过删除.

让我们来看看评估:

summation start upto 
  | upto == 0 = start
  | otherwise = summation (start+upto) (upto-1)

main = print $ summation 0 1000000000

- >

summation 0 1000000000

- >

summations (0 + 1000000000) 999999999

- >

summation (0 + 1000000000 + 999999999) 999999998

- >

summation (0 + 1000000000 + 999999999 + 999999998) 999999997

编辑:我没有看到你编译过,-O2所以上面没有发生.即使没有任何严格的注释,累加器也可以在大多数情况下使用适当的优化级别.

不好了!您正在将十亿个数字存储在您未评估的大型数据中!TISK!有很多使用累加器和严格的解决方案 - 似乎大多数stackoverflow的答案与这个问题附近的任何东西都足以教你除库函数之外的那些,比如fold{l,r},它们可以帮助你避免编写自己的原始递归函数.既然你可以环顾四周和/或询问这些概念,我会用这个答案来追逐.

如果您真的想以正确的方式执行此操作,那么您将使用列表并了解Haskell编译器可以执行"砍伐森林",这意味着从未实际分配了十亿元素列表:

main = print (sum [0..1000000000])

然后:

% ghc -O2 x.hs
[1 of 1] Compiling Main             ( x.hs, x.o )
Linking x ...
% time ./x
500000000500000000
./x  16.09s user 0.13s system 99% cpu 16.267 total

很酷,但为什么16秒？那么默认情况下,这些值是整数(GHC编译器的GMP整数),并且比机器慢Int.让我们用Int!

% cat x.hs
main = print (sum [0..1000000000] :: Int)
tommd@HalfAndHalf /tmp% ghc -O2 x.hs && time ./x
500000000500000000
./x  0.31s user 0.00s system 99% cpu 0.311 total