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

我想使用Haskell來計算存儲在文件中的唯一塊。該塊只是連續字節，長度爲512，目標文件的大小至少爲1GB。Haskell中有效的哈希映射容器？

這是我的第一次嘗試。

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。但沒有任何明顯的差異。

請幫我改進這個程序。

來源

2013-02-01 comatose

我不認爲你將能夠擊敗python詞典的表現。實際上，它們是用c語言實現的，並且經過多年的優化，hashmap是新的並且沒有太多優化。所以在我看來獲得3倍的表現已經夠好了。你可以在某些地方優化你的Haskell代碼，但它仍然無關緊要。如果你仍然堅持提高性能，我認爲你應該在你的代碼中使用帶有ffi的高度優化的c庫。

這裏有一些類似的討論

haskell beginners

來源

2013-02-01 04:27:09 Satvik

其實，我最關心的是內存使用情況，我無法理解Haskell hashmaps的過多內存使用情況。例如。當輸入文件包含600MB獨特數據時，它使用了大約1GB或更多的內存。無論如何，感謝您的答案和文章鏈接。我應該考慮使用FFI。 – comatose

@comatose，那只是GHC。 GHC垃圾收集策略使用複製收集器，它非常快速，但是具有2倍的內存開銷。 – luqui

這可能會根據您的使用是完全不相干的，但我稍微擔心insertWith (+) block 1。如果你的數量達到很高的數字，你會在散列圖的單元格中積累thunk。不要緊，你使用($!)，只會強制脊椎 - 值可能仍然是懶惰的。

Data.HashMap沒有提供嚴格的版本insertWith'像Data.Map那樣。從toBlocks

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

此外，您可能想輸出（而非輸入）的嚴格字節串名單，這將使散列更快：但是你可以實現它。

這就是我所擁有的 - 儘管如此，我並不是表演大師。

來源

2013-02-01 04:42:11 luqui

我可以通過創建一個'data Blk = Blk { - ＃UNPACK＃ - } Word64 ...'來保存512字節。如果切換到嚴格的ByteStrings，會發生相當大的性能提升，但我不確定這是由於諸如緩存之類的效應造成的，以及由於我的老對手懶惰ByteString塊沒有合理對齊而導致的性能提高程度。我因爲它會導致分歧，複製等）。最終，'unordered-containers'做得最好（4.8秒對比6.5秒，但這是嚴格的字節串），而'hashtable'只是因爲沒有'insertWith'操作而令人沮喪。 –

@luqui謝謝你的回答，我從你那裏學到了一些東西。實際上，在'unordered-containers'中有'Data.HashMap.Strict'，我試過了，但它不能使情況更好，也沒有嚴格的'ByteString'。 'toStrict'有點貴。 – comatose

@ ThomasM.DuBuisson謝謝，我應該嘗試一下。 – comatose

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

回答

相關問題