performance - 为什么 "better"数字列表功能较慢？

Question

我在玩 Project Euler #34，我写了这些函数:

import Data.Time.Clock.POSIX
import Data.Char

digits :: (Integral a) => a -> [Int]
digits x
    | x < 10 = [fromIntegral x]
    | otherwise = let (q, r) = x `quotRem` 10 in (fromIntegral r) : (digits q)

digitsByShow :: (Integral a, Show a) => a -> [Int]
digitsByShow = map (\x -> ord x - ord '0') . show

我认为肯定 digits 必须是更快的，因为我们不转换为字符串。我大错特错了。我通过 pe034 运行了两个版本:

pe034 digitFunc = sum $ filter sumFactDigit [3..2540160]
    where
        sumFactDigit :: Int -> Bool
        sumFactDigit n = n == (sum $ map sFact $ digitFunc n)
        sFact :: Int -> Int
        sFact n
            | n == 0 = 1
            | n == 1 = 1
            | n == 2 = 2
            | n == 3 = 6
            | n == 4 = 24
            | n == 5 = 120
            | n == 6 = 720
            | n == 7 = 5040
            | n == 8 = 40320
            | n == 9 = 362880

main = do
    begin <- getPOSIXTime
    print $ pe034 digitsByShow -- or digits
    end <- getPOSIXTime
    print $ end - begin

使用 ghc -O 编译后，digits 始终需要 0.5 秒，而 digitsByShow 始终需要 0.3 秒。为什么会这样？为什么留在整数运算中的函数较慢，而进入字符串比较的函数更快？

我问这个是因为我来自 Java 和类似语言的编程，其中生成数字的 %10 技巧比“转换为字符串”方法快得多。我无法理解转换为字符串可能会更快这一事实。

Answer 1

这是我能想到的最好的。

digitsV2 :: (Integral a) => a -> [Int]
digitsV2 n = go n []
    where
      go x xs
          | x < 10    = fromIntegral x : xs
          | otherwise = case quotRem x 10 of
                  (q,r) -> go q (fromIntegral r : xs)

当使用 -O2 编译并使用 Criterion 测试时

digits 运行时间为 470.4 毫秒

digitsByShow 运行时间为 421.8 毫秒

digitsV2 运行时间为 258.0 毫秒

结果可能不同

编辑: 我不确定为什么构建这样的列表会有如此大的帮助。 但是您可以通过严格评估 quotRem x 10

来提高代码速度

你可以用 BangPatterns 做到这一点

| otherwise = let !(q, r) = x `quotRem` 10 in (fromIntegral r) : (digits q)

或带壳

| otherwise = case quotRem x 10 of
                (q,r) -> fromIntegral r : digits q

这样做会将 digits 降低到 323.5 毫秒

编辑:不使用标准的时间

位数 = 464.3 毫秒

digitsStrict = 328.2 毫秒

digitsByShow = 259.2 毫秒

digitV2 = 252.5 毫秒

注意:标准包衡量软件性能。