10
24
2012
33

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

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

看到别人的 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');
}
Category: 编程 | Tags: Haskell Project Euler Erlang Lua Rust 编程语言 | Read Count: 8630
Avatar_small
Qians 说:
Oct 24, 2012 08:48:22 PM

囧...不用racket的ide...快了差不多一半..

Avatar_small
依云 说:
Oct 24, 2012 09:27:09 PM

不同的机器啊。
racket 还有 ide?叫什么名字呢?

Avatar_small
Qians 说:
Oct 24, 2012 09:56:57 PM

不是.我说我不用drracket用命令行.快了差不多一半..
叫drracket

Avatar_small
依云 说:
Oct 24, 2012 09:58:43 PM

哦~看到了,GTK 的,还有中文翻译呢 ^_^

alsotang 说:
Oct 24, 2012 11:43:10 PM

我写的 Ruby 版本。

alsotang 说:
Oct 24, 2012 11:43:31 PM

https://gist.github.com/3946838

sorry,忘记给地址了。

Avatar_small
依云 说:
Oct 25, 2012 11:16:01 AM

你这个算法跟那个 Racket 的一样吧。

登录 说:
Oct 25, 2012 11:29:46 AM

Erlang怎么可能比得过Java

http://www.quora.com/Erlang/Why-does-Erlangs-init-stop-function-take-so-long

Avatar_small
TBY 说:
Oct 26, 2012 08:55:46 AM

你的Haskell版本编译时没开优化么?开优化然后-fforce-recomp一下应该不会这么慢吧。

我没开优化时:
real 0m17.263s
user 0m17.202s
sys 0m0.037s
-O2时:
real 0m2.699s
user 0m2.693s
sys 0m0.000s
-O2 -fllvm:

real 0m1.584s
user 0m1.580s
sys 0m0.000s

Avatar_small
TBY 说:
Oct 26, 2012 09:07:30 AM

你这算法单线程已经非常快了,而且不需要保存状态。

不过可以稍作修改弄成个并发版本的,切割成每次扫1w个数,然后并发算这100份,最后再合并一下。

Avatar_small
依云 说:
Oct 26, 2012 10:21:54 AM

嗯,忘记了……新的结果是:
./3xp1 2.31s user 0.00s system 99% cpu 2.308 total
和 -fllvm 的:
./3xp1 1.27s user 0.00s system 99% cpu 1.271 total

我是说怎么那么慢呢……

Avatar_small
依云 说:
Oct 26, 2012 10:22:51 AM

