हास्केल में कुशल हैश नक्शा कंटेनर?

Question

मैं हास्केल का उपयोग कर फ़ाइल में संग्रहीत अद्वितीय ब्लॉक गिनना चाहता हूं। ब्लॉक 512 की लंबाई के साथ लगातार बाइट्स है और लक्ष्य फ़ाइल का आकार कम से कम 1 जीबी है।

यह मेरी प्रारंभिक कोशिश है।

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 

यह काम करता है, लेकिन मैं इसके निष्पादन समय और स्मृति उपयोग से निराश हो गया। स्पष्ट रूप से जब मैंने नीचे सूचीबद्ध सी ++ और यहां तक ​​कि पायथन कार्यान्वयन की तुलना की, तो यह 3 ~ 5x धीमा था और 2 ~ 3x अधिक स्मृति स्थान का उपभोग किया।

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

मुझे नहीं लगता कि आप पाइथन शब्दकोशों के प्रदर्शन को हरा सकते हैं। वे वास्तव में सी में लागू किए गए अनुकूलन के वर्षों के साथ लागू होते हैं, दूसरी ओर हैशप नया है और इतना अनुकूलित नहीं है। तो मेरी राय में 3x प्रदर्शन प्राप्त करना काफी अच्छा है। आप कुछ स्थानों पर हैकेल कोड अनुकूलित कर सकते हैं लेकिन फिर भी इससे कोई फर्क नहीं पड़ता। यदि आप अभी भी प्रदर्शन बढ़ाने के बारे में अशिष्ट हैं, तो मुझे लगता है कि आपको अपने कोड में एफएफआई के साथ एक अत्यधिक अनुकूलित सी लाइब्रेरी का उपयोग करना चाहिए।

यहाँ समान विचार विमर्श के कुछ

haskell beginners

Answer 2

यह आपके उपयोग के आधार पर पूरी तरह से अप्रासंगिक हो सकता है, लेकिन मैं insertWith (+) block 1 के बारे में थोड़ा चिंतित हूँ। यदि आपकी गणना उच्च संख्या तक पहुंच जाती है, तो आप हैश मानचित्र की कोशिकाओं में थंक जमा करेंगे। इससे कोई फर्क नहीं पड़ता कि आपने ($!) का उपयोग किया है, जो केवल रीढ़ की हड्डी को मजबूर करता है - मान अभी भी आलसी हैं।

Data.HashMap कोई सख्त संस्करण insertWith' प्रदान करता है जैसे Data.Map करता है। toBlocks से सख्त ByteStrings की एक सूची

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 

इसके अलावा, आप उत्पादन के लिए (लेकिन इनपुट नहीं) चाहते हो सकता है, जो तेजी से hashing कर देगा: लेकिन आप इसे लागू कर सकते हैं।

यह सब मुझे मिला है - हालांकि, मैं कोई प्रदर्शन गुरु नहीं हूं।