なぜ `(map digitToInt) なのか。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 非常に高速？
GHC6.12.3を使用しています。
解決
まだコメントを追加できないので、もう少し作業を進めて、すべてのコメントを分析するだけです。私は分析を一番上に置きます。ただし、関連するデータは以下のとおりです。（注記：これはすべて 6.12.3 でも行われます - GHC 7 マジックはまだありません。)
分析：
バージョン 1: show は int 、特に今回のような短い int に非常に適しています。実際、GHC では文字列の作成が適切になる傾向があります。ただし、文字列の読み取りとファイル (または、それは望ましくありませんが stdout) への大きな文字列の書き込みは、コードが完全にクロールできる場所です。これが非常に速い理由の詳細の多くは、Int のショー内の賢明な最適化によるものではないかと思います。
バージョン 2: これは、コンパイル時に最も遅いものでした。いくつかの問題：reverse はその議論において厳密です。これが意味するのは、次の要素を計算している間にリストの最初の部分で計算を実行してもメリットが得られないということです。それらをすべて計算し、反転してから、リストの要素に対して計算 (つまり、 (`mod` 10) ) を実行する必要があります。これは小さいように思えるかもしれませんが、メモリ使用量が増加し (ここでも 5 GB のヒープ メモリが割り当てられていることに注意してください)、計算が遅くなる可能性があります。(長い話を短くすると:逆は使用しないでください。)
バージョン 3: リバースを使用しないでくださいと言ったことを覚えていますか?これを取り除くと、合計実行時間は 1.79 秒に低下し、ベースラインよりもわずかに遅いことがわかりました。ここでの唯一の問題は、数値を深く掘り下げていくと、間違った方向にリストの背骨を構築していることです (本質的に、リストを「上に」コンスするのではなく、再帰でリストを「中へ」コンスしているのです)リスト）。
バージョン 4: これは非常に賢い実装です。次のような優れたメリットが得られます。まず、quotRem は、より大きな引数で対数となるユークリッド アルゴリズムを使用する必要があります。(もしかしたら速いかもしれませんが、一定の係数以上に Euclid より速いものはないと思います。) さらに、前回説明したようにリストに cons を適用するため、リストのサンクを解決する必要がありません。 go - リストを解析するために戻ったときには、リストはすでに完全に構築されています。ご覧のとおり、これによりパフォーマンスが向上します。
このコードはおそらく GHCi で最も遅いものでした。これは、GHC では -O3 フラグを使用して実行される最適化の多くがリストの高速化を処理するのに対し、GHCi ではそのような処理が行われないためです。
教訓: 短所をリストに正しく追加し、計算速度を低下させる可能性がある中間の厳密性を監視し、コードのパフォーマンスの詳細な統計を調べるための下調べを行います。-O3 フラグを使用してコンパイルすることもできます。そうしないと、GHC を超高速で作成するために多くの時間を費やしたすべての人々が、大きな子犬のような目であなたを見つめることになります。
データ：
4 つの関数をすべて取り出して 1 つの .hs ファイルに貼り付け、使用中の関数を反映するために必要に応じて変更しました。また、制限を 5e6 まで引き上げました。場合によっては、コンパイルされたコードが 1e6 で 0.5 秒未満で実行され、これにより、実行している測定に粒度の問題が発生し始める可能性があるためです。
コンパイラ オプション:使用 ghc --make -O3 [ファイル名].hs GHCに最適化をしてもらうためです。次を使用して統計を標準エラーにダンプします。 桁数 +RTS -sstderr.
-sstderr にダンプすると、digital1 の場合、次のような出力が得られます。
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
ここには 3 つの重要な統計があります。
- 使用中の合計メモリ:わずか 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
さて、興味深いパターンが見えてきました。
- 使用されるメモリ量は同じです。これは、これがかなり優れた実装であることを意味しますが、違いを見つけることができるかどうかを確認するには、より高いサンプル入力でテストする必要があることを意味する可能性があります。
- 2倍の時間がかかります。なぜこれがそうなのかについては、後でいくつかの推測に戻ります。
- 実際には生産性がわずかに向上しますが、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 です。したがって、メモリ効率の悪い問題には遭遇していません。これは良いことです。
- 桁 1 にはまだ達していませんが、桁 2 には簡単に勝てます。
- 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 のモニタリングの粒度を反映しているのではないかと思います。
他のヒント
「なぜmodの代わりにレム？」という質問に答えます。コメントで。正の値を扱う場合 rem x y === mod x y したがって、考慮すべき点はパフォーマンスだけです。
> import Test.QuickCheck
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y)
それで、パフォーマンスは何ですか？よほどの理由がない限り (怠惰であることも、Criterion を知らないことも理由にはなりません)、優れたベンチマーク ツールを使用しない限り、私は Criterion を使用しました。
$ 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
