सूची पैकेज से मोनैडिक सूचियों का उपयोग करके मेरा कोड इतना धीमा क्यों है?

Question

पिछले हफ्ते उपयोगकर्ता मास ने हास्केल में एक निर्देशिका में question about recursively listing files से पूछा। मेरा पहला विचार प्रिंटिंग शुरू होने से पहले स्मृति में पूरी सूची बनाने से बचने के लिए List package से मोनैडिक सूचियों का उपयोग करने का प्रयास करना था। मैंने इसे निम्नानुसार कार्यान्वित किया:

module Main where 

import Prelude hiding (filter) 
import Control.Applicative ((<$>)) 
import Control.Monad (join) 
import Control.Monad.IO.Class (liftIO) 
import Control.Monad.ListT (ListT) 
import Data.List.Class (cons, execute, filter, fromList, mapL) 
import System (getArgs) 
import System.Directory (getDirectoryContents, doesDirectoryExist) 
import System.FilePath ((</>)) 

main = execute . mapL putStrLn . listFiles =<< head <$> getArgs 

listFiles :: FilePath -> ListT IO FilePath 
listFiles path = liftIO (doesDirectoryExist path) >>= listIfDir 
    where 
    valid "." = False 
    valid ".." = False 
    valid _ = True 
    listIfDir False = return path 
    listIfDir True 
     = cons path 
     $ join 
     $ listFiles 
    <$> (path </>) 
    <$> (filter valid =<< fromList <$> liftIO (getDirectoryContents path)) 

यह खूबसूरती से प्रिंट करना शुरू करता है और बहुत कम स्मृति का उपयोग करता है। दुर्भाग्यवश यह तुलनीय FilePath -> IO [FilePath] संस्करण की तुलना में धीमी बार भी धीमी है।

मैं क्या गलत कर रहा हूं? मैंने इस तरह के खिलौनों के उदाहरणों के बाहर List पैकेज का ListT कभी भी उपयोग नहीं किया है, इसलिए मुझे नहीं पता कि किस प्रकार का प्रदर्शन अपेक्षित है, लेकिन ~ 40,000 फ़ाइलों के साथ निर्देशिका को संसाधित करने के लिए 30 सेकंड (बनाम सेकेंड का एक अंश) बहुत धीमी

Answer 1

प्रोफाइलिंग से पता चलता है कि join (doesDirectoryExists के साथ) आपके कोड में अधिकांश समय के लिए खाते हैं। देखते हैं कि कैसे अपनी परिभाषा करेंगी चलें:

join x 
=> (definition of join in Control.Monad) 
    x >>= id 
=> (definition of >>= in Control.Monad.ListT) 
    foldrL' mappend mempty (fmap id x) 
=> (fmap id = id) 
    foldrL' mappend mempty x 

खोज की रूट निर्देशिका में वहाँ k उपनिर्देशिका हैं और उनकी सामग्री को पहले से ही सूची में अभिकलन रहे हैं: d1, d2, ... dk, तो join लागू करने के बाद आप (मोटे तौर पर) प्राप्त होंगे: (...(([] ++ d1) ++ d2) ... ++ dk)। चूंकि x ++ y समय O(length x) लेता है, इसलिए पूरी चीज़ में समय लगेगा O(d1 + (d1 + d2) + ... + (d1 + ... dk-1))। अगर हम मानते हैं कि फाइलों की संख्या n है और उन्हें d1 ... dk के बीच समान रूप से वितरित किया जाता है तो join की गणना करने का समय O(n*k) होगा और यह केवल listFiles के पहले स्तर के लिए होगा।

यह, मुझे लगता है, आपके समाधान के साथ मुख्य प्रदर्शन समस्या है।

Answer 2

इसे एक बड़ी निर्देशिका में चलाने से स्मृति रिसाव पता चलता है। मुझे संदेह है कि इसे GetDirectoryContents की सख्तता से करना है, लेकिन हो सकता है कि आगे बढ़ रहा हो। सरल प्रोफाइलिंग बहुत अधिक नहीं हुआ, मैं कुछ अतिरिक्त लागत केंद्र जोड़ता हूं और वहां से जाता हूं ...

Answer 3

मैं उत्सुक हूं, logict का उपयोग करने के लिए एक ही प्रोग्राम कितना अच्छा लिखा गया है? LogicT अर्थात् ListT जैसा ही है, लेकिन निरंतरता-गुजरने वाली शैली में कार्यान्वित किया गया है ताकि इसमें concat-संबंधित प्रकार की समस्याएं न हो जो आप चल रहे हैं।

import Prelude hiding (filter) 
import Control.Applicative 
import Control.Monad 
import Control.Monad.Logic 
import System (getArgs) 
import System.Directory (getDirectoryContents, doesDirectoryExist) 
import System.FilePath ((</>)) 

main = sequence_ =<< observeAllT . fmap putStrLn . listFiles =<< head <$> getArgs 

cons :: MonadPlus m => a -> m a -> m a 
cons x xs = return x `mplus` xs 

fromList :: MonadPlus m => [a] -> m a 
fromList = foldr cons mzero 

filter :: MonadPlus m => (a -> Bool) -> m a -> m a 
filter f xs = do 
    x <- xs 
    guard $ f x 
    return x 

listFiles :: FilePath -> LogicT IO FilePath 
listFiles path = liftIO (doesDirectoryExist path) >>= listIfDir 
    where 
    valid "." = False 
    valid ".." = False 
    valid _ = True 
    listIfDir False = return path 
    listIfDir True 
     = cons path 
     $ join 
     $ listFiles 
    <$> (path </>) 
    <$> (filter valid =<< fromList <$> liftIO (getDirectoryContents path))