Haskell中的高效哈希映射容器？

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

它有效,但我对它的执行时间和内存使用感到沮丧.Especilly当我与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.但没有任何明显的差异.

请帮我改进这个程序.

Answer 1

我不认为你能够击败python词典的表现.它们实际上是在c中实现的,经过多年的优化,另一方面,hashmap是新的,并没有那么多优化.因此,在我看来,获得3倍的表现就足够了.您可以在某些地方优化您的haskell代码,但仍然无关紧要.如果您仍然坚持提高性能,我认为您应该在代码中使用带有ffi的高度优化的c库.

以下是一些类似的讨论

哈斯克尔初学者