Pourquoi est la version F # de ce programme 6 x plus rapide que le Haskell un ?

Question

Haskell version(1.03 s):

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,17 s):

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)

Les deux programmes sont les solutions pour le Stock de Maximiser le problème et le temps sont pour le premier test de l' Run Code bouton.

Pour une raison quelconque, le F# version est d'environ 6x plus rapide, mais je suis sûr que si je l'ai remplacé la lenteur des fonctions de la bibliothèque avec l'impératif de boucles que j'ai pu accélérer par au moins 3 fois et plus susceptibles de 10x.

Pourrait le Haskell version en être de même améliorée?

Je suis en train de faire le ci-dessus à des fins d'apprentissage et, en général, je trouve qu'il est difficile de comprendre comment écrire efficace du code Haskell.

Answer 1

Si vous passez en ByteString et le bâton avec plaine Haskell listes (au lieu de vecteurs), vous obtiendrez une solution plus efficace. Vous pouvez également réécrire le résoudre fonction avec un seul de gauche pli de dérivation et de zip et à droite de balayage ⁽¹⁾. Dans l'ensemble, sur mon ordinateur, je reçois 20 fois l'amélioration de la performance par rapport à votre Haskell solution de ⁽²⁾.

Ci-dessous code Haskell effectue plus rapidement que le code 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

<sub>1. Voir modifications pour une version antérieure de cette réponse qui implémente solve l'aide zip et scanr.
2. HackerRank site web montre même une plus grande amélioration de la performance.</sub>

Answer 2

Si je voulais le faire rapidement en F#, je vous conseille d'éviter toutes les fonctions d'ordre supérieur à l'intérieur d' solve et il suffit d'écrire un C-style impératif de la boucle:

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

D'après mes mesures, c'est 11x plus vite que votre F#.

Ensuite, la performance est limitée par l'OI couche (unicode analyse) et de la chaîne de fractionnement. Cela peut être optimisé par la lecture dans un tampon d'octets et de l'écriture de l'analyseur lexical par la main:

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

Answer 3

Juste pour mémoire, le F# version est également pas optimal. Je ne pense pas que cela importe vraiment, à ce point, mais si les gens voulaient comparer les performances, il est intéressant de noter qu'il peut être plus rapide.

Je n'ai pas essayé très dur (vous pouvez certainement le faire encore plus vite en utilisant restreint de mutation, ce qui ne serait pas contre la nature de F#), mais le simple changement d'utiliser Seq au lieu de Array dans les bons endroits (pour éviter l'allocation temporaire tableaux) rend le code à propos de 2x à 3x plus rapide:

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'

Si vous utilisez Seq.zip, vous pouvez également déposer l' take appel (parce que Seq.zip tronque la séquence automatiquement). Mesurée à l'aide de #time en utilisant le code suivant:

let rnd = Random()
let inp = Array.init 100000 (fun _ -> uint64 (rnd.Next()))
for a in 0 .. 10 do ignore (solve inp) // Measure this line

Je reçois environ 150ms pour le code d'origine et de quelque chose entre 50-75ms à l'aide de la nouvelle version.