18

我想，我正在测试partition列表函数的性能，得到了一些奇怪的结果。

我们有那个partition p xs == (filter p xs, filter (not . p) xs)但我们选择了第一个实现，因为它只对列表执行一次遍历。然而，我得到的结果表明，使用使用两次遍历的实现可能会更好。

这是显示我所看到内容的最小代码

import Criterion.Main
import System.Random
import Data.List (partition)

mypartition :: (a -> Bool) -> [a] -> ([a],[a])
mypartition p l = (filter p l, filter (not . p) l)



randList :: RandomGen g => g -> Integer -> [Integer]
randList gen 0 = []
randList gen n = x:xs
  where
    (x, gen') = random gen
    xs = randList gen' (n - 1)

main = do
  gen <- getStdGen
  let arg10000000 = randList gen 10000000
  defaultMain [
      bgroup "filters -- split list in half " [
        bench "partition100"         $ nf (partition (>= 50)) arg10000000
      , bench "mypartition100"       $ nf (mypartition (>= 50)) arg10000000
      ]
      ]

-O我在有和没有它的情况下都运行了测试，两次我都认为双遍历更好。

我正在ghc-7.10.3使用criterion-1.1.1.0

我的问题是：

  • 这是预期的吗？

  • 我是否正确使用了标准？我知道惰性可能很棘手，(filter p xs, filter (not . p) xs)如果使用元组的两个元素，只会进行两次遍历。

  • 这是否与 Haskell 中处理列表的方式有关？

非常感谢！

4

1 回答 1

5

这个问题没有非黑即白的答案。要剖析问题，请考虑以下代码：

import Control.DeepSeq
import Data.List (partition)
import System.Environment (getArgs)


mypartition :: (a -> Bool) -> [a] -> ([a],[a])
mypartition p l = (filter p l, filter (not . p) l)


main :: IO ()
main = do
  let cnt = 10000000
      xs = take cnt $ concat $ repeat [1 .. 100 :: Int]
  args <- getArgs
  putStrLn $ unwords $ "Args:" : args
  case args of
    [percent, fun]
      -> let p = (read percent >=)
         in case fun of
           "partition"      ->              print $ rnf $ partition   p xs
           "mypartition"    ->              print $ rnf $ mypartition p xs
           "partition-ds"   -> deepseq xs $ print $ rnf $ partition   p xs
           "mypartition-ds" -> deepseq xs $ print $ rnf $ mypartition p xs
           _ -> err
    _ -> err
  where
    err = putStrLn "Sorry, I do not understand."

我不使用 Criterion 来更好地控制评估顺序。为了获得时间，我使用+RTS -s运行时选项。使用不同的命令行选项执行不同的测试用例。第一个命令行选项定义谓词保存的数据百分比。第二个命令行选项在不同的测试之间进行选择。

测试区分两种情况：

  1. 数据是惰性生成的（第二个参数partition或mypartition）。
  2. 数据已经在内存中进行了全面评估（第二个参数partition-ds或mypartition-ds）。

分区的结果总是从左到右进行评估，即从包含谓词所适用的所有元素的列表开始。

情况 1partition的优点是第一个结果列表的元素在输入列表的所有元素都生成之前就被丢弃了。情况 1 特别好，如果谓词匹配许多元素，即第一个命令行参数很大。

在情况 2 中，partition无法发挥这种优势，因为所有元素都已在内存中。

对于mypartition，在任何情况下，在计算第一个结果列表之后，所有元素都保存在内存中，因为再次需要它们来计算第二个结果列表。因此，这两种情况没有太大区别。

看起来，使用的内存越多，垃圾收集就越困难。因此partition非常适合，如果谓词匹配许多元素并且使用惰性变体。

相反，如果谓词不匹配许多元素或所有元素都已在内存中，则mypartition性能更好，因为它的递归不处理与partition.

Stackoverflow 问题“<a href="https://stackoverflow.com/questions/11625840/irrefutable-pattern-does-not-leak-memory-in-recursion-but-why">无可辩驳的模式不会在递归中泄漏内存， 但为什么？” 可能会对partition.

于 2016-08-04T17:09:04.553 回答