Почему версия F # этой программы на 6 раз быстрее, чем у Haskell?

Версия 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,17 с):

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)

Вышеуказанные две программы - это решения для Проблема с максимальным объемом запасов, а время для первого тестового примера кнопки Run Code.

По какой-то причине версия F # примерно на 6 раз быстрее, но я уверен, что если бы я заменил медленные библиотечные функции императивными циклами, я мог бы ускорить ее, по крайней мере, в 3 раза и более вероятно 10x.

Можно ли улучшить версию Haskell?

Я делаю это выше для учебных целей, и в целом мне трудно понять, как писать эффективный код Haskell.

Ответы

Ответ 1

Если вы переключитесь на ByteString и придерживаетесь простых списков Haskell (вместо векторов), вы получите более эффективное решение. Вы также можете переписать функцию решения с помощью одного левого сложения и обходной почты и правого сканирования ⁽¹⁾. В целом, на моей машине я добился 20-кратного повышения производительности по сравнению с вашим решением Haskell ⁽²⁾.

Ниже код 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 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

<суб > 1. См. изменения для более ранней версии этого ответа, который реализует solve с помощью zip и scanr.
<Суб > 2. Веб-сайт HackerRank показывает даже большее улучшение производительности.

Ответ 2

Если бы я захотел сделать это быстро в F #, я бы избегал всех функций более высокого порядка внутри solve и просто написал императивный цикл 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 p m
    sr <- sr + m - p
  sr

По моим измерениям, это на 11 раз быстрее, чем ваш F #.

Тогда производительность ограничена уровнем ввода-вывода (разбор Unicode) и разбиением строк. Это может быть оптимизировано путем чтения в буфер байта и записи лексера вручную:

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

Ответ 3

Только для записи версия F # также не оптимальна. Я не думаю, что это действительно важно на данный момент, но если люди хотели сравнить производительность, то стоит отметить, что это можно сделать быстрее.

Я не очень старался (вы можете сделать это еще быстрее, используя ограниченную мутацию, которая не противоречит природе F #), но простое изменение для использования Seq вместо Array в правильных местах (чтобы избежать выделения временных массивов) делает код примерно в 2 раза быстрее:

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

Я получаю около 150 мс для исходного кода и что-то между 50-75 мс с использованием новой версии.