为什么这个程序的F＃版本比Haskell版本快6倍？ [英] Why is the F# version of this program 6x faster than the Haskell one?

问题描述

Haskell版本（1.03s）：
$ b

module Main其中
导入限定Data.Text作为T
导入限定的Data.Text.IO作为TIO
导入Control.Monad
导入Control.Applicative（（< $>））
导入数据。 Vector.Unboxed（Vector，（！））
将合格的Data.Vector.Unboxed导入为V

solve :: Vector Int - > Int
解析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（读取T.unpack）TIO.getLine - 使用Data.Text，该示例的结束速度提高15％ 。
T.unlines。映射（T.pack。show。solve.V.fromList.map（read.tunpack）.token）
< $> replicateM t（TIO.getLine>> TIO.getLine）>> = TIO.putStr


F＃版本（0.17s）：
$ b

 打开系统
 
 let solve（ar：uint64 []）= 
 let ar'= 
 let t = Array.scanBack max ar 0UL |>有趣的x  - > Array.take（x.Length-1）x 
 Array.zip ar t 
 
 let 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）
 $ b $ get getInt（）= getIntLine（）。[0] 
 
 let t = getInt（）
 for i = 1 to int t do 
 getInt（）|>忽略
 let ar = getIntLine（）
 printfn％i（solve ar）
  

以上两个计划是股票最大化问题的解决方案，时间为第一个测试用例是运行代码按钮。

由于某些原因，F＃版本大约快了6倍，但是我我敢肯定，如果我用命令式循环取代了缓慢的库函数，我可以加快它至少3倍，更可能是10倍。

Haskell版本可以同样的改进？

我正在为学习目的做上述工作，一般来说，我很难弄清楚如何编写高效的Haskell代码。 $ b

解决方案

如果您切换到 ByteString 和stick使用普通的Haskell列表（而不是向量），您将获得更高效的解决方案。您也可以用单个左侧折叠和旁路zip和右侧扫描^（1）来重写solve函数。
总体而言，在我的机器上，与您的 Haskell 解决方案相比，性能提升了20倍。（2）。

下面的Haskell代码执行速度比F＃代码快：

  import Data.List（unfoldr）
 import Control.Applicative（（< $>））
 import Control.Monad（replicateM_）
 import Data.ByteString（ByteString）
将限定的Data.ByteString导入为B 
导入合格Data.ByteString.Char8作为C 
 
 parse :: ByteString  - > [Int] 
 parse = unfoldr $ C.readInt。 C.dropWhile（==''）
 
解析:: [Int]  - > Int 
求解xs = foldl go（const 0）xs minBound 
其中go f x s = if s< x then f x else s  -  x + f s 
 
 main = do 
 [n]<  -  parse< $> B.getLine 
 replicateM_ n $ B.getLine>> B.getLine>> =打印。解决。解析
  

<sub>1。请参阅编辑获取此答案的早期版本，该版本使用 solve 来使用 zip 和 scanr 。

2。 HackerRank网站显示出更大的性能提升。</sub>

Haskell version(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# version(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)

The above two programs are the solutions for the Stock Maximize problem and times are for the first test case of the Run Code button.

For some reason the F# version is roughly 6x faster, but I am pretty sure that if I replaced the slow library functions with imperative loops that I could speed it up by at least 3 times and more likely 10x.

Could the Haskell version be similarly improved?

I am doing the above for learning purposes and in general I am finding it difficult to figure out how to write efficient Haskell code.

解决方案

If you switch to ByteString and stick with plain Haskell lists (instead of vectors) you will get a more efficient solution. You may also rewrite the solve function with a single left fold and bypass zip and right scan ⁽¹⁾. Overall, on my machine, I get 20 times performance improvement compared to your Haskell solution ⁽²⁾.

Below Haskell code performs faster than the F# code:

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 f x s = if s < x then f x else s - x + f s

main = do
    [n] <- parse <$> B.getLine
    replicateM_ n $ B.getLine >> B.getLine >>= print . solve . parse

<sub>1. See edits for an earlier version of this answer which implements solve using zip and scanr.
2. HackerRank website shows even a larger performance improvement.</sub>

这篇关于为什么这个程序的F＃版本比Haskell版本快6倍？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！