Pourquoi la version F # de ce programme est-elle 6 fois plus rapide que celle de Haskell?

Version 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 

Version 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) 

Les deux programmes ci-dessus sont les solutions pour le problème Stock Maximize et les heures correspondent au premier scénario de test du bouton Run Code .

Pour une raison quelconque, la version F # est environ 6 fois plus rapide, mais je suis sûr que si je remplaçais les fonctions de bibliothèque lentes par des boucles impératives, je pourrais accélérer au moins 3 fois et plus probablement 10 fois.

La version de Haskell pourrait-elle être améliorée de la même manière?

Je fais ce qui précède à des fins d’apprentissage et en général, j’ai du mal à comprendre comment écrire du code Haskell efficace.

Si vous passez à ByteSsortingng et que vous ByteSsortingng avec les listes Haskell simples (au lieu des vecteurs), vous obtiendrez une solution plus efficace. Vous pouvez également réécrire la fonction de résolution avec un simple zip à gauche et un bypass et un scan à droite (1) . Globalement, sur ma machine, j’obtiens 20 fois plus de performance que votre solution Haskell (2) .

Le code Haskell ci-dessous est plus rapide que le code F #:

 import Data.List (unfoldr) import Control.Applicative ((<$>)) import Control.Monad (replicateM_) import Data.ByteSsortingng (ByteSsortingng) import qualified Data.ByteSsortingng as B import qualified Data.ByteSsortingng.Char8 as C parse :: ByteSsortingng -> [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. Reportez-vous aux modifications apscopes à une version antérieure de cette réponse, qui implémente des solve utilisant zip et scanr .
2. Le site Web de HackerRank montre même une plus grande amélioration des performances.

Si je voulais le faire rapidement dans F #, j’éviterais toutes les fonctions d’ordre supérieur à l’intérieur de la solve et j’écrirais simplement une boucle impérative de style 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 

Selon mes mesures, ceci est 11 fois plus rapide que votre F #.

La performance est alors limitée par la couche IO (parsing unicode) et le fractionnement de chaînes. Cela peut être optimisé en lisant dans un tampon d’octets et en écrivant le lexer à 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 

Pour la petite histoire, la version F # n’est pas optimale non plus. Je ne pense pas que ce soit vraiment important à ce stade, mais si les gens veulent comparer les performances, il convient de noter que cela peut être fait plus rapidement.

Je n’ai pas essayé très fort (vous pouvez certainement le rendre encore plus rapide en utilisant des mutations restreintes, ce qui ne serait pas contre la nature de F #), mais simplement utiliser Seq au lieu de Array aux bons endroits (pour éviter d’allouer des tableaux temporaires) rend le code environ 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 supprimer l’appel de take (car Seq.zip tronque automatiquement la séquence). Mesuré en utilisant #time utilisant l’extrait 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 150 ms pour le code d’origine et quelque chose entre 50 et 75 ms en utilisant la nouvelle version.