本文来自依云'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'); }
Oct 24, 2012 08:48:22 PM
囧...不用racket的ide...快了差不多一半..
Oct 24, 2012 09:27:09 PM
不同的机器啊。
racket 还有 ide？叫什么名字呢？
Oct 24, 2012 09:56:57 PM
不是.我说我不用drracket用命令行.快了差不多一半..
叫drracket
Oct 24, 2012 09:58:43 PM
哦～看到了，GTK 的，还有中文翻译呢 ^_^
Oct 24, 2012 11:43:10 PM
我写的 Ruby 版本。
Oct 24, 2012 11:43:31 PM
https://gist.github.com/3946838
sorry，忘记给地址了。
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
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
Oct 26, 2012 09:07:30 AM
你这算法单线程已经非常快了，而且不需要保存状态。
不过可以稍作修改弄成个并发版本的，切割成每次扫1w个数，然后并发算这100份，最后再合并一下。
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
我是说怎么那么慢呢……
Oct 26, 2012 10:22:51 AM
不过还是没 LuaJIT 快啊 :-(
Oct 26, 2012 10:24:22 AM
应该并发4份吧，纯计算，并发那么多有用么？
Oct 26, 2012 11:38:37 AM
要是只针对特定的某台计算机，数目定死比较好，割的细的话，可以考虑到其他机子。我以前经验，在c下，粒度不要细于数十毫秒(单线程)的话，核更多都可以提升。
现在7.6版ghc可以运行时直接getNumCapabilities和setNumCapabilities的，也不需要硬设阈值了。
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
Oct 26, 2012 03:35:06 PM
你ghci里输入这两句看下结果：
:m +Foreign.Storable
sizeOf (1::Int)
如果结果等于4的话，则可以解释你无法终止的原因。Int的范围在Haskell里没有定义，有的等价于Int32，有的是Int64，如果这个题目用的是Int32，会因为上溢导致程序无法终止，你可以import Data.Int，然后把签名全换成Int64试试看。
Oct 26, 2012 03:40:33 PM
其实这程序非要比速度的话，是在比较各编程语言的编译器后端优化能力。能直接使用机器字的肯定都不会差太多。Ruby这类全对象的oop语言估计要哭。
Oct 26, 2012 03:50:01 PM
这题还可以再快一些的，因为都是*2 ，*3这种，所以可以把*2改成移位，*3改成一次移位和一次加法操作。
Oct 26, 2012 04:06:25 PM
那个不是编译器应该做的事么？
Oct 26, 2012 04:26:17 PM
的确，sizeOf (1::Int) 返回4。
换成Int64，-O2编译，仍然需要7s，比PyPy还慢
Oct 26, 2012 04:57:00 PM
嗯，gcc 把 *3 弄成 leal (%rax,%rax,2), %esi 了～
Oct 31, 2012 08:27:33 PM
域名和郵箱都更新了……
注意設置一個常數 n 把 n 以下的結果都緩存
http://hpaste.org/77055
Oct 31, 2012 09:36:12 PM
Gravatar 还没更新呢。
缓存我也想啊，但是不会 :-(
另外，Python 用缓存的结果也很不理想 :-(
hpaste 这网站不错 :-)
Oct 31, 2012 09:58:46 PM
>>> ./t
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
喵……
Oct 31, 2012 10:17:56 PM
只緩存比如1000000以下的結果……不要全部緩存
Oct 31, 2012 10:55:59 PM
不会……
Nov 10, 2012 07:49:58 PM
你太小睢现在的编译器了。
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())
Nov 10, 2012 10:40:04 PM
能不能不要有事没事就发邮件过来啊。。
Nov 11, 2012 12:30:12 AM
邮件里有取消通知的链接，你访问下就好。
Nov 18, 2012 11:31:54 AM
你写的 Haskell 还是一如既往的丑啊。
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)
Nov 18, 2012 02:36:40 PM
你写得太丑了招编译器讨厌了 :D