C vs Haskell Collatz猜想速度比较

2018-06-28 19:10:05

我的第一个真正的编程经验是Haskell。为了满足我的特殊需求，我需要一个易于学习，易于编码和易于维护的工具，我可以说它很好地完成了这项工作。

然而，我的任务规模一度变得更大，我认为C可能更适合他们，而且确实如此。也许我在编程方面没有足够的技巧，但是我没有把Haskell作为C的速度效率，尽管我听说Haskell具有相似的性能。

最近，我想我会再次尝试一些Haskell，虽然对于通用简单（在计算方面）的任务来说它仍然很棒，但它似乎无法将C的速度与Collatz猜想等问题相匹配。我读过了：

与Project Euler进行速度比较：C vs Python vs Erlang vs Haskell

GHC优化：Collatz猜想

使用haskell实现collatz-list实现

但从我所看到的简单的优化方法，包括：

选择“更紧密”的类型，如Int64而不是Integer

开启GHC优化

使用简单的优化技术，如避免不必要的计算或更简单的功能

仍然不会使Haskell代码甚至接近几乎完全相同（就方法论而言）C代码的真正大数字。唯一能够使它的性能与C相当（用于大规模问题）的唯一方法是使用优化方法，使代码成为漫长而可怕的monadic地狱，这违背了Haskell（和我）非常重视的原则。

这是C版本：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int32_t col(int64_t n);

int main(int argc, char **argv)
{
    int64_t n = atoi(argv[1]), i;
    int32_t s, max;

    for(i = 2, max = 0; i <= n; ++i)
    {
        s = col(i);
        if(s > max) max = s;
    }
    printf("%dn", max);

    return 0;
}

int32_t col(int64_t n)
{
    int32_t s;

    for(s = 0; ; ++s)
    {
        if(n == 1) break;
        n = n % 2 ? 3 * n + 1 : n / 2;
    }

    return s;
}

和Haskell版本：

module Main where

import System.Environment (getArgs)
import Data.Int (Int32, Int64)

main :: IO ()
main = do
    arg <- getArgs
    print $ maxCol 0 (read (head arg) :: Int64)

col :: Int64 -> Int32
col x = col' x 0

col' :: Int64 -> Int32 -> Int32
col' 1 n            = n
col' x n
    | rem x 2 == 0  = col' (quot x 2) (n + 1)
    | otherwise     = col' (3 * x + 1) (n + 1)

maxCol :: Int32 -> Int64 -> Int32
maxCol maxS 2   = maxS
maxCol maxS n
    | s > maxS  = maxCol s (n - 1)
    | otherwise = maxCol maxS (n - 1)
    where s = col n

TL; DR：Haskell代码是否易于编写，并且易于维护，仅用于计算简单的任务，并且在性能至关重要时会丢失此特性？

你的Haskell代码的一个大问题是你正在分割，而你不在C版本中。

是的，你写了n % 2和n / 2 ，但编译器用shift和bitwise替换了它。遗憾的是，GHC还没有被教导要这么做。

如果你自己做替换

module Main where

import System.Environment (getArgs)
import Data.Int (Int32, Int64)
import Data.Bits

main :: IO ()
main = do
    arg <- getArgs
    print $ maxCol 0 (read (head arg) :: Int64)

col :: Int64 -> Int32
col x = col' x 0

col' :: Int64 -> Int32 -> Int32
col' 1 n            = n
col' x n
    | x .&. 1 == 0  = col' (x `shiftR` 1) (n + 1)
    | otherwise     = col' (3 * x + 1) (n + 1)

maxCol :: Int32 -> Int64 -> Int32
maxCol maxS 2   = maxS
maxCol maxS n
    | s > maxS  = maxCol s (n - 1)
    | otherwise = maxCol maxS (n - 1)
    where s = col n

与64位GHC你可以得到相同的速度（0.35s与C的0.32s在我的盒子上限制为1000000）。如果你使用LLVM后端进行编译，甚至不需要用位运算替换% 2和/ 2 ，LLVM可以为你做这件事（但它会为你的原始Haskell源代码生成较慢的代码，0.4s） - 通常，LLVM在循环优化时并不比原生代码生成器差）。

使用32位GHC时，您无法获得可比较的速度，因为在这些情况下，64位整数的基本操作是通过C调用实现的 - 在32位系统上，对于快速的64位操作从来没有足够的需求他们被实施为首饰; 为GHC工作的人很少花时间去做其他更重要的事情。

TL; DR：Haskell代码是否易于编写，并且易于维护，仅用于计算简单的任务，并且在性能至关重要时会丢失此特性？

那要看。您必须了解GHC根据什么类型的输入生成的代码类型，并且您必须避免一些性能陷阱。通过一些练习，在这种任务中获得2倍于gcc -O3的速度是相当容易的。

链接地址: http://www.djcxy.com/p/80423.html

上一篇: C vs Haskell Collatz conjecture speed comparison

下一篇: Project Euler #1 using Haskell

C vs Haskell Collat​​z猜想速度比较

C vs Haskell Collatz猜想速度比较