Haskell极慢的简单复发

Question

我正在尝试haskell用简单的递归max算法进行分析：

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x:xs) =
    let {m = max_tag x xs} in
      let {b = (Prelude.<=) m head} in
        case b of {True -> head; False -> m}

当我将其与python势在必式等价物进行比较时，我会得到 10x速度因子赞成Python：

with open("input.txt") as fl:
    data = [int(d) for d in fl.read().splitlines()]
max_ = 0
for d in data:
    if max_ < d:
        max_ = d
print(max_)

• 似乎在haskell案例中使用 tail recursion 的固有限制，我对吗？
• 有什么其他使Haskell代码更快的方法？
• 输入文件包含1M未签名的，无绑定的整数（平均32位数字）

，这是完整的haskell file（不确定需要它）：

import Max
import System.IO  
import Control.Monad
import System.Environment
import Prelude

readInt :: String -> Integer
readInt = read

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x:xs) =
    let {m = max_tag x xs} in
      let {b = (Prelude.<=) m head} in
        case b of {True -> head; False -> m}

main = do
    args <- getArgs
    contents <- readFile "input.txt"
    let numbers_as_strings = words $ contents
    let numbers = map readInt numbers_as_strings
    let max_number = max_tag 0 numbers
    print max_number

编辑： @willem van onsem建议的重构， 作品！ （28秒 - ＆gt; 12秒）

max_bar :: Integer -> [Integer] -> Integer
max_bar head [] = head
max_bar head (x:xs) =
  let {b = head < x} in
    let {m = case b of {True -> x; False -> head}} in
      max_bar m xs

关于进一步改进的任何想法？我必须比Python快！

Answer 1

一种比 @noughtmare的答案更有效的方法是使用data.bytestring，它没有处理编码的开销，这里不需要。在我的测试中，以100万个随机32位数字作为输入，这在〜290ms中运行，而 @noughtmare的答案在约1020毫秒内运行。为了进行比较，原始的Python One运行〜560ms。

import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as C
import Data.Maybe (fromJust)

-- NOTE: This will throw an error if parsing fails.
readInt :: B.ByteString -> Integer
readInt = fst . fromJust . C.readInteger

main :: IO ()
main = do
  contents <- B.readFile "read-integers.txt"
  let numbers = map readInt $ C.lines contents
  print $ max_tag 0 numbers

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x : xs) = max_tag (max head x) xs

Answer 2

使用此功能基于您的函数应该使其变得更快（也请确保使用文本版本2.0或更高版本）：

import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

readInt :: T.Text -> Integer
readInt t = 
  case T.signed T.decimal t of
    Right (x, _) -> x

main :: IO ()
main = do
    args <- getArgs
    contents <- T.readFile "input.txt"
    let numbers_as_strings = T.words contents
    let numbers = map readInt numbers_as_strings
    let max_number = max_tag 0 numbers
    print max_number

您还可以通过制作来加快max_tag函数来加快速度它会递归递归，从而避免了大量内存分配：

max_tag :: Integer -> [Integer] -> Integer
max_tag head [] = head
max_tag head (x:xs) 
  | x <= head = max_tag head xs
  | otherwise = max_tag x xs

您可以使用foldr使其更快地使其更快，以便使用MAP READINT获得foldr/build Fusion：

max_tag :: Integer -> [Integer] -> Integer
max_tag x0 xs = foldr (\x go y -> if x > y then go x else go y) id xs x0