2

(厳密な) ByteString が与えられた場合、含まれる可能性のある各バイトの数を数える最も効率的な方法は何ですか?

カウントソートとして実装されるはずですsortが、関連するカウントにアクセスする方法はないようです。countまた、特定のバイトが出現する回数をカウントする関数があることもわかります。これにより、次のオプションが得られます。

  • map (\ b -> count b str) [0x00 .. 0xFF]
  • map length . group . sort
  • fold*およびIntMapバイト周波数の何か。

最高のパフォーマンスを発揮する可能性が高いのはどれですか?

4

4 に答える 4

5

dflemstrの基本的な考え方はもちろん正しいですが、最高のパフォーマンスが必要なため、次ByteStringのようにカウント配列だけでなく にも未チェックのアクセスを使用する必要があります。

import Control.Monad.ST
import Data.Array.ST
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.Unboxed

import Data.Word

import Data.ByteString (ByteString)
import qualified Data.ByteString as BS
import Data.ByteString.Unsafe

histogram :: ByteString -> UArray Word8 Int
histogram bs = runSTUArray $ do
    hist <- newArray (0, 255) 0
    let l = BS.length bs
        update b = do
            o <- unsafeRead hist b
            unsafeWrite hist b (o+1)
        loop i
            | i < 0     = return hist
            | otherwise = do
                update $ fromIntegral (bs `unsafeIndex` i)
                loop (i-1)
    loop (l-1)

criterion（ 200000 long のヒストグラムの構築）によると、それはかなりの違いを生みByteStringます：

warming up
estimating clock resolution...
mean is 1.667687 us (320001 iterations)
found 3078 outliers among 319999 samples (1.0%)
  1947 (0.6%) high severe
estimating cost of a clock call...
mean is 40.43765 ns (14 iterations)

benchmarking dflemstr
mean: 21.42852 ms, lb 21.05213 ms, ub 21.77954 ms, ci 0.950
std dev: 1.873897 ms, lb 1.719565 ms, ub 2.038779 ms, ci 0.950
variance introduced by outliers: 74.820%
variance is severely inflated by outliers

benchmarking unsafeIndex
mean: 312.6447 us, lb 304.3425 us, ub 321.0795 us, ci 0.950
std dev: 42.86886 us, lb 39.64363 us, ub 46.52899 us, ci 0.950
variance introduced by outliers: 88.342%
variance is severely inflated by outliers

(dflemstr のコードを変更してrunSTUArray、 a も使用して返すように変更UArray Word8 Intし、uiform の戻り値を持つようにしましたが、実行時間に大きな違いはありません。)

于 2013-06-15T15:32:09.030 に答える
4

最も効率的な方法は、おそらく可変配列を使用してカウントを格納することです。これは、利用可能な最も効率的な O(n) ソリューションの 1 つになる可能性があります。

import Control.Monad
import Control.Monad.ST

import Data.Array.ST

import Data.ByteString (ByteString)
import qualified Data.ByteString as ByteString

import Data.Word

byteHistogram :: ByteString -> [Int]
byteHistogram bs = runST $ do
  histogram <- newArray (minBound, maxBound) 0 :: ST s (STUArray s Word8 Int)
  forM_ (ByteString.unpack bs) $ \ byte ->
    readArray histogram byte >>= return . (+1) >>= writeArray histogram byte
  getElems histogram
于 2013-06-15T14:56:04.443 に答える