读了night_stalker老兄的[url=http://www.iteye.com/problems/12568]Ruby算法求优化：spoj PRIME1[/url]，深感自己对Ruby的性能特性了解的太少了。也试了些办法不过最多也就得到了10%左右的性能提升，没啥意义。
想想，干脆用F#来试试看。这个是F# 1.9.6.2，运行环境是HP nx9040/Windows 7 Beta Build 7000。随手写了一份代码，先通过记录已知的非质数得到sqrt(n)以内的质数表ps，然后用筛选法求m..n之间的质数：
#lightlet primesBetween m n = let pmax = int << sqrt << float <| n let rec loop i ps kn = if i > pmax then ps else let kn_next = List.fold_left (fun (acc : int Set) e -> acc.Add(e)) kn [i..i..pmax] loop (i + 2) (if kn.Contains(i) then ps else i :: ps) kn_next let ps = loop 3 [2] (Set []) let mm = if m <= 2 then 3 else if m % 2 = 0 then m + 1 else m let cand1 = List.init ((n - mm >>> 1) + 1) (fun i -> (i <<< 1) + mm) let cand2 = cand1 |> List.filter (fun e -> None = List.tryfind (fun p -> e % p = 0 && e <> p) ps) if m <= 2 then 2 :: cand2 else cand2open System.Diagnosticslet watch = new Stopwatch()watch.Start()let primes = primesBetween 999900000 1000000000watch.Stop()printfn "%A" primesprintfn "%A" watch.ElapsedMilliseconds
在我的机器上运行，速度居然跟Ruby 1.9.1差不多 OTL
[quote]5425L[/quote]
把第8行的List.fold_left和[i..i..pmax]换成对应的Seq版，Seq.fold和{i..i..pmax}，速度只有很细微的提升。瓶颈是出在什么地方我也没弄清楚。
呜，太慢了。不过慢的主要原因应该还是我写的太糟糕了。
这种事情还是应该开多线程并行计算的好。改用比较原始的筛选法就有机会并行。以后有空再玩玩 T T
