Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is the F# version of this program 6x faster than the Haskell one?

Haskell version(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 

F# version(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) 

The above two programs are the solutions for the Stock Maximize problem and times are for the first test case of the Run Code button.

For some reason the F# version is roughly 6x faster, but I am pretty sure that if I replaced the slow library functions with imperative loops that I could speed it up by at least 3 times and more likely 10x.

Could the Haskell version be similarly improved?

I am doing the above for learning purposes and in general I am finding it difficult to figure out how to write efficient Haskell code.

like image 892
Marko Grdinić Avatar asked May 30 '16 13:05

Marko Grdinić


People also ask

What is so special about the F-35?

Designed from the ground up to prioritize low-observability, the F-35 may be the stealthiest fighter in operation today. It uses a single F135 engine that produces 40,000 lbs. of thrust with the afterburner engaged, capable of pushing the sleek but husky fighter to speeds as high as Mach 1.6.

Is the F-35A good fighter?

The F-35 Lightning II is considered the most modern fighter jet in the world. The jet, made by US manufacturer Lockheed Martin, is considered more than just a fighter aircraft.

Why is the F-22 so good?

Thrust vectoring means the F-22 can point its engine nozzles slightly up and down for greater control and maneuverability. Very few aircraft on the planet have that capability, and skilled Raptor pilots like Gunderson can use it to tie adversaries in knots.

Is the F-16 still good?

The jet will continue to be USAF's low-end, multipurpose force builder. The F-16 can be that “one airplane that can do a lot of low-end missions, and remarkably cheaper than a fifth-generation platform, and it can do them well,” he said.


1 Answers

If you switch to ByteString and stick with plain Haskell lists (instead of vectors) you will get a more efficient solution. You may also rewrite the solve function with a single left fold and bypass zip and right scan (1). Overall, on my machine, I get 20 times performance improvement compared to your Haskell solution (2).

Below Haskell code performs faster than the F# code:

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. See edits for an earlier version of this answer which implements solve using zip and scanr.
2. HackerRank website shows even a larger performance improvement.

like image 130
behzad.nouri Avatar answered Sep 30 '22 05:09

behzad.nouri