代码之家 › 专栏 › 技术社区 › twosan

Haskell:两个版本代码之间的速度差异

profiling optimization haskell

3

twosan · 技术社区 · 8 年前

“标准haskell友好型” 解决方案和我的版本

我相信哈斯凯勒的同事们,这种表现上的差异有一个很好的原因,我对此一无所知,可以在这个话题上教育我。

查找数字字符串中的最大5位数

两者使用相同的概念求解时:生成所有5位数字并找到最大值。

digit5 :: String -> Int
digit5 = maximum . map (read . take 5) . init . tails

丑陋且非常慢的代码(一旦字符串大)

digit5' :: String -> String -> String
-- xs - input string
-- maxim - current maximal value
digit5' xs maxim 
  | (length xs) < 5 = maxim
  | y > maxim = digit5' (drop 1 xs) y -- use new detected maximum value
  | otherwise = digit5' (drop 1 xs) maxim
  where y = take 5 xs

digit5 :: String -> Int
digit5 xs
-- return the original string if the input size is smaller than 6
  | length (xs) < 6 = read xs 
  | otherwise = read $ digit5' xs "00000"

对于小输入,我得到的执行时间大致相同,对于大输入,我开始看到非常大的差异(对于44550个元素的输入):

Computation time for ugly version: 2.047 sec
Computation time for nice version: 0.062 sec

我对此的肤浅理解是,fast代码正在使用 .对于较慢的版本,使用递归,但我认为应该可以咬尾巴。但是在一个 缺乏经验的

虽然较慢的函数对字符串进行比较,而不是将其转换为数字,但我也尝试将字符串转换为整数,但没有任何大的改进

我尝试过使用不带任何标志和以下命令的ghc进行编译:

ghc 
ghc -O2 
ghc -O2 -fexcess-precision -optc-O3 -optc-ffast-math -no-
recomp 
stack runhaskell 
ghc -O3

https://pastebin.com/kuS5iKgd

1 回复 | 直到 8 年前

1

9

Fyodor Soikin 8 年前

你的“慢”版本的问题是这一行:

| length xs < 5 = maxim

xs ,并且由于Haskell列表是单链表,因此该操作需要完全遍历整个列表,即O(n)。每次迭代都会发生这种情况。有N次迭代。这使得整个过程为O(n^2)。

如果您只是用以下内容替换有问题的行:

| null xs = maxim

它将使整个事情只是线性的,它将与“优雅”的解决方案一样快。当然,这将导致额外的5次迭代,但通过降低总体复杂度,损失得到了更多补偿。

digit5 = maximum . map (read . take 5) . filter ((>= 5) . length) . tails