versione Haskell (1.03s):Perché la versione F # di questo programma è 6 volte più veloce di quella Haskell?
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 # versione (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)
I due programmi di cui sopra sono le soluzioni per le Stock Maximize problem ed i tempi sono per il primo caso di prova del Run Code
pulsante.
Per qualche motivo la versione F # è circa 6 volte più veloce, ma sono abbastanza sicuro che se avessi sostituito le funzioni di libreria lente con cicli imperiosi, avrei potuto accelerarlo di almeno 3 volte e più probabilmente 10 volte.
La versione Haskell potrebbe essere migliorata in modo simile?
Sto facendo quanto sopra per scopi di apprendimento e in generale trovo difficile capire come scrivere codice Haskell efficiente.
Solo per la cronaca, cosa stai misurando? L'esecuzione dell'intero programma (dalla riga di comando) o del runtime del corpo (utilizzando qualcosa non mostrato nello snippet)? –
Avrei immaginato che per codice puramente funzionale, Haskell sarebbe stato prima di F # almeno. Nell'attuale versione '4.0', F # non ha nemmeno fold, scan e zip in linea. Immagino che per un codice simile, puramente funzionale, Haskell debba superare F # a causa delle ottimizzazioni offerte dalla sua purezza. –
Quello che sto misurando è quando [vado a] (https://www.hackerrank.com/challenges/stockmax), incollare quei programmi e premere RunCodeRunCodeRun Code. Non la piena sottomissione. Il tempo verrà stampato in alto. –