2010-12-16 219 views
3

J'ai essayé de résoudre Duplicate each element in a Haskell List tâche et faire comme un programme complet, qui écrivent la liste à la sortie standardComment contrôler la paresse exemple de double chaque élément de la liste

Voici ma solution

 
main :: IO() 
main = getList >>= return . doubleEachItem >>= putStrLn . show 

getList = return [1,3,5] 

doubleEachItem :: [Int] -> [Int] 
doubleEachItem = foldr (++) [] . map (take 2 . repeat) 

Mais lorsque je tente de traiter très longue liste

 
getList = return . take 10000000000 $ repeat 15 

le programme terminé avec erreur de dépassement de mémoire.

La question est: comment je peux améliorer le programme, afin qu'il puisse traiter des listes de n'importe quelle taille?

Edit:

Je pense que le programme est écrasé parce que je le lance avec la commande runghc. Dans ce cas, ghc consomme environ 3Gbytes de mémoire et a été tué par le système d'exploitation. Le fichier de sortie après le crash était seulement d'environ 0,6 Go. La raison d'un tel comportement n'est pas claire pour moi.

Lorsque je compile le programme exécutable natif ghc haskell03.hs -o haskell03 et l'exécuter avec redirection vers un fichier ./haskell03 >out03.txt il fonctionne parfaitement dans l'espace mémoire constant et produit le fichier de sortie avec la vitesse sur les 20MBytes/s. Lorsque le programme est terminé, le fichier de sortie prend 57 Go. Le temps d'exécution total était de 47 minutes.

+0

Je ne vois aucun problème lors de l'exécution du même code sur ma machine. – ephemient

+1

Note de style: 'foo >> = return. bar' est la même chose que 'fmap bar foo'. – luqui

Répondre

7

Oh! Je pense que je sais ce qui se passe. C'est subtil.

runghc s'exécute en mode interprété, comme si vous aviez chargé et exécuté le fichier via ghci. getList est une liaison de niveau supérieur, de sorte que sa valeur (et toutes les valeurs qu'elle référence) sont mises en cache. Cela signifie que GHC essayait de mettre en cache l'intégralité de votre réseau de dix milliards d'éléments.

Vous pourriez penser que si vous inline la liste, il travaillerait:

main = putStrLn . show . doubleEachElement $ [1..10^10] 

Mais pas, parce que main est un haut niveau de liaison ainsi, et il fait référence [1..10^10], de sorte que le géant se déroulait version cette liste sera également mise en cache là-bas.

La règle générale est que lorsque quelque chose ne dépend pas de l'entrée, il peut être mis en cache. Vous pouvez donc corriger cela en faisant en sorte qu'il semble dépendre de l'entrée.En mode interprété, GHC est pas très intelligent à ce sujet, il est assez facile de le tromper:

main = do 
    n <- return (10^10) 
    putStrLn . show . doubleEachElement $ [1..n] 

Cela fonctionnerait avec votre getList aussi bien, si getList a pris un paramètre au lieu de coder en dur 10^10. Heureusement, en mode compilé, GHC s'intéresse plus aux utilisations de ces symboles de niveau supérieur, de sorte qu'il peut voir que la liste n'est utilisée qu'une seule fois, et peut donc commencer à ramasser ses têtes à la sortie.

Ce problème n'apparaît pas très souvent dans le monde réel, car les programmes dépendent souvent fortement de leur entrée, il n'y a donc pas de grandes constantes de niveau supérieur comme celle-ci. Mais oui, ça peut être pénible quand GHC essaie de mettre en cache quelque chose que vous ne voulez pas.

+0

Merci. Cela résout le problème. – sign

-1

Votre implémentation doubleEachItem via foldr nécessite une liste entière construite en mémoire, car foldr commence à fonctionner à partir de la fin de la liste. Pour éviter cela, remplacer foldr-foldl' ou récrire fonction:

doubleEachItem = concatMap (replicate 2) 
+1

'foldr' n'a besoin de fonctionner que depuis la fin de la liste dans un langage strict. 'foldr' est le lazier des deux plis dans une langue paresseuse. Essayez 'prendre 10 $ doubleEachItem [1 ..]' et regardez vous donner 10 nombres. – luqui

+3

De http://www.haskell.org/onlinereport/standard-prelude.html: 'concatMap f = concat. carte f'; 'concat xss = foldr (++) [] xss'; 'répliquer n x = prendre n (répéter x)'. Donc, votre définition est exactement équivalente à la sienne. – luqui

+0

Merci pour votre commentaire. Je ne suis pas familier avec les opérateurs de sucre "Haskell" donc ce commentaire est précieux pour moi. – sign

1

Votre code est tout à fait paresseux, il n'a pas besoin d'optimisation. Ce qui se passe probablement, c'est que toute la sortie est sur une seule ligne, qui est tamponnée. Vous pouvez résoudre ce problème en désactivant tampon:

import System.IO 
main = do 
    hSetBuffering stdout NoBuffering 
    getList >>= ... 

Ou, disons, l'impression de chaque numéro sur sa propre ligne

main = getList >>= return . doubleEachItem >>= mapM_ print 
+0

Cela n'explique pas une erreur de MOO, n'est-ce pas? – ephemient

+0

Merci pour le commentaire. Je suis complètement nouveau à Haskell donc tout commentaire est précieux pour moi. Malheureusement, cette solution n'aide pas lorsque j'exécute mon programme avec runghc. Sans tampon, ghc produit la sortie très lentement mais consomme toujours de la mémoire. – sign

+0

@sign, hmm, c'est bizarre. Très lentement? Avez-vous essayé la solution 'mapM_ print'? – luqui

1

Cette application de réponse Luqui au programme original de la question avec un minimum de modifications

 
main :: IO() 
main = return 1 >>=getList >>= return . doubleEachElement >>= putStrLn . show 

getList doNotCache = return . take (10^10) $ repeat 15 

doubleEachElement :: [Int] -> [Int] 
doubleEachElement = foldr (++) [] . map (take 2 . repeat) 

Les modifications sont soulignées en gras.

Comme luqui l'a montré, getList a été mis en cache car il s'agissait d'une expression constante. Mais nous pouvons faire du haskell pour croire qu'il n'est pas constant simplement en fournissant un argument fictif, dépendant de l'entrée.