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 中实现的，并且经过了多年的优化，另一方面，hashmap 是新的并且没有那么优化。因此，在我看来，获得 3 倍的性能就足够了。您可以在某些地方优化您的 haskell 代码，但这仍然无关紧要。如果您仍然坚持提高性能，我认为您应该在代码中使用高度优化的 c 库和 ffi。

以下是一些类似的讨论

哈斯克尔初学者

于 2013-02-01T04:27:09.110 回答
3

根据您的使用情况，这可能完全无关紧要，但我有点担心insertWith (+) block 1. 如果您的计数达到很高的数字，您将在哈希映射的单元格中累积 thunk。你使用 没关系($!)，这只会迫使脊椎 - 这些值可能仍然是懒惰的。

Data.HashMap没有提供严格的insertWith'版本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

此外，您可能希望从 输出（但不输入）严格的ByteString列表toBlocks，这将使散列更快。

这就是我所拥有的——不过，我不是表演大师。

于 2013-02-01T04:42:11.540 回答