在某种情况下,国家的表现比我预期的要慢.为什么？

Question

考虑一下这个功能reverseAndMinimum(从附近的另一个答案略微修改):

import Control.Monad.State.Strict

reverseAndMinimum' :: Ord a => [a] -> State a [a] -> State a [a]
reverseAndMinimum' [ ] res = res
reverseAndMinimum' (x:xs) res = do
        smallestSoFar <- get
        when (x < smallestSoFar) (put x)
        reverseAndMinimum' xs ((x:) <$> res)

reverseAndMinimum :: Ord a => [a] -> ([a], a)
reverseAndMinimum [ ] = error "StateSort.reverseAndMinimum: This branch is unreachable."
reverseAndMinimum xs@(x:_) = runState (reverseAndMinimum' xs (return [ ])) x

它只遍历一次论证; 然而,它比两次执行它的天真函数慢约30%:

reverseAndMinimum_naive :: Ord a => [a] -> ([a], a)
reverseAndMinimum_naive xs = (reverse xs, minimum xs)

它还消耗大约57%的内存.

以下是来自运行的相关摘录+RTS -s:

reverseAndMinimum

     176,672,280 bytes allocated in the heap
...

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.064s  (  0.063s elapsed)
  GC      time    0.311s  (  0.311s elapsed)
  EXIT    time    0.005s  (  0.005s elapsed)
  Total   time    0.379s  (  0.380s elapsed)

  %GC     time      82.0%  (82.0% elapsed)

reverseAndMinimum_naive

     112,058,976 bytes allocated in the heap
...

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.041s  (  0.040s elapsed)
  GC      time    0.245s  (  0.245s elapsed)
  EXIT    time    0.005s  (  0.005s elapsed)
  Total   time    0.291s  (  0.291s elapsed)

  %GC     time      84.2%  (84.3% elapsed)

 

发生了什么,我该如何诊断,是否有可能改善？

PSmain对于运行测试很方便:

main = do
    top <- (read :: String -> Int) . (!! 0) <$> getArgs
    val <- evaluate . force $ reverseAndMinimum (take top [top, top - 1.. 1 :: Int])
    print $ (\x -> (last . fst $ x, snd x)) $ val

Answer 1

编辑:这是指问题的先前版本在哪里reverseAndMinimum :: Ord a => [a] -> State a ([a] -> [a]).

在朴素版本中,reverse它是高效的,因为它可以在遍历列表时直接构建反向列表,并且minimum因为不需要而被忽略.

"一次通过" reverseAndMinimum分配差异列表,必须应用该列表以产生实际列表,然后再次遍历该列表以查找其最后一个元素.

复制所使用的累加器技术reverse,以下代码编译为紧密循环,以计算一次传递中列表的反向和最小值.

import Control.Monad.State.Strict

reverseAndMinimum :: Ord a => [a] -> ([a], a)
reverseAndMinimum [ ] = error "Empty list!"
reverseAndMinimum (x:xs) = runState (reverseAndMinimum' xs [x]) x

reverseAndMinimum' :: Ord a => [a] -> [a] -> State a [a]
reverseAndMinimum' [ ] acc = return acc
reverseAndMinimum' (x:xs) acc = do
    smallestSoFar <- get
    when (x < smallestSoFar) (put $ x)
    reverseAndMinimum' xs (x : acc)