ハスケルの効率的なハッシュマップコンテナ？

Question

私は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、hashtables及びunordered-containersなどの他の実装を試みました。 しかし、顕著な違いはありませんでした。

このプログラムを改善するのに手伝ってください。

Answer 1

私はあなたがpython辞書の性能を上回ることはできないと思います。彼らは実際には、ハッシュマップはそれほど最適化されていないハッシュマップで入れられた長年の最適化でcで実装されています。私の意見で3倍のパフォーマンスを得ることは十分です。特定の場所でhaskellコードを最適化することはできますが、それでも問題はありません。あなたがまだパフォーマンスを向上させることに固執しているのであれば、あなたのコードでffiを使って高度に最適化されたCライブラリを使うべきだと思います。ここで

同様の議論

haskell beginners

Answer 2

の一部ですこれは、あなたの使用状況に応じて、完全に無関係かもしれないが、私はinsertWith (+) block 1について少し心配しています。カウントが高い数値に達すると、ハンクマップのセルにサンクが蓄積されます。 ($!)を使用しても問題ありません。値はまだ怠け者である可能性があります。

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

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 

また、あなたはより速くハッシングようになりますこれは、（入力ではなく）toBlocksから厳しいバイト文字列のリストを出力したい場合があります。

これはすべて私が持っているものです。しかし、私はパフォーマンスの専門家ではありません。