为什么这个程序的F＃版本比Haskell版本快6倍？
Haskell版本（1.03s）：
module Main where import qualified Data.Text as T import qualified Data.Text.IO as TIO import Control.Monad import Control.Applicative ((<$>)) import Data.Vector.Unboxed (Vector,(!)) import qualified Data.Vector.Unboxed as V solve :: Vector Int -> Int solve ar = V.foldl' go 0 ar' where ar' = V.zip ar (V.postscanr' max 0 ar) go sr (p,m) = sr + m - p main = do t <- fmap (read . T.unpack) TIO.getLine -- With Data.Text, the example finishes 15% faster. T.unlines . map (T.pack . show . solve . V.fromList . map (read . T.unpack) . T.words) <$> replicateM t (TIO.getLine >> TIO.getLine) >>= TIO.putStr F＃版本（0.17s）：
open System let solve (ar : uint64[]) = let ar' = let t = Array.scanBack max ar 0UL |> fun x -> Array.take (x.Length-1) x Array.zip ar t let go sr (p,m) = sr + m - p Array.fold go 0UL ar' let getIntLine() = Console.In.ReadLine().Split [|' '|] |> Array.choose (fun x -> if x <> "" then uint64 x |> Some else None) let getInt() = getIntLine().[0] let t = getInt() for i=1 to int t do getInt() |> ignore let ar = getIntLine() printfn "%i" (solve ar)
上述两个程序是股票最大化问题的解决scheme，时间是Run Codebutton的第一个testing用例。
出于某种原因，F＃版本大约快了6倍，但是我相当确定，如果我用命令循环replace了慢库函数，那么我可以加速至less3倍，更可能是10倍。
Haskell版本可以被类似地改进吗？
我正在做上述学习的目的，一般来说，我很难找出如何编写高效的Haskell代码。
如果你切换到ByteString并坚持使用普通的Haskell列表（而不是向量），你将得到一个更有效的解决scheme。 您也可以用一个左侧折叠和旁路拉链和右侧扫描（1）来重写解决function。 总的来说，在我的机器上，与Haskell解决scheme（2）相比，性能提高了20倍。
下面的Haskell代码执行比F＃代码更快：
import Data.List (unfoldr) import Control.Applicative ((<$>)) import Control.Monad (replicateM_) import Data.ByteString (ByteString) import qualified Data.ByteString as B import qualified Data.ByteString.Char8 as C parse :: ByteString -> [Int] parse = unfoldr $ C.readInt . C.dropWhile (== ' ') solve :: [Int] -> Int solve xs = foldl go (const 0) xs minBound where go fxs = if s < x then fx else s - x + fs main = do [n] <- parse <$> B.getLine replicateM_ n $ B.getLine >> B.getLine >>= print . solve . parse
1.请参阅使用zip和scanr solvescheme的早期版本的编辑 。
2. HackerRank网站显示更大的性能改善。
如果我想在F＃中快速执行该操作，我将避免解决所有高级函数，只需编写一个C风格的命令循环：
let solve (ar : uint64[]) = let mutable sr, m = 0UL, 0UL for i in ar.Length-1 .. -1 .. 0 do let p = ar.[i] m <- max pm sr <- sr + m - p sr
根据我的测量，这比F＃快了11倍。
然后性能受到IO层（unicodeparsing）和string拆分的限制。 这可以通过读入字节缓冲区并手动编写词法分析器来优化：
let buf = Array.create 65536 0uy let mutable idx = 0 let mutable length = 0 do use stream = System.Console.OpenStandardInput() let rec read m = let c = if idx < length then idx <- idx + 1 else length <- stream.Read(buf, 0, buf.Length) idx <- 1 buf.[idx-1] if length > 0 && '0'B <= c && c <= '9'B then read (10UL * m + uint64(c - '0'B)) else m let read() = read 0UL for _ in 1UL .. read() do Array.init (read() |> int) (fun _ -> read()) |> solve |> System.Console.WriteLine
只是为了logging，F＃版本也不是最佳的。 在这一点上，我觉得这并不重要，但如果人们想比较一下这个performance，那么值得注意的是它可以做得更快。
我没有很努力地尝试（通过使用受限制的变异，你可以更快地使用受限制的变异，这不会违背F＃的本质），但是在正确的位置使用Seq而不是Array来简单的改变（为了避免分配临时数组）使代码快2倍到3倍：
let solve (ar : uint64[]) = let ar' = Seq.zip ar (Array.scanBack max ar 0UL) let go sr (p,m) = sr + m - p Seq.fold go 0UL ar'
如果您使用Seq.zip ，您也可以放弃take电话（因为Seq.zip自动截断该序列）。 使用以下代码片段使用#time进行测量：
let rnd = Random() let inp = Array.init 100000 (fun _ -> uint64 (rnd.Next())) for a in 0 .. 10 do ignore (solve inp) // Measure this line
原来的代码约150ms，使用新版本的话，在50-75ms之间。
