11

SHA512 ハッシュの 16 進数表現を提供できるようにする必要がありました。よく調べていなかっただけかもしれませんが、Hackage でそれを行うための関数を見つけることができました。そこで、 を使って実装を書きましたunfoldrN。私の目的には間違いなく十分に高速ですが、より高速なアプローチを誰かが知っているかどうか疑問に思っています。

実装を Gist として Github に掲載しました: https://gist.github.com/2356925。Numeric.showHexこのファイルには、QuickCheck テストと基準ベンチマークに基づく簡単な実装も含まれています。シンプルバージョンとバージョンの現在の結果は次のunfoldrNとおりです。

benchmarking simple
mean: 4.677296 ms, lb 4.656011 ms, ub 4.696684 ms, ci 0.950
std dev: 104.2791 us, lb 87.77023 us, ub 128.1627 us, ci 0.950
found 5 outliers among 100 samples (5.0%)
  4 (4.0%) low mild
variance introduced by outliers: 15.195%
variance is moderately inflated by outliers

benchmarking unfoldrN_MS1
mean: 370.0101 us, lb 365.9819 us, ub 373.8619 us, ci 0.950
std dev: 20.17016 us, lb 16.92772 us, ub 24.08982 us, ci 0.950
found 14 outliers among 100 samples (14.0%)
  7 (7.0%) low mild
  7 (7.0%) high mild
variance introduced by outliers: 52.467%
variance is severely inflated by outliers

誰かがそれを改善することに挑戦したいですか？

4

3 に答える 3

8

レベルを下げて、

import Data.ByteString.Internal
import Foreign.Ptr
import Foreign.Storable
import qualified Data.ByteString as B
import Data.ByteString.Unsafe
import Data.Bits
import Data.Word

maxLen :: Int
maxLen = maxBound `quot` 2

hexDig :: Word8 -> Word8
hexDig d
    | d < 10    = d + 48
    | otherwise = d + 87

toHex :: ByteString -> ByteString
toHex bs
    | len > maxLen = error "too long to convert"
    | otherwise    = unsafeCreate nl (go 0)
      where
        len = B.length bs
        nl  = 2*len
        go i p
            | i == len  = return ()
            | otherwise = case unsafeIndex bs i of
                            w -> do poke p (hexDig $ w `shiftR` 4)
                                    poke (p `plusPtr` 1) (hexDig $ w .&. 0xF)
                                    go (i+1) (p `plusPtr` 2)

ボックスの変換時間をさらに約 3.5 倍短縮できました。もう少しsample長くして(25000)、

benchmarking simple
mean: 13.76532 ms, lb 13.64184 ms, ub 13.88680 ms, ci 0.950
std dev: 633.2413 us, lb 582.6342 us, ub 687.9701 us, ci 0.950
variance introduced by outliers: 44.438%
variance is moderately inflated by outliers

benchmarking unfoldrN_MS1
mean: 430.5705 us, lb 424.9206 us, ub 438.5689 us, ci 0.950
std dev: 33.85429 us, lb 26.25623 us, ub 45.74915 us, ci 0.950
found 4 outliers among 100 samples (4.0%)
  3 (3.0%) high mild
  1 (1.0%) high severe
variance introduced by outliers: 69.726%
variance is severely inflated by outliers

benchmarking LowHex
mean: 123.6000 us, lb 123.0551 us, ub 124.7084 us, ci 0.950
std dev: 3.837497 us, lb 1.869370 us, ub 6.470112 us, ci 0.950
found 6 outliers among 100 samples (6.0%)
  4 (4.0%) high mild
  2 (2.0%) high severe
variance introduced by outliers: 25.818%
variance is moderately inflated by outliers

オリジナルの 500 ロングsampleの場合、

benchmarking simple
mean: 2.603306 ms, lb 2.583054 ms, ub 2.629212 ms, ci 0.950
std dev: 116.5341 us, lb 81.61409 us, ub 191.3293 us, ci 0.950
found 7 outliers among 100 samples (7.0%)
  2 (2.0%) low severe
  3 (3.0%) low mild
  1 (1.0%) high severe
variance introduced by outliers: 42.490%
variance is moderately inflated by outliers

benchmarking unfoldrN_MS1
mean: 83.19349 us, lb 82.88474 us, ub 83.58283 us, ci 0.950
std dev: 1.771460 us, lb 1.486104 us, ub 2.174729 us, ci 0.950
found 14 outliers among 100 samples (14.0%)
  12 (12.0%) high mild
  2 (2.0%) high severe
variance introduced by outliers: 14.225%
variance is moderately inflated by outliers

benchmarking LowHex
mean: 24.50564 us, lb 24.41683 us, ub 24.61241 us, ci 0.950
std dev: 497.1908 ns, lb 415.6366 ns, ub 609.7594 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
  5 (5.0%) high mild
variance introduced by outliers: 13.256%
variance is moderately inflated by outliers
于 2012-04-11T09:55:57.477 に答える
6

探している関数Data.ByteString.Builder.byteStringHex(または Lazy ByteStrings のツイン関数) は、新しいバイト文字列ビルダーによって提供されます。ベンチマークを拡張したところ、私のマシンで次の結果が得られました。

benchmarking size 5000/simple
mean: 2.469847 ms, lb 2.440422 ms, ub 2.522850 ms, ci 0.950
std dev: 196.5903 us, lb 116.8811 us, ub 318.4720 us, ci 0.950
found 16 outliers among 100 samples (16.0%)
  3 (3.0%) low severe
  2 (2.0%) low mild
  10 (10.0%) high severe
variance introduced by outliers: 70.721%
variance is severely inflated by outliers

benchmarking size 5000/unfoldrN_MS1
mean: 102.6075 us, lb 101.7695 us, ub 104.0159 us, ci 0.950
std dev: 5.468574 us, lb 3.681120 us, ub 8.080665 us, ci 0.950
found 16 outliers among 100 samples (16.0%)
  6 (6.0%) high mild
  10 (10.0%) high severe
variance introduced by outliers: 51.455%
variance is severely inflated by outliers

benchmarking size 5000/byteStringHexFixed
mean: 5.675204 us, lb 5.636296 us, ub 5.750211 us, ci 0.950
std dev: 264.3726 ns, lb 140.9738 ns, ub 398.8494 ns, ci 0.950
found 5 outliers among 100 samples (5.0%)
  4 (4.0%) high severe
variance introduced by outliers: 44.476%
variance is moderately inflated by outliers

私はこの数字が好きです。バイト文字列ライブラリへの私のパッチがまだ Duncan Coutts によってレビュー中であることは残念です。遅くとも、次の GHC リリースで新しいバイト文字列ビルダが利用可能になります。

于 2012-04-25T08:13:15.270 に答える
2

使っただけみたい

hex :: B.ByteString -> String
hex = concatMap (printf "%02x") . B.unpack

前回はやりたかった。これは、Crypto.Hash ライブラリ iirc と連携していました。パフォーマンスがそれほど優れているとは思えませんが、(遅い) sha512 関数自体と比較して、なぜ 16 進変換が問題になるのでしょうか?

于 2012-04-19T05:35:50.237 に答える