6

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

 3 years ago
source link: https://blog.lilydjwg.me/2012/10/24/project-euler-problem-14-haskell-and-erlang-answers.36085.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

本文来自依云's Blog，转载请注明。

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

3xp1.hs
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 版：

e3xp1.erl
-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');
}

发送到 Kindle


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK