- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我写了量化函数exists
, forall
, 和 none
用于 Haskell 的内置 []
列表数据类型。在很多情况下,这些似乎比 Prelude
更有效。/Data.List
s any
和 all
.我天真地怀疑这种表现是由于any
和 all
使用 Θ(n) 折叠实现。由于我对 Haskell 比较陌生,我想我一定是弄错了,否则这种现象会有很好的理由。
来自 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)
forall
:
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
与默认优化级别性能相比,产生如此巨大的整体差异,也不是个别定制编写和库公式之间的优化有效性差异。许多高效的专业标准功能优化显然只有在明确启用时才会发挥作用。
RULES
pragma 或重新制定基本形式,以尝试利用已经培养的优化潜力。
最佳答案
我发现以各种方式重新实现 any
很有启发性:
import Prelude hiding (any)
import Criterion.Main
import Data.Foldable (foldMap)
import Data.Monoid
exists
:
exists :: (a -> Bool) -> [a] -> Bool
exists _ [] = False
exists pred (x : xs)
= if pred x
then True
else exists pred xs
(||)
的版本:
existsOr :: (a -> Bool) -> [a] -> Bool
existsOr _ [] = False
existsOr pred (x : xs) = pred x || existsOr pred xs
foldr
:
any :: (a -> Bool) -> [a] -> Bool
any pred = foldr ((||) . pred) False
foldr
和
Any
:
anyF :: (a -> Bool) -> [a] -> Bool
anyF pred = getAny . foldr (mappend . (Any . pred)) mempty
foldMap
和
Any
:
anyFM :: (a -> Bool) -> [a] -> Bool
anyFM pred = getAny . foldMap (Any . pred)
ghc -O0
的基准测试:
benchmarking exists
time 1.552 μs (1.504 μs .. 1.593 μs)
0.989 R² (0.983 R² .. 0.993 R²)
mean 1.482 μs (1.427 μs .. 1.545 μs)
std dev 196.1 ns (168.8 ns .. 229.2 ns)
variance introduced by outliers: 93% (severely inflated)
benchmarking existsOr
time 2.699 μs (2.616 μs .. 2.768 μs)
0.992 R² (0.988 R² .. 0.995 R²)
mean 2.629 μs (2.554 μs .. 2.704 μs)
std dev 277.8 ns (235.8 ns .. 351.1 ns)
variance introduced by outliers: 89% (severely inflated)
benchmarking any
time 5.551 μs (5.354 μs .. 5.777 μs)
0.990 R² (0.986 R² .. 0.995 R²)
mean 5.553 μs (5.395 μs .. 5.750 μs)
std dev 584.2 ns (447.5 ns .. 835.5 ns)
variance introduced by outliers: 88% (severely inflated)
benchmarking anyF
time 7.330 μs (7.081 μs .. 7.612 μs)
0.988 R² (0.982 R² .. 0.994 R²)
mean 7.502 μs (7.272 μs .. 7.762 μs)
std dev 848.2 ns (712.6 ns .. 1.022 μs)
variance introduced by outliers: 89% (severely inflated)
benchmarking anyFM
time 5.668 μs (5.451 μs .. 6.008 μs)
0.987 R² (0.975 R² .. 0.996 R²)
mean 5.807 μs (5.659 μs .. 5.975 μs)
std dev 542.5 ns (446.4 ns .. 721.8 ns)
variance introduced by outliers: 86% (severely inflated)
exists
) 确实是最快的,而
foldr
版本则相当慢。
ghc -O2
,您的版本 (
exists
) 是最慢的,并且所有其他函数的速度几乎相同:
benchmarking exists
time 753.5 ns (725.4 ns .. 779.9 ns)
0.990 R² (0.986 R² .. 0.995 R²)
mean 762.4 ns (737.0 ns .. 787.0 ns)
std dev 82.47 ns (66.79 ns .. 105.1 ns)
variance introduced by outliers: 91% (severely inflated)
benchmarking existsOr
time 491.5 ns (478.2 ns .. 503.2 ns)
0.994 R² (0.992 R² .. 0.996 R²)
mean 494.5 ns (481.1 ns .. 512.9 ns)
std dev 54.97 ns (42.54 ns .. 80.34 ns)
variance introduced by outliers: 92% (severely inflated)
benchmarking any
time 461.2 ns (442.0 ns .. 479.7 ns)
0.989 R² (0.985 R² .. 0.993 R²)
mean 456.0 ns (439.3 ns .. 476.3 ns)
std dev 60.04 ns (47.27 ns .. 89.47 ns)
variance introduced by outliers: 94% (severely inflated)
benchmarking anyF
time 436.9 ns (415.8 ns .. 461.0 ns)
0.978 R² (0.967 R² .. 0.988 R²)
mean 450.8 ns (430.1 ns .. 472.6 ns)
std dev 70.64 ns (57.04 ns .. 85.92 ns)
variance introduced by outliers: 96% (severely inflated)
benchmarking anyFM
time 438.9 ns (426.9 ns .. 449.5 ns)
0.993 R² (0.989 R² .. 0.996 R²)
mean 435.8 ns (421.4 ns .. 447.6 ns)
std dev 45.32 ns (36.73 ns .. 58.74 ns)
variance introduced by outliers: 90% (severely inflated)
ghc -O2 -ddump-simpl
),就会发现不再有
foldr
s(使用
-O0
,所有内容都还在那里,包括
fold
s)。
-O0
),因为它更简单(因为潜在的代价是不那么通用)。优化后的库代码比您的版本更快,因为它是以编译器识别其优化潜力的方式编写的。 (诚然,这有点猜测)
关于performance - `any`/`all` 的 Haskell/GHC 性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42248592/
runghc 和 ghc 有什么区别? 我运行了一个简短的程序,似乎可以用两者编译,除了我用 runghc 得到了以下内容,但不是普通的 ghc: error: Variable not in sco
如果 friend 想要运行我的 Haskell 二进制文件,他是否必须先安装 Haskell,还是可以立即自行运行二进制文件? Mac、Windows 和 Linux 上的答案相同吗? 最佳答案 G
ffunction glMultiDrawElements 需要一个指向指针的指针作为其参数之一。如何从 StorableArray Int a 获取 Ptr(Ptr a) ? 最佳答案 您需要先将索
module Has (r,p,s) where import Prelude ((==),Bool(..),otherwise,(||),Eq) import qualified Data.List
我已经构建了 ghc-HEAD,我想尝试构建所有的 stackage lts 或 nightly 看看它能做多少。 无论我说什么都无法说服 stack 使用我的新 ghc 构建任何东西。我尝试设置如下
我正在使用 Emacs (24.3.1) 在 haskell-mode 中与 ghc-mod 一起使用 Haskell。 现在除了一件烦人的事情外,一切都很好: GHC 信息缓冲区中的每个输出仅包含第
为什么升级到 OSX Mavericks 后我的 GHC 7.6.3 不能工作? 最佳答案 花了很长时间才弄清楚如何同时使用 OSX 10.9 和 GHC 7.6.3,这里有一些技巧可以帮助您重新构建
我有一个带有 cabal 文件的主要 Haskell 可执行程序。在那里,我指定 ghc-options . 这个可执行文件链接到野外的其他库。请问ghc-options忽略这些库的 cabal 文件
我有一个使用 -Wall 编译的库,并且我有一个使用 -Wall -Wno-incomplete-patterns 的测试套件 当我使用 stack ghci --test 启动 ghci 时,ghc
我正在尝试使用以下脚本在 Windows 上安装 GHC(并将 ghc 放在路径中),但是当我尝试运行 ghci --version 时它失败了。我认为脚本有问题。 install: - ps:
我在 $HOME 中安装了 ghc-7.2.2 unknown linux tar.bz2在archlinux上。 在使用 cabal-dev 成功安装多个软件包后,尝试安装例如。我得到的解析数字、文
想法 我正在写 DSL ,编译为 Haskell。 该语言的用户可以定义自己的不可变数据结构和相关函数。关联函数是指属于数据结构的函数。 例如,用户可以编写(在“pythonic”伪代码中): dat
(我的问题是在没有 haskell-platform、ghc、cabal 等的情况下分发二进制文件) 我需要部署一个结构良好的 haskell 应用程序(Yesod 脚手架),但我有磁盘空间限制。 G
我试图将 Cygwin 安装程序指向 http://haskell.org/ghc/cygwin ,但安装程序无法找到 setup.ini.sig。如果可能的话,我该如何编辑我的 .bashrc 以引
我有一个现有的 Haskell 函数,它使用 GHC API 从模块中动态加载已编译的代码。它基于博客文章中的代码 Dynamic Compilation and Loading of Modules
我使用:Ubuntu 上的 GHC 7.6.3(通过 apt-get install haskell-platform) 从当前存储库安装它。 正在尝试安装ghc-mod ,因为我的 ide 插件需要
AFAIK,有两种方法可以在 Haskell 中获取用于调试的调用堆栈: 添加 HasCallStack代码中的约束 使用 ghc -prof -fprof-auto-top 编译代码 我的测试代码:
我想用 64 位 GHC 构建 32 位 DLL。这是最小的例子。 测试.hs {-# LANGUAGE ForeignFunctionInterface #-} module Test where
ghc-gc-tune 0.2.1 可以与 ghc 7.4.1 一起使用吗?看来 ghc-gc-tune 已经有一段时间没有更新了,可能只适用于 ghc 6.x?我找不到任何可靠的信息。 我收到以下错
语言扩展 ExplicitForall 使得使用 forall 绑定(bind)类型变量成为可能但不是必需的。 例如,下面的程序可以编译 {-# LANGUAGE ExplicitForAll #-}
我是一名优秀的程序员,十分优秀!