2016-05-30 16 views
49

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.

+1

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)? –

+2

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. –

+0

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. –

risposta

71

Se si passa a ByteString e si utilizzano semplicemente elenchi Haskell (anziché vettori) si otterrà una soluzione più efficiente. È anche possibile riscrivere la funzione di risoluzione con una sola piega sinistra e bypass zip e scansione destra (1). Nel complesso, sulla mia macchina, ottengo un miglioramento delle prestazioni di 20 volte rispetto alla soluzione Haskell(2).

Di seguito il codice Haskell esegue più velocemente di quanto il codice 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. Cfr edits per una versione precedente di questa risposta che implementa solve utilizzando zip e scanr.
2. Il sito Web HackerRank mostra anche un miglioramento delle prestazioni più ampio.

+2

Capisco che le funzioni stringa dovrebbero essere lente, ma le funzioni di testo dovrebbero essere anche lente? –

+1

@MarkoGrdinic con testo solo ascii, il mio _guess_ è che 'ByteString.Char8' esegue più velocemente di' Text'; ma affidati ai tuoi parametri di riferimento. –

+4

Puoi farlo cinque volte più velocemente - 0,02 anziché 0,1 - se ripristini l'utilizzo di vettori non in scatola per la funzione principale 'solve', ora che il problema è ben analizzato sprunge.us/PUYW – Michael

43

Solo per la cronologia, anche la versione F # non è ottimale. Non penso che sia importante a questo punto, ma se le persone volessero confrontare le prestazioni, allora vale la pena notare che può essere reso più veloce.

Non ho provato molto duro (si può certamente fare ancora più veloce utilizzando la mutazione ristretta, che non sarebbe contro la natura di F #), ma il cambiamento semplice da usare Seq invece di Array nei posti giusti (per evitare assegnazione array temporanei) rende il codice su 2x a 3x più velocemente:

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' 

Se si utilizza Seq.zip, si può anche cadere la chiamata take (perché Seq.zip tronca automaticamente la sequenza). Misurato utilizzando #time utilizzando il seguente frammento:

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

I aggirare 150ms per il codice originale e qualcosa tra 50-75ms che utilizzano la nuova versione.

+7

Ho postato una soluzione F # molto più veloce, ma è stata ridimensionata in oblio ... –

+2

@JonHarrop Speravo che tu ti unissi al gioco :-). Non preoccuparti dei downvotes, l'intera domanda verrà probabilmente eliminata presto perché "non si adatta al formato Q & A" o qualcosa del genere. –

+4

In tutta onestà dovrebbe essere nella revisione del codice –

50

Se avessi voluto farlo rapidamente in F # Vorrei evitare tutte le funzioni di ordine superiore all'interno solve e solo scrivere un C-style ciclo imperativo:

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 

Secondo le mie misure, questo è 11 volte più veloce del tuo F #.

Quindi le prestazioni sono limitate dal livello IO (analisi unicode) e dalla divisione delle stringhe. Questo può essere ottimizzato leggendo in un buffer di byte e scrivendo il 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 
+1

Secondo [HackerRank] (https://www.hackerrank.com/challenges/stockmax), è leggermente più veloce, 0,14 anziché 0,17 – Michael

+13

Non appena ho visto una domanda con le parole F # e Haskell, ho iniziato a scansionare la pagina per la risposta di Dr. Harrop! – Shredderroy

+1

FYI; a causa di un problema nel compilatore F # c'è un extra 5% da guadagnare scrivendo questo come una funzione ricorsiva in coda che va verso 0. – FuleSnabel

Problemi correlati