12

Haskell を使用して、ファイルに格納されている一意のブロックをカウントしたいと考えています。ブロックは長さが 512 の連続したバイトであり、ターゲット ファイルのサイズは少なくとも 1GB です。

これは私の最初の試みです。

import           Control.Monad
import qualified Data.ByteString.Lazy as LB
import           Data.Foldable
import           Data.HashMap
import           Data.Int
import qualified Data.List            as DL
import           System.Environment

type DummyDedupe = Map LB.ByteString Int64

toBlocks :: Int64 -> LB.ByteString -> [LB.ByteString]
toBlocks n bs | LB.null bs = []
              | otherwise = let (block, rest) = LB.splitAt n bs
                            in block : toBlocks n rest

dedupeBlocks :: [LB.ByteString] -> DummyDedupe -> DummyDedupe
dedupeBlocks = flip $ DL.foldl' (\acc block -> insertWith (+) block 1 $! acc)

dedupeFile :: FilePath -> DummyDedupe -> IO DummyDedupe
dedupeFile fp dd = LB.readFile fp >>= return . (`dedupeBlocks` dd) . toBlocks 512

main :: IO ()
main = do
  dd <- getArgs >>= (`dedupeFile` empty) . head
  putStrLn . show . (*512) . size $ dd
  putStrLn . show . (*512) . foldl' (+) 0 $ dd

動作しますが、実行時間とメモリ使用量に不満を感じました. 特に C++ や下記の Python 実装と比べてみると、3~5 倍遅く、2~3 倍のメモリ容量を消費していました。

import os
import os.path
import sys

def dedupeFile(dd, fp):
    fd = os.open(fp, os.O_RDONLY)
    for block in iter(lambda : os.read(fd, 512), ''):
        dd.setdefault(block, 0)
        dd[block] = dd[block] + 1
    os.close(fd)
    return dd

dd = {}
dedupeFile(dd, sys.argv[1])

print(len(dd) * 512)
print(sum(dd.values()) * 512)

これは主に hashmap の実装によるものだと思い、 、 、 などの他の実装を試しhashmapましhashtablesたunordered-containers。しかし、目立った違いはありませんでした。

このプログラムの改善にご協力ください。

4

2 に答える 2

6

Python 辞書のパフォーマンスに勝るものはないと思います。それらは実際にはcで実装されており、何年にもわたる最適化が行われていますが、ハッシュマップは新しく、それほど最適化されていません。したがって、私の意見では、パフォーマンスが 3 倍になれば十分です。特定の場所で Haskell コードを最適化できますが、それでも大した問題にはなりません。パフォーマンスの向上にまだ固執している場合は、コードで ffi を使用して高度に最適化された C ライブラリを使用する必要があると思います。

似たような議論はこちら

ハスケル初心者

于 2013-02-01T04:27:09.110 に答える
3

使い方によっては全く関係ないかもしれませんが、ちょっと気になるところinsertWith (+) block 1です。カウントが多くなると、ハッシュ マップのセルにサンクが蓄積されます。を使用したかどうかは問題ではありません。これは($!)スパインを強制するだけです。値はまだ遅延している可能性があります。

Data.HashMapinsertWith'のように厳密なバージョンは提供しませんData.Map。しかし、あなたはそれを実装することができます:

insertWith' :: (Hashable k, Ord k) => (a -> a -> a) -> k -> a 
                                   -> HashMap k a -> HashMap k a
insertWith' f k v m = maybe id seq maybeval m'
    where
    (maybeval, m') = insertLookupWithKey (const f) k v m

また、 から厳密なByteStringsのリストを出力 (入力ではなく) したい場合がありますtoBlocks。これにより、ハッシュが高速になります。

私が持っているのはこれだけです。ただし、私はパフォーマンスの第一人者ではありません。

于 2013-02-01T04:42:11.540 に答える