爲什麼`（地圖digitToInt）。表演`是如此之快？

Question

將非負Integer其數字列表的通常做法是這樣的：

import Data.Char 

digits :: Integer -> [Int] 
digits = (map digitToInt) . show 

我試圖找到一種更直接的方式來執行任務，不涉及一個字符串轉換，但我不能想出更快的東西。

事情我一直在努力，到目前爲止：

基線：

digits :: Int -> [Int] 
digits = (map digitToInt) . show 

得到這個一個來自另一個問題在計算器上：

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。

Answer 1

鑑於我不能添加評論，我會做更多的工作，並分析所有這些。我將分析置於頂端;但是，相關數據如下。 （注意：所有這些都是在6.12.3中完成的 - 沒有GHC 7的魔法。）

---

分析：

版本1：展是整數相當不錯的，特別是短，我們有。製作琴絃在GHC中實際上很體面;然而，讀取字符串並將大字符串寫入文件（或stdout，儘管您不想這樣做）是您的代碼絕對可以抓取的位置。我猜想很多背後的細節背後的細節都是因爲Ints展會內的巧妙優化。

版本2：這是編譯時最慢的一組。一些問題：反向在其論據中是嚴格的。這意味着當你計算下一個元素時，你不能從列表的第一部分執行計算;你必須全部計算它們，翻轉它們，然後對列表中的元素進行計算（即（mod'10））。雖然這可能看起來很小，但它可能會導致更大的內存使用量（請注意這裏分配的5GB堆內存）以及較慢的計算。 （長話短說：不要使用反向。）

版本3：請記住我剛纔說的不要使用反向？結果，如果你把它拿出來，這個總執行時間會下降到1.79s--幾乎比基線慢。這裏唯一的問題是，當你更深入地瞭解數字時，你會在錯誤的方向上建立列表的脊柱（本質上，你正在考慮將遞歸列入「列表」，而不是「列表）。

版本4：這是一個非常聰明的實現。您可以從幾件好事中受益：例如，quotRem應該使用歐幾里德算法，該算法在其較大的參數中是對數的。 （也許速度更快，但我不相信比歐幾里得更快的東西不僅僅是一個恆定的因素）。此外，你上一次討論的時候會列出名單，這樣你就不必像你一樣解決任何列表中的連詞去 - 當你回來解析它時，這個列表已經完全構建完成。正如你所看到的，性能可以從這方面受益。

此代碼可能是在GHCI最慢的，因爲很多與-O3標誌GHC處理製作名單更快，而GHCI不會做任何的所執行的優化。

經驗教訓：以正確的方式放在一個列表中，注意可能會減慢計算速度的中間嚴格性，並在查看代碼性能的細粒度統計信息時進行一些操作。也用-O3標誌進行編譯：如果你不這樣做，所有那些花費大量時間讓GHC超快速運行的人都會在你身上看到大大小小的眼睛。

---

數據：

我只是把所有四個功能，把它們貼到一個名爲.hs文件，然後根據需要改變以反映在使用該功能。另外，我將你的極限提高到了5e6，因爲在某些情況下，編譯後的代碼在1e6時間內運行時間不到半秒，這可能導致我們正在測量的粒度問題。

編譯選項：使用ghc --make -O3 [filename] .hs讓GHC做一些優化。我們會使用digits + RTS -sstderr將統計信息轉儲到標準錯誤。

轉儲到-sstderr給我們輸出看起來像這樣，在digits1的情況下：

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 

這裏有三個關鍵的統計信息：

1. 使用的總內存：只有1MB手段這個版本非常節省空間。
2. 總時間：1.61s現在沒有任何意義，但我們會看到它與其他實現的不同之處。
3. 生產力：這只是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 

好的，所以我們看到了一個有趣的模式。

1. 相同的內存使用量。這意味着這是一個非常好的實現，儘管這可能意味着我們需要測試更高的樣本輸入以查看是否可以找到差異。
2. 需要兩倍的時間。我們將回到一些猜測，爲什麼這是後來。
3. 實際上它的效率稍高一點，但考慮到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 

好吧，讓我們看到了一些奇怪的圖案。

1. 我們仍在使用1MB總內存。所以我們沒有打任何記憶 - 效率低下，這很好。
2. 我們並不完全處於數位1，但我們已經有了位數2輕鬆打敗了。
3. 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 

Wowza！讓我們來分解它：

1. 我們仍然總共1MB。這幾乎肯定是這些實現的一個特性，因爲它們在5e5和5e7的輸入上保持在1MB。如果你願意的話，可以證明懶惰。
2. 我們截斷了原來的約32％，這是非常令人印象深刻的。
3. 我懷疑這裏的百分比反映了-sstderr監測的粒度，而不是任何超光速粒子的計算。

Answer 2

回答「爲什麼REM而不是MOD？」在評論中。當正值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