haskell - 分支预测对 Haskell 程序有多大影响?
问题描述
我在最坏情况输入(反向排序列表)和随机输入上对插入排序进行基准测试。
import Control.Monad
import Data.List
import System.Random
import Control.Exception
import Control.DeepSeq
import Criterion.Main
--- Sorting ---
insertionSort :: (Ord a) => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = x `insert` (sort xs)
--- Generators ---
worstCaseGen :: Int -> [Int]
worstCaseGen n = [n, n-1..1]
bestCaseGen :: Int -> [Int]
bestCaseGen n = [1..n]
randomGen :: Int -> StdGen -> [Int]
randomGen n = take n . randoms
--- Testing ---
main = do
gen <- newStdGen
randomList <- evaluate $ force $ randomGen 10000 gen
defaultMain [
bgroup "Insertion Sort" [ bench "worst" $ nf insertionSort (worstCaseGen 10000)
, bench "best" $ nf insertionSort (bestCaseGen 10000)
, bench "gen" $ nf last randomList
, bench "random" $ nf insertionSort randomList
]
]
虽然随机输入的性能应该与最坏情况输入的幅度大致相同,但实际上基准测试显示它慢了大约 20 倍。我的猜测是分支预测开始了,随机情况很难预测,因此变得更慢。这可能是真的吗?
如果有帮助,这是我的 .cabal:
executable BranchPrediction
main-is: Main.hs
build-depends: base >=4.12 && <4.13,
random,
criterion ==1.5.4.0,
deepseq ==1.4.4.0
default-language: Haskell2010
解决方案
你打电话sort
而不是insertionSort
在你的(假设是)递归案例中。这是一个运行优化的合并排序,它在 O(n) 时间内处理反向输入。因此,您的“最坏情况”实际上是所写算法的近乎最佳情况,而不是预期的。
推荐阅读
- javascript - 为什么从前端传递的 javascript Map() 对象为空?
- node.js - E11000 mongoDB 中多个唯一键的重复键错误
- python - 读取带有洗牌行的大型 csv 文件块以使用 ML 进行分类
- c# - Sonarqube 报告控制器操作的重复代码块
- c# - 如何从 MainWindow 调用 XAML 中的方法?
- python - 保存和加载 Sklearn 的 CalibratedClassifierCV 的正确方法
- python - csv 文件不会在 while 循环期间创建,仅在使用 csv.writer 执行之后
- c# - 超轻量级 | 弹出窗口的宽度和高度
- spring - 每次 Spring Retry 尝试更改参数值
- ruby - Ruby 代码覆盖率:SimpleCov + MiniTest?