10
24
2012
33

欧拉项目第14题,Haskell 和 Erlang 等语言版

看到别人的 Racket 版,心里痒痒,写了个 Haskell 版。只用了尾递归,没用什么高级特性。题目地址。

calc3xp1 :: Int -> Int
calc3xp1 n | even n = n `div` 2
           | otherwise = 3 * n + 1

countlen :: Int -> Int
countlen = countlen_tail 0

countlen_tail :: Int -> Int -> Int
countlen_tail c n | n == 1 = c
                  | otherwise = countlen_tail (c+1) $ calc3xp1 n

findmax :: Int -> Int
findmax = findmax_tail 1 1 1

findmax_tail max maxn n final | n >= final = maxn
                              | otherwise = if new_len > max
                                               then findmax_tail new_len n n' final
                                               else findmax_tail max maxn n' final
                                             where new_len = countlen n
                                                   n' = n + 1

main = print $ findmax 1000000
>>> time ./3xp1
./3xp1  14.92s user 0.02s system 99% cpu 14.955 total

Erlang 版本直接照抄 Haskell 版:

-module(e3xp1).
-export([main/1]).

calc3xp1(N) when N rem 2 == 0 ->
  N div 2;
calc3xp1(N) ->
  3 * N + 1.

countlen(N) -> countlen_tail(0, N).

countlen_tail(C, 1) ->
  C;
countlen_tail(C, N) ->
  countlen_tail(C+1, calc3xp1(N)).

findmax(N) ->
  findmax_tail(1, 1, 1, N).

findmax_tail(_, Maxn, N, Final) when N >= Final ->
  Maxn;
findmax_tail(Max, Maxn, N, Final) ->
  Newlen = countlen(N),
  if Newlen > Max -> findmax_tail(Newlen, N, N+1, Final);
    true -> findmax_tail(Max, Maxn, N+1, Final)
  end.

main(_) ->
  io:format("~B~n", [findmax(1000000)]).

它在六分钟后还没能输出结果……

>>> time escript e3xp1.erl
^C
escript e3xp1.erl  374.55s user 0.94s system 99% cpu 6:15.76 total

Racket 版在同一机器上用时:

>>> time racket 3xp1.racket
racket 3xp1.racket  3.22s user 0.22s system 99% cpu 3.448 total

这是为什么呢?

PS: C 更快,不到半秒就搞定了……

更新:又试了试 Lua 版本的,和 Haskell 版速度相当。但是——LuaJIT 竟然只 2.4s 出结果,因为换了机器,所以实际上它应该比 Racket 版快一倍以上。

再次更新:Erlang 版编译后还是挺快的:

>>> erlc e3xp1.erl
>>> time erl -noshell -s e3xp1 main -s init stop
erl -noshell -s e3xp1 main -s init stop  5.59s user 0.01s system 84% cpu 6.608 total

不过,它什么事都不干启动后立即停止也花了一秒多,比 Java 更厉害:

>>> time erl -noshell -s init stop
erl -noshell -s init stop  0.06s user 0.01s system 6% cpu 1.077 total

2014年12月24日更新:Rust 版也非常快,而且写起来舒服:

fn calc3xpi(n: uint) -> uint {
    if n % 2 == 0 {
        n / 2
    } else {
        3 * n + 1
    }
}

fn countlen(&n: &uint) -> uint {
    let mut c = 0;
    let mut x = n;
    while x != 1 {
        c += 1;
        x = calc3xpi(x);
    }
    c
}

fn findmax(n: uint) -> uint {
    range(1, n).max_by(countlen).unwrap()
}

fn main(){
    let mut stdout = std::io::stdout();
    stdout.write_uint(findmax(1000000));
    stdout.write_char('\n');
}

| Theme: Aeros 2.0 by TheBuckmaker.com