我正在对最坏情况输入(反向排序列表)和随机输入的插入排序进行基准测试。
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)时间内处理反向输入。所以你的“最坏情况”实际上是写入算法的最佳情况,而不是预期的。