在C中,如果我想将int除以2,x%2
应该运行得像(x%10)% 2
一样快,因为好的编译器只会查看最后一位。但是如何用无限精度的算术语言呢?无限精度整数:除以2
特别是在Haskell中,它会更快(或者它们会是相同的速度):even x
或even (quot x 10)
?
在C中,如果我想将int除以2,x%2
应该运行得像(x%10)% 2
一样快,因为好的编译器只会查看最后一位。但是如何用无限精度的算术语言呢?无限精度整数:除以2
特别是在Haskell中,它会更快(或者它们会是相同的速度):even x
或even (quot x 10)
?
好吧,我会咬:
import Control.DeepSeq
import Criterion.Main
import Data.Bits
import System.Random
lotsOfBigNumbers :: [Integer]
lotsOfBigNumbers = take 10000 $ randomRs (2^128, 2^132) (mkStdGen 42)
evenRem, evenBits :: Integer -> Bool
evenRem x = even (x `rem` 10)
evenBits x = (x .&. 1) == 0
remRem x = ((x `rem` 10) `rem` 2) == 0
main = do
deepseq lotsOfBigNumbers (return())
defaultMain
[ bench "even" $ nf (map even ) lotsOfBigNumbers
, bench "evenRem" $ nf (map evenRem) lotsOfBigNumbers
, bench "evenBits" $ nf (map evenBits) lotsOfBigNumbers
, bench "remRem" $ nf (map remRem ) lotsOfBigNumbers
]
而且结果:
sorghum:~/programming% ghc -O2 test && ./test
[1 of 1] Compiling Main (test.hs, test.o)
Linking test ...
warming up
estimating clock resolution...
mean is 1.920340 us (320001 iterations)
found 51108 outliers among 319999 samples (16.0%)
46741 (14.6%) low severe
4367 (1.4%) high severe
estimating cost of a clock call...
mean is 83.20445 ns (16 iterations)
found 4 outliers among 16 samples (25.0%)
2 (12.5%) low mild
2 (12.5%) high severe
benchmarking even
mean: 1.508542 ms, lb 1.503661 ms, ub 1.514950 ms, ci 0.950
std dev: 28.53574 us, lb 23.35796 us, ub 35.19769 us, ci 0.950
found 18 outliers among 100 samples (18.0%)
17 (17.0%) high severe
variance introduced by outliers: 11.371%
variance is moderately inflated by outliers
benchmarking evenRem
mean: 1.937735 ms, lb 1.930118 ms, ub 1.949699 ms, ci 0.950
std dev: 48.17240 us, lb 34.95334 us, ub 71.22055 us, ci 0.950
found 14 outliers among 100 samples (14.0%)
3 (3.0%) high mild
11 (11.0%) high severe
variance introduced by outliers: 18.989%
variance is moderately inflated by outliers
benchmarking evenBits
mean: 996.3537 us, lb 992.2839 us, ub 1.003864 ms, ci 0.950
std dev: 27.37875 us, lb 17.51923 us, ub 43.98499 us, ci 0.950
found 15 outliers among 100 samples (15.0%)
2 (2.0%) high mild
13 (13.0%) high severe
variance introduced by outliers: 21.905%
variance is moderately inflated by outliers
benchmarking remRem
mean: 1.925495 ms, lb 1.918590 ms, ub 1.935869 ms, ci 0.950
std dev: 43.00092 us, lb 31.67173 us, ub 57.83841 us, ci 0.950
found 13 outliers among 100 samples (13.0%)
13 (13.0%) high severe
variance introduced by outliers: 15.198%
variance is moderately inflated by outliers
结论:一个额外的费用rem
多一点,和.&.
费用少一点。
'evenBits x =(x。|。1)== 0' < - 应该是'。&。'。这使得这个比较快(〜20%)。但实际上,它应该是'evenBits x =(fromInteger x。&。(1 :: Int))== 0',因为'Integer'上的位操作并不是特别快。 –
@DanielFischer哎呀,这是一个糟糕的错误,谢谢指出! –
我注意到另一个,'evenquot x = even(x'''10)''检查第二个最低有效位是否是偶数。应该是“even(x'rem' 10)''。然后差别几乎消失了,因为''x'rem' 10''变成'S#i #',然后'even'使用'Int#'除法(在测试它是'S#'后)而且比GMP的调用速度快得多,所以'整数'除法+'内部'除法与“整数”除法几乎相同。 –
我不太确定'x%2'与C中的'(x%10)%2'一样快。如果编译器认识到'%10'部分不改变结果,那么它可能会被删除,但这是一种算术简化 - 与位摆动和数字表示无关,因此同样适用于任意精度整数。如果它没有被移除,那么它可能确实会首先计算余数w/10,这是通过屏蔽掉位来实现的。 – delnan
@delnan这是一个很公平的点,谢谢。我想我不是很严谨。 –