为什么`(map digitalToInt) .show`这么快？
https://stackoverflow.com/questions/4841078
-
27-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
转换非负数 Integer 其数字列表通常是这样完成的：
import Data.Char
digits :: Integer -> [Int]
digits = (map digitToInt) . show
我试图找到一种更直接的方法来执行任务，而不涉及字符串转换，但我无法想出更快的方法。
到目前为止我一直在尝试的事情：
基线：
digits :: Int -> [Int]
digits = (map digitToInt) . show
从 StackOverflow 上的另一个问题得到这个：
digits2 :: Int -> [Int]
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10)
尝试推出我自己的：
digits3 :: Int -> [Int]
digits3 = reverse . revDigits3
revDigits3 :: Int -> [Int]
revDigits3 n = case divMod n 10 of
(0, digit) -> [digit]
(rest, digit) -> digit:(revDigits3 rest)
这个的灵感来自于 showInt 在 Numeric:
digits4 n0 = go n0 [] where
go n cs
| n < 10 = n:cs
| otherwise = go q (r:cs)
where
(q,r) = n `quotRem` 10
现在是基准。笔记：我强制使用评估 filter.
λ>:set +s
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000]
2400000
(1.58 secs, 771212628 bytes)
这是参考。现在为 digits2:
λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000]
2400000
(5.47 secs, 1256170448 bytes)
那是 3.46 时间更长。
λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000]
2400000
(7.74 secs, 1365486528 bytes)
digits3 是 4.89 时间变慢。只是为了好玩，我尝试仅使用 revDigits3 并避免 reverse.
λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000]
2400000
(8.28 secs, 1277538760 bytes)
奇怪的是，这甚至更慢， 5.24 慢几倍。
最后一个：
λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000]
2400000
(16.48 secs, 1779445968 bytes)
这是 10.43 时间变慢。
我的印象是，仅使用算术和缺点会优于涉及字符串转换的任何内容。显然，有些东西我无法理解。
那么有什么技巧呢？为什么是 digits 很快？
我正在使用 GHC 6.12.3。
解决方案
鉴于我还无法添加评论，我将做更多工作并分析所有评论。我把分析放在最上面；不过，相关数据如下。（笔记：所有这些也在 6.12.3 中完成 - 还没有 GHC 7 魔法。）
分析：
版本1： show 对于整数来说非常好，尤其是像我们这样短的整数。实际上，在 GHC 中制作字符串往往是不错的；然而，读取字符串并将大字符串写入文件（或标准输出，尽管您不想这样做）是您的代码绝对可以抓取的地方。我怀疑为什么这么快背后的很多细节都是由于 Ints 显示中的巧妙优化。
版本2： 编译时，这是其中最慢的一个。一些问题：相反，它的论证是严格的。这意味着在计算下一个元素时，您无法从对列表的第一部分执行计算中受益；你必须计算它们全部，翻转它们，然后对列表的元素进行计算（即 (`mod` 10) ）。虽然这看起来很小，但它可能会导致更大的内存使用量（请注意此处分配的 5GB 堆内存）和更慢的计算速度。（长话短说：不要使用反向。）
版本3： 还记得我刚才说过不要使用反向吗？事实证明，如果你把它拿出来，总执行时间会下降到 1.79 秒——仅比基线慢一点。这里唯一的问题是，当你深入了解数字时，你会以错误的方向构建列表的主干（本质上，你是通过递归“进入”列表，而不是“进入”列表）列表）。
版本 4： 这是一个非常巧妙的实现。您可以从以下几项好处中受益：其一，quotRem 应该使用欧几里得算法，该算法的较大参数是对数的。（也许它更快，但我不相信有什么比欧几里得更快的常数因子。）此外，您可以像上次讨论的那样进入列表，这样您就不必在处理任何列表时解决任何列表重击问题。 go - 当您返回解析列表时，列表已经完全构建完毕。如您所见，性能由此受益。
这段代码可能是 GHCi 中最慢的，因为 GHC 中使用 -O3 标志执行的许多优化都是为了使列表更快，而 GHCi 不会做任何事情。
教训： 以正确的方式将 cons 放入列表中，注意可能减慢计算速度的中间严格性，并做一些跑腿工作来查看代码性能的细粒度统计数据。还可以使用 -O3 标志进行编译：每当你不这样做时，所有那些花费大量时间让 GHC 超快的人都会对你投以大眼睛。
数据：
我只是将所有四个函数粘贴到一个 .hs 文件中，然后根据需要进行更改以反映正在使用的函数。另外，我将限制提高到 5e6，因为在某些情况下，编译的代码在 1e6 上运行时间不到半秒，这可能会导致我们正在进行的测量出现粒度问题。
编译器选项：使用 ghc --make -O3 [文件名].hs 让 GHC 做一些优化。我们将使用以下命令将统计数据转储到标准错误 数字+RTS -sstderr.
在digits1的情况下，转储到-sstderr给我们提供如下所示的输出：
digits1 +RTS -sstderr
12000000
2,885,827,628 bytes allocated in the heap
446,080 bytes copied during GC
3,224 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 5504 collections, 0 parallel, 0.06s, 0.03s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.61s ( 1.66s elapsed)
GC time 0.06s ( 0.03s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.67s ( 1.69s elapsed)
%GC time 3.7% (1.5% elapsed)
Alloc rate 1,795,998,050 bytes per MUT second
Productivity 96.3% of total user, 95.2% of total elapsed
这里有三个关键统计数据：
- 使用中的总内存：只有 1MB 意味着这个版本非常节省空间。
- 总时间：1.61s 现在没有任何意义，但我们将看看它与其他实现相比如何。
- 生产率：这只是 100% 减去垃圾收集；因为我们已经完成了 96.3%，这意味着我们没有创建大量留在内存中的对象。
好吧，让我们继续讨论版本 2。
digits2 +RTS -sstderr
12000000
5,512,869,824 bytes allocated in the heap
1,312,416 bytes copied during GC
3,336 bytes maximum residency (1 sample(s))
13,048 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 10515 collections, 0 parallel, 0.06s, 0.04s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 3.20s ( 3.25s elapsed)
GC time 0.06s ( 0.04s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 3.26s ( 3.29s elapsed)
%GC time 1.9% (1.2% elapsed)
Alloc rate 1,723,838,984 bytes per MUT second
Productivity 98.1% of total user, 97.1% of total elapsed
好吧，我们看到了一个有趣的模式。
- 使用相同数量的内存。这意味着这是一个非常好的实现，尽管这可能意味着我们需要测试更高的样本输入以查看是否可以找到差异。
- 需要两倍的时间。我们稍后会回过头来猜测为什么会这样。
- 它实际上稍微更有效率，但考虑到 GC 并不是这两个程序的很大一部分，这对我们没有任何重大帮助。
版本3：
digits3 +RTS -sstderr
12000000
3,231,154,752 bytes allocated in the heap
832,724 bytes copied during GC
3,292 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 6163 collections, 0 parallel, 0.02s, 0.02s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 2.09s ( 2.08s elapsed)
GC time 0.02s ( 0.02s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 2.11s ( 2.10s elapsed)
%GC time 0.7% (1.0% elapsed)
Alloc rate 1,545,701,615 bytes per MUT second
Productivity 99.3% of total user, 99.3% of total elapsed
好吧，我们看到了一些奇怪的模式。
- 我们的总内存使用量仍为 1MB。所以我们没有遇到任何内存效率低下的问题，这很好。
- 我们还没有完全达到“digits1”，但我们已经很容易击败“digits2”了。
- GC 很少。（请记住，任何超过 95% 的生产率都非常好，因此我们在这里并没有真正处理任何太重要的事情。）
最后是版本 4：
digits4 +RTS -sstderr
12000000
1,347,856,636 bytes allocated in the heap
270,692 bytes copied during GC
3,180 bytes maximum residency (1 sample(s))
12,100 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Generation 0: 2570 collections, 0 parallel, 0.00s, 0.01s elapsed
Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.09s ( 1.08s elapsed)
GC time 0.00s ( 0.01s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 1.09s ( 1.09s elapsed)
%GC time 0.0% (0.8% elapsed)
Alloc rate 1,234,293,036 bytes per MUT second
Productivity 100.0% of total user, 100.5% of total elapsed
哇扎！让我们来分解一下：
- 总共仍然是 1MB。这几乎肯定是这些实现的一个特性，因为它们在 5e5 和 5e7 的输入上保持在 1MB。如果你愿意的话，这是懒惰的证明。
- 我们削减了大约 32% 的原始时间，这非常令人印象深刻。
- 我怀疑这里的百分比反映了 -sstderr 监控的粒度，而不是对超光速粒子的任何计算。
其他提示
回答“为什么物权而不是国防部？”在评论。当与正值rem x y === mod x y处理这样音符的唯一要考虑的是性能：
> import Test.QuickCheck
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y)
那么，什么是性能？除非你有一个很好的理由不要（和懒惰是不是一个很好的理由，也不是不知道标准），然后使用一个很好的基准测试工具，我用标准：
$ cat useRem.hs
import Criterion
import Criterion.Main
list :: [Integer]
list = [1..10000]
main = defaultMain
[ bench "mod" (nf (map (`mod` 7)) list)
, bench "rem" (nf (map (`rem` 7)) list)
]
运行该节目rem是可测量地优于mod（与-O2编译）：
$ ./useRem
...
benchmarking mod
...
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950
benchmarking rem
...
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950
