我为Haskell的内置列表数据类型“[]”编写了量化函数“exists”,“forall”和“none”。在多个场合中,它们似乎比“Prelude / Data.List”的“any”和“all”更有效。我天真地认为,这种性能是因为使用Θ(n)折叠实现了“any”和“all”。由于我对Haskell相对较新,我认为我一定是错的,或者存在一个好的原因解释这种现象。
来自“Data.Foldable”:
来自“Data.Foldable”:
-- | Determines whether any element of the structure satisfies the predicate.
any :: Foldable t => (a -> Bool) -> t a -> Bool
any p = getAny #. foldMap (Any #. p)
-- | Determines whether all elements of the structure satisfy the predicate.
all :: Foldable t => (a -> Bool) -> t a -> Bool
all p = getAll #. foldMap (All #. p)
我的实现:
exists :: (a -> Bool) -> [a] -> Bool
exists _ [] = False
exists pred (x : xs) | pred x = True
| otherwise = exists pred xs
并且
forall pred = not . exists (not . pred)
none pred = not . exists pred = forall (not . pred)
消除布尔反转:
forall, none :: (a -> Bool) -> [a] -> Bool
forall _ [] = True
forall pred (x : xs) | pred x = forall pred xs
| otherwise = False
none _ [] = True
none pred (x : xs) | pred x = False
| otherwise = none pred xs
all
:
time 327.8 μs (322.4 μs .. 333.0 μs)
0.997 R² (0.996 R² .. 0.998 R²)
mean 328.7 μs (324.1 μs .. 334.2 μs)
std dev 16.95 μs (14.63 μs .. 22.02 μs)
以及 对于所有
:
time 113.2 μs (111.2 μs .. 115.0 μs)
0.997 R² (0.996 R² .. 0.998 R²)
mean 112.0 μs (110.0 μs .. 113.9 μs)
std dev 6.333 μs (5.127 μs .. 7.896 μs)
使用准则nf
来衡量性能。
正如预期的那样,我没有重新发明折叠方法,但是低估了编译器标志,并且天真地认为与默认优化级别性能相比,-O2
不会产生如此激烈的整体差异,也没有预料到单独定制和库式表述之间的优化效果差异。许多高度有效的专业标准函数优化显然只有在明确启用时才会启动。
Haskell标签信息中的“性能”部分强调了测试代码效率时优化级别编译器标志的重要性。通常建议信任库函数实现的复杂性,而不是重新编写RULES
规范或重新构思基本形式,而是尝试利用已经培养的优化潜力。
Foldable
函数中缺乏内联所致。所有你的函数都等价于某个f
、z
的foldr f z
,而List.foldr
即使在Foldable.foldr
不行时也可能进行内联。 - user2407038-O
。它的编译速度比-O2
快得多,而且它生成的代码通常已经足够好了。 - dfeuer