基准过滤器和分区
Benchmarking Filter and Partition
我正在测试 partition
列表函数的性能,我想得到了一些 st运行ge 结果。
我们有 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
我的问题是:
这是预期的吗?
我是否正确使用了 Criterion?我知道懒惰可能很棘手,如果元组的两个元素都被使用,(filter p xs, filter (not . p) xs)
只会进行两次遍历。
这是否与 Haskell 中列表的处理方式有关?
非常感谢!
这个问题没有非黑即白的答案。要剖析问题,请考虑以下代码:
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
运行时选项。使用不同的命令行选项执行不同的测试用例。第一个命令行选项定义谓词保留的数据百分比。第二个命令行选项在不同的测试之间进行选择。
测试区分两种情况:
- 延迟生成数据(第二个参数
partition
或 mypartition
)。
- 数据已在内存中完全计算(第二个参数
partition-ds
或 mypartition-ds
)。
分区的结果总是从左到右求值,即从包含谓词所对应的所有元素的列表开始。
在情况 1 partition
中,第一个结果列表的元素在输入列表的所有元素生成之前就被丢弃了。情况 1 特别好,如果谓词匹配很多元素,即第一个命令行参数很大。
在情况 2 中,partition
无法发挥此优势,因为所有元素都已在内存中。
对于mypartition
,在任何情况下,在计算第一个结果列表后,所有元素都保存在内存中,因为再次需要它们来计算第二个结果列表。因此,这两种情况之间没有太大区别。
看来,使用的内存越多,垃圾回收就越难。因此 partition
非常适合,如果谓词匹配许多元素并且使用惰性变体。
相反,如果谓词不匹配很多元素或所有元素都已在内存中,mypartition
表现更好,因为与 partition
相比,它的递归不处理对。
Whosebug 问题“Irrefutable pattern does not leak memory in recursion, but why?”可能会提供更多关于在 partition
.
的递归中处理对的见解
我正在测试 partition
列表函数的性能,我想得到了一些 st运行ge 结果。
我们有 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
我的问题是:
这是预期的吗?
我是否正确使用了 Criterion?我知道懒惰可能很棘手,如果元组的两个元素都被使用,
(filter p xs, filter (not . p) xs)
只会进行两次遍历。这是否与 Haskell 中列表的处理方式有关?
非常感谢!
这个问题没有非黑即白的答案。要剖析问题,请考虑以下代码:
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
运行时选项。使用不同的命令行选项执行不同的测试用例。第一个命令行选项定义谓词保留的数据百分比。第二个命令行选项在不同的测试之间进行选择。
测试区分两种情况:
- 延迟生成数据(第二个参数
partition
或mypartition
)。 - 数据已在内存中完全计算(第二个参数
partition-ds
或mypartition-ds
)。
分区的结果总是从左到右求值,即从包含谓词所对应的所有元素的列表开始。
在情况 1 partition
中,第一个结果列表的元素在输入列表的所有元素生成之前就被丢弃了。情况 1 特别好,如果谓词匹配很多元素,即第一个命令行参数很大。
在情况 2 中,partition
无法发挥此优势,因为所有元素都已在内存中。
对于mypartition
,在任何情况下,在计算第一个结果列表后,所有元素都保存在内存中,因为再次需要它们来计算第二个结果列表。因此,这两种情况之间没有太大区别。
看来,使用的内存越多,垃圾回收就越难。因此 partition
非常适合,如果谓词匹配许多元素并且使用惰性变体。
相反,如果谓词不匹配很多元素或所有元素都已在内存中,mypartition
表现更好,因为与 partition
相比,它的递归不处理对。
Whosebug 问题“Irrefutable pattern does not leak memory in recursion, but why?”可能会提供更多关于在 partition
.