不过还是没 LuaJIT 快啊 :-(

Avatar_small
依云 说:
Oct 26, 2012 10:24:22 AM

应该并发4份吧,纯计算,并发那么多有用么?

Avatar_small
TBY 说:
Oct 26, 2012 11:38:37 AM

要是只针对特定的某台计算机,数目定死比较好,割的细的话,可以考虑到其他机子。我以前经验,在c下,粒度不要细于数十毫秒(单线程)的话,核更多都可以提升。

现在7.6版ghc可以运行时直接getNumCapabilities和setNumCapabilities的,也不需要硬设阈值了。

Avatar_small
Jam 说:
Oct 26, 2012 12:42:10 PM

靠,在我的机器上Haskell运行的不知道为啥慢得不行,计算1000还可以计算,计算1000000,开了-O2什么的,根本就等不到结果 随便写个Python版本的,都只要2秒就出结果了

见这里:

http://virtue.is-programmer.com/2012/10/26/project-euler-14-python-pypy.36115.html

Avatar_small
TBY 说:
Oct 26, 2012 03:35:06 PM

你ghci里输入这两句看下结果:
:m +Foreign.Storable
sizeOf (1::Int)
如果结果等于4的话,则可以解释你无法终止的原因。Int的范围在Haskell里没有定义,有的等价于Int32,有的是Int64,如果这个题目用的是Int32,会因为上溢导致程序无法终止,你可以import Data.Int,然后把签名全换成Int64试试看。

Avatar_small
TBY 说:
Oct 26, 2012 03:40:33 PM

其实这程序非要比速度的话,是在比较各编程语言的编译器后端优化能力。能直接使用机器字的肯定都不会差太多。Ruby这类全对象的oop语言估计要哭。

Avatar_small
TBY 说:
Oct 26, 2012 03:50:01 PM

这题还可以再快一些的,因为都是*2 ,*3这种,所以可以把*2改成移位,*3改成一次移位和一次加法操作。

Avatar_small
依云 说:
Oct 26, 2012 04:06:25 PM

那个不是编译器应该做的事么?

Avatar_small
Jam 说:
Oct 26, 2012 04:26:17 PM

的确,sizeOf (1::Int) 返回4。
换成Int64,-O2编译,仍然需要7s,比PyPy还慢

Avatar_small
依云 说:
Oct 26, 2012 04:57:00 PM

嗯,gcc 把 *3 弄成 leal (%rax,%rax,2), %esi 了~

MaskRay 说:
Oct 31, 2012 08:27:33 PM

域名和郵箱都更新了……

注意設置一個常數 n 把 n 以下的結果都緩存
http://hpaste.org/77055

Avatar_small
依云 说:
Oct 31, 2012 09:36:12 PM

Gravatar 还没更新呢。
缓存我也想啊,但是不会 :-(
另外,Python 用缓存的结果也很不理想 :-(
hpaste 这网站不错 :-)

Avatar_small
依云 说:
Oct 31, 2012 09:58:46 PM

>>> ./t
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
喵……

MaskRay 说:
Oct 31, 2012 10:17:56 PM

只緩存比如1000000以下的結果……不要全部緩存

Fermat618 说:
Nov 10, 2012 07:49:58 PM

你太小睢现在的编译器了。

Fermat618 说:
Nov 10, 2012 09:10:36 PM

想要快么,用 julia 吧,非缓存版本,不用特殊优化选项,0.74s.

function find_longest()
starting_number = 1
length_of_chains = 1
for i =1:1000000
n_tmp :: Int64 = i
steps = 1
while (n_tmp != 1)
if n_tmp % 2 == 0
n_tmp = n_tmp / 2
else
n_tmp = n_tmp * 3 + 1
end
steps = steps + 1
end
if length_of_chains < steps
length_of_chains = steps
starting_number = i
end
end
starting_number
end
println(@time find_longest())

alsotang 说:
Nov 10, 2012 10:40:04 PM

能不能不要有事没事就发邮件过来啊。。

Avatar_small
依云 说:
Nov 11, 2012 12:30:12 AM

邮件里有取消通知的链接,你访问下就好。

Fermat618 说:
Nov 18, 2012 11:31:54 AM

你写的 Haskell 还是一如既往的丑啊。

Fermat618 说:
Nov 18, 2012 01:28:04 PM

haskell 的优化还有待提高。一样语义的程序,我这个就只能到 8 秒。

find_max nmax =
____let total_steps n =
____________let total_steps_sub n acc
____________________|(n == 1) = acc
____________________|(even n) = total_steps_sub (n `div` 2) (acc + 1)
____________________|(otherwise) = total_steps_sub (n*3 + 1) (acc + 1)
____________in
________________total_steps_sub n 1
________find_max_sub n max_index max_value
____________|(n == 0) = max_index
____________|(otherwise) =
________________let t = total_steps n
____________________result
________________________|(t > max_value) = find_max_sub (n-1) n t
________________________|(otherwise) = find_max_sub (n-1) max_index max_value
________________in
____________________result
____in
________find_max_sub nmax 1 1

main = print (find_max 1000000)

Avatar_small
依云 说:
Nov 18, 2012 02:36:40 PM

你写得太丑了招编译器讨厌了 :D


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

部分静态文件存储由又拍云存储提供。 | Theme: Aeros 2.0 by TheBuckmaker.com