I’m experimenting with Haskell
profiling with a simple recursive max
algorithm:
JavaScript
x
7
1
max_tag :: Integer -> [Integer] -> Integer
2
max_tag head [] = head
3
max_tag head (x:xs) =
4
let {m = max_tag x xs} in
5
let {b = (Prelude.<=) m head} in
6
case b of {True -> head; False -> m}
7
When I compare it to a python imperative equivalent, I get a 10x speed factor in favor of python:
JavaScript
1
8
1
with open("input.txt") as fl:
2
data = [int(d) for d in fl.read().splitlines()]
3
max_ = 0
4
for d in data:
5
if max_ < d:
6
max_ = d
7
print(max_)
8
- It seems there is an inherent limitation of using tail recursion in the
Haskell
case, am I right? - Any other way to make the Haskell code faster?
- The input file contains
1M
unsigned, unbounded integers (on average 32 digits)
For completeness, here is the complete Haskell
file (not sure it is needed):
JavaScript
1
24
24
1
import Max
2
import System.IO
3
import Control.Monad
4
import System.Environment
5
import Prelude
6
7
readInt :: String -> Integer
8
readInt = read
9
10
max_tag :: Integer -> [Integer] -> Integer
11
max_tag head [] = head
12
max_tag head (x:xs) =
13
let {m = max_tag x xs} in
14
let {b = (Prelude.<=) m head} in
15
case b of {True -> head; False -> m}
16
17
main = do
18
args <- getArgs
19
contents <- readFile "input.txt"
20
let numbers_as_strings = words $ contents
21
let numbers = map readInt numbers_as_strings
22
let max_number = max_tag 0 numbers
23
print max_number
24
EDIT: refactor suggested by @Willem Van Onsem, works ! (28 sec -> 12 sec)
JavaScript
1
7
1
max_bar :: Integer -> [Integer] -> Integer
2
max_bar head [] = head
3
max_bar head (x:xs) =
4
let {b = head < x} in
5
let {m = case b of {True -> x; False -> head}} in
6
max_bar m xs
7
Any ideas on further improvements? I must be faster than python !
Advertisement
Answer
Using this to benchmark your function should make it go much faster (also be sure to use text
version 2.0 or later):
JavaScript
1
18
18
1
import qualified Data.Text as T
2
import qualified Data.Text.IO as T
3
import qualified Data.Text.Read as T
4
5
readInt :: T.Text -> Integer
6
readInt t =
7
case T.signed T.decimal t of
8
Right (x, _) -> x
9
10
main :: IO ()
11
main = do
12
args <- getArgs
13
contents <- T.readFile "input.txt"
14
let numbers_as_strings = T.words contents
15
let numbers = map readInt numbers_as_strings
16
let max_number = max_tag 0 numbers
17
print max_number
18
You can also speed up your max_tag
function itself by making it tail recursive and thus avoiding a bunch of memory allocations:
JavaScript
1
6
1
max_tag :: Integer -> [Integer] -> Integer
2
max_tag head [] = head
3
max_tag head (x:xs)
4
| x <= head = max_tag head xs
5
| otherwise = max_tag x xs
6
You can make it even slightly faster by using foldr
so that you get foldr/build fusion with map readInt
:
JavaScript
1
3
1
max_tag :: Integer -> [Integer] -> Integer
2
max_tag x0 xs = foldr (x go y -> if x > y then go x else go y) id xs x0
3