我想使用 Haskell 计算存储在文件中的唯一 block 。
该 block 只是长度为 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
.但是并没有什么明显的区别。
请帮助我改进这个程序。
最佳答案
我认为您无法击败 python 字典的性能。它们实际上是在 c 中实现的,并在其中进行了多年的优化,另一方面,hashmap 是新的,并没有那么优化。因此,在我看来,获得 3 倍的性能就足够了。您可以在某些地方优化您的 haskell 代码,但这仍然无关紧要。如果您仍然坚持提高性能,我认为您应该在代码中使用高度优化的 c 库和 ffi。
以下是一些类似的讨论
haskell beginners
关于haskell - Haskell 中高效的 HashMap 容器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14639322/