首页 文章

C vs Haskell Collatz猜想速度比较[关闭]

提问于
浏览
12

我的第一个真正的编程经验是Haskell . 为了满足我的临时需求,我需要一个易于学习,编码快速且易于维护的工具,我可以说它很好地完成了工作 .

然而,在某一点上,我的任务规模变得更大,我认为C可能更适合他们,而且确实如此 . 也许我在[任何]编程方面不够熟练,但我无法使Haskell像C一样快速高效,即使我听说适当的Haskell能够具有类似的性能 .

最近,我想我会再次尝试一些Haskell,虽然它对于通用的简单(在计算方面)任务仍然很好,但它似乎无法将C的速度与Collatz猜想之类的问题相匹配 . 我读过了:

Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell

GHC Optimization: Collatz conjecture

collatz-list implementation using haskell

但从我看到的,简单的优化方法,包括:

  • 选择"tighter"类型,如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("%d\n", 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代码编写速度快,易于维护,仅用于计算简单的任务,并且在性能至关重要时会丢失此特性吗?

1 回答

  • 20

    你的Haskell代码的一个大问题是你要分割,而你在C版本中没有 .

    是的,您编写了 n % 2n / 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 vs C 's 0.32s on my box for a limit of 1000000). If you compile using the LLVM backend, you don' t甚至需要用按位操作替换 % 2/ 2 ,LLVM为您做到这一点(但它会为您的原始Haskell源生成较慢的代码,0.4s,令人惊讶的是 - 通常,LLVM并不比循环优化中的本机代码生成器差 .

    使用32位GHC,您将无法获得可比较的速度,因为有了这些,64位整数的原始操作是通过C调用实现的 - 对32位系统上的快速64位操作的需求从来没有 . 他们被实施为初学者;很少有人在GHC工作,他们花时间做其他更重要的事情 .

    TL; DR:Haskell代码编写速度快,维护简单,仅用于计算简单的任务,并且在性能至关重要时会失去这一特性吗?

    那要看 . 你必须知道GHC从什么类型的输入生成什么类型的代码,你必须避免一些性能陷阱 . 通过一些练习,对于这样的任务来说,很容易说gcc -O3的速度是2倍 .

相关问题