在某种情况下，国家的表现比我预期的要慢。为什么？ [英] Performance of State in a certain case is slower than I would expect. Why?

问题描述

考虑函数 reverseAndMinimum （稍微从附近的另一个答案修改） ：

  import Control.Monad.State.Strict 
 
 reverseAndMinimum':: Ord a => [a]  - >陈述a [a]  - >状态a [a] 
 reverseAndMinimum'[] res = res 
 reverseAndMinimum'（x：xs）res = do 
 smallestSoFar < - 当$（x  （x）
 reverseAndMinimum'xs（（x :)< $> $）
 
 reverseAndMinimum :: Ord a => [a]  - > （[a]，a）
 reverseAndMinimum [] =错误StateSort.reverseAndMinimum：此分支无法访问。 
 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字节
 ... 
 
初始时间0.000s（已过0.000s）
 MUT时间0.064s （经过0.063s）
 GC时间0.311s（已过0.311s）
出口时间0.005s（已过0.005s）
总时间0.379s（已过0.380s）
 
％GC时间82.0％（经过82.0％）
  

reverseAndMinimum_naive

 在堆中分配112,058,976字节
 ... 
 
初始时间0.000s（已过0.000s）
 MUT时间0.041s（已过0.040s）
 GC时间0.245s（已过0.245s）
退出时间0.005秒（已过0.005秒）
总时间0.291秒（已过0.291秒）
 
％GC时间84.2％（已过84.3％）
  

 

发生什么事了，我该如何诊断，改进？

PS 用于运行测试的方便的 main ：

  main = do 
 top<  - （read :: String  - > Int）。 （!! 0）< $> getArgs 
 val < - 评估。强制$ reverseAndMinimum（取顶部[top，top  -  1..1 :: Int]）
 print $（\ x  - >（last。fst $ x，snd x））$ val 
  

解决方案

编辑：问题的以前版本，其中 reverseAndMinimum :: Ord a => [a] - >状态a（[a] - > [a]）。

在天真版中， reverse 是有效的，因为它可以在遍历列表时直接构建反转列表，并且 minimum 被忽略，因为它不是必需的。

一次传递 reverseAndMinimum 分配一个差异列表，必须应用该差异列表才能生成一个实际列表，然后再次遍历找到它的最后一个元素。

复制反向，下面的代码编译为一个紧密的循环来计算一次传递中列表的反向和最小值。



  import控制.Monad.State.Strict 
 
 reverseAndMinimum :: Ord a => [a]  - > （[a]，a）
 reverseAndMinimum [] =错误空列表！ 
 reverseAndMinimum（x：xs）= runState（reverseAndMinimum'xs [x]）x 
 
 reverseAndMinimum':: Ord a => [a]  - > [a]  - >状态a [a] 
 reverseAndMinimum'[] acc =返回acc 
 reverseAndMinimum'（x：xs）acc = do 
 smallestSoFar < - 获得
当（x  reverseAndMinimum'xs（x：acc）
  




Consider the function reverseAndMinimum (slightly modified from another answer nearby):

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

It traverses the argument only once; however, it is about 30% slower than a naive function that does it two times:

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

It also consumes about 57% as much memory.

Here are the relevant extracts from a run with +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)

 

What's happening, how can I diagnose, is it possible to improve?

P.S. A handy main for running tests:

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

解决方案

EDIT: this refers to a previous version of the question where reverseAndMinimum :: Ord a => [a] -> State a ([a] -> [a]).

In the naive version, reverse is efficient because it can build up the reversed list directly while traversing the list, and minimum is ignored because it's not needed.

The "one pass" reverseAndMinimum allocates a difference list, that must be applied to yield an actual list which is then traversed again to find its last element.

---

Replicating the accumulator technique used in reverse, the following code compiles to a tight loop to compute the reverse and minimum of a list in one pass.

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)

这篇关于在某种情况下，国家的表现比我预期的要慢。为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！