Comment faire mon code Haskell utiliser Laziness et Garbage collector

Question

J'ai écrit un code Haskell qui doit résoudre le problème suivant: nous avons n fichiers: f1, f2, f3 .... fn et j'ai coupé ces fichiers de manière que chaque tranche a 100 lignes

f1_1, f1_2, f1_3 .... f1_m 

    f2_1, f2_2, .... f2_n 
    ... 

    fn_1, fn_2, .... fn_k 

enfin je construis un type de données spécial (Dags) en utilisant des tranches de la manière suivante

f1_1, f2_1, f3_1, .... fn_1 => Dag1 

    f1_2, f2_2, f3_2, ..... fn_2 => Dag2 

    .... 

    f1_k, f2_k, f3_k, ..... fn_k => Dagk 

le code que j'ai écrit début en coupant tous les fichiers, il coupler les éléments de la liste des résultats et construire Dag en utilisant la liste des résultats finaux

il ressemble à ceci

-- # take a filename and cut the file in slices of 100 lines 

    sliceFile :: FilePath -> [[String]] 

    -- # take a list of lists and group the i-th elements into list 

    coupleIthElement :: [[String]] -> [[String]] 

    -- # take a list of lines and create a DAG 

    makeDags :: [String] -> Dag 

    -- # final code look like this 

    makeDag_ :: [FilePath] -> [Dag] 

    makeDags files = map makeDags $ coupleIthElement (concat (map sliceFile files)) 

Le problème est que ce code est non-efficace, car:

• dont il a besoin stocker tous les fichiers dans la mémoire sous forme de listes

• le garbage collector ne fonctionne pas efficacement puisque toutes les fonctions ont besoin de la liste des résultats de la fonction précédente

Comment puis-je réécrire mon programme pour tirer parti du travail de garbage collector et de Laziness of Haskell?

Si ce n'est pas possible ou plus facile, que puis-je faire pour être plus efficace, même un peu?

merci pour la réponse

---

modifier

coupleIthElement ["abc", "123", "xyz"] doit retourner ["a1x","b2y","c3z"]

des causes les 100 lignes sont arbitraires sélectionnées en utilisant un critère particulier sur certains éléments des lignes, mais je jeter cet aspect pour rendre le problème plus facile à comprendre,

une autre édition

data Dag = Dag ([(Int, String)], [((Int, Int), Int)]) deriving Show 

test_dag = Dag ([(1, "a"),(2, "b"),(3, "c")],[((1,2),1),((1,3),1)]) 

test_dag2 = Dag ([],[]) 

la première liste est chaque Vertice définit par le nombre et l'étiquette, la deuxième liste est les bords ((1,2),3) signifie arête entre Vertice 1 et 2 avec le coût 3

Answer 1

Quelques points:

1) Avez-vous pensé à utiliser fgl? C'est probablement plus efficace que votre propre implémentation Dag. Si vous avez vraiment besoin d'utiliser Dag, vous pouvez construire vos graphiques avec fgl puis les convertir en Dag quand ils sont terminés.

2) Il semble que vous n'utilisiez pas réellement les tranches lors de la construction de vos graphiques, mais plutôt qu'ils contrôlent le nombre de graphiques que vous avez. Si oui, que diriez-vous quelque chose comme ceci:

dagFromHandles :: [Handle] -> IO Dag 
dagFromHandles = fmap makeDags . mapM hGetLine 

allDags :: [FilePath] -> IO [Dag] 
allDags listOfFiles = do 
    handles <- mapM (flip openFile ReadMode) listOfFiles 
    replicateM 100 (dagFromHandles handles) 

Cela suppose que chaque fichier a au moins 100 lignes et des lignes supplémentaires seront ignorées. Il serait encore mieux si vous aviez une fonction qui consommerait une Dag, alors vous pourriez faire

useDag :: Dag -> IO() 

runDags :: [FilePath] -> IO() 
runDags listOfFiles = do 
    handles <- mapM (flip openFile ReadMode) listOfFiles 
    replicateM_ 100 (dagFromHandles handles >>= useDag) 

Cela devrait permettre une utilisation plus efficace de la collecte des ordures.

Bien sûr, cela suppose que je comprends correctement le problème, et je ne suis pas certain de le faire. Notez que concat (map sliceFile) devrait être un no-op (sliceFile aurait besoin d'être dans IO comme vous avez défini le type, mais en ignorant cela pour le moment), donc je ne vois pas pourquoi vous le dérangez du tout.

Answer 2

Si c'est pas nécessaire de traiter votre fichier en tranches, éviter cela. Haskell fait cela automatiquement! Dans Haskell, vous pensez à IO en tant que flux. Les données sont lues depuis l'entrée, dès qu'elles sont nécessaires et rejetées, dès qu'elles sont inutilisées. Ainsi, par exemple, c'est un programm copie de fichiers facile:

main = interact id 

interact a la signature interact :: (String -> String) -> IO(), et alimente l'entrée en fonction qu'il gère et produit une sortie qui est écrit sur la sortie standard. Ce programme est plus efficace que la plupart des implémentations C, car le runtime tamponne automatiquement l'entrée et la sortie.Si vous voulez comprendre la paresse, vous devez oublier toute la sagesse que vous avez apprise en tant que programmeur impératif et vous devez considérer un programme comme une description pour modifier des données, pas comme un ensemble d'instructions - les données sont traitées uniquement. si nécessaire!

Le point clé, pourquoi vos données peuvent être traitées dans le mauvais sens est la translation multiple de la liste. Votre fonction makeDags parcourt la liste de tranches transposée une par une, de sorte que les éléments de la liste d'origine ne peuvent pas être ignorés. Ce que vous devriez essayer, est d'écrire votre fonction d'une manière comme ceci:

sliceFile :: FilePath -> [[String]] 
sliceFile fp = do 
    f <- readFile fp 
    let l = lines fp 
     slice [] = [] 
     slice x = ll : slice ls where (ll,ls) = splitAt 100 x 
    return slice l 

sliceFirstRow :: [[String]] -> ([String],[[String]]) 
sliceFirstRow list = unzip $ map (\(x:xs) -> (x,xs)) list 

makeDags :: [[String]] -> [Dag] 
makeDags [[]] = [] 
makeDags list = makeDag firstRow : makeDags restOfList where 
(firstRow,restOfList) = sliceFirstRow list 

Cette fonction peut être une solution, car la première ligne est plus référencé, quand il est fait. Mais dans la plupart des cas, ceci est dû à la paresse, donc vous pouvez probablement essayer d'utiliser seq pour forcer la construction des Dags et permettre aux données d'E/S d'être récupérées. (Si vous ne forcez pas la construction des dags, les données ne peuvent pas être récupérées).

Mais de toute façon, je pourrais fournir une réponse plus utile, si vous donnez quelques informations sur ce que ces dags sont.