performance - tuplas - tipo de funciones haskell

¿Por qué la versión F#de este programa es 6 veces más rápida que la de Haskell?

Question

Versión de 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

Versión 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)

Los dos programas anteriores son las soluciones para el problema Stock Maximize y los tiempos son para el primer caso de prueba del botón Run Code .

Por alguna razón, la versión F # es aproximadamente 6 veces más rápida, pero estoy bastante seguro de que si reemplazara las funciones lentas de la biblioteca con bucles imperativos, podría acelerarla al menos 3 veces y más probablemente 10 veces.

¿Podría la versión de Haskell ser mejorada de manera similar?

Estoy haciendo lo anterior con fines de aprendizaje y, en general, me resulta difícil descubrir cómo escribir un código Haskell eficiente.

Answer 1

Si cambia a ByteString y se ByteString con listas simples de Haskell (en lugar de vectores), obtendrá una solución más eficiente. También puede reescribir la función de resolución con un solo pliegue izquierdo y omitir el zip y el escaneo derecho ⁽¹⁾ . En general, en mi máquina, obtengo una mejora de rendimiento 20 veces mayor en comparación con su solución Haskell ⁽²⁾ .

El siguiente código de Haskell funciona más rápido que el código 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. Vea las edits para una versión anterior de esta respuesta que implementa solve usando zip y scanr .
2. El sitio web de HackerRank muestra una mejora aún mayor en el rendimiento.</sub>

Answer 2

Si quisiera hacerlo rápidamente en F #, evitaría todas las funciones de orden superior dentro de solve y simplemente escribiría un bucle imperativo de estilo 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

Según mis mediciones, esto es 11 veces más rápido que su F #.

Entonces, el rendimiento está limitado por la capa IO (análisis unicode) y la división de cadenas. Esto se puede optimizar leyendo en un búfer de bytes y escribiendo el lexer a mano:

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

Solo para el registro, la versión F # tampoco es óptima. No creo que realmente importe en este momento, pero si la gente quisiera comparar el rendimiento, vale la pena señalar que se puede hacer más rápido.

No lo he intentado mucho (ciertamente puedes hacerlo aún más rápido usando una mutación restringida, que no estaría en contra de la naturaleza de F #), sino un simple cambio para usar Seq lugar de Array en los lugares correctos (para evitar asignar matrices temporales) hace que el código sea de 2x a 3x más rápido:

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 usa Seq.zip , también puede descartar la llamada de Seq.zip (porque Seq.zip trunca la secuencia automáticamente). Medido usando #time usando el siguiente fragmento:

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

Obtuve alrededor de 150ms para el código original y algo entre 50-75ms usando la nueva versión.