IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Défis langages fonctionnels Discussion :

Défi N°1 : Génération des ensembles de nombre dont la somme est identique


Sujet :

Défis langages fonctionnels

  1. #1
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut Défi N°1 : Génération des ensembles de nombre dont la somme est identique
    Bonjour,

    Pour ce premier défi, l'équipe de developpez.com vous propose un challenge assez simple pour débuter.

    Le problème étant le suivant :

    Challenge :
    Soit un entier n en entrée,
    Déterminer tous les ensembles de nombre entier positif dont la somme vaut n.

    Par exemple pour 5, tous les ensembles de nombre dont la somme vaut 5 sont :
    • 5
    • 4 1
    • 3 2
    • 3 1 1
    • 2 2 1
    • 2 1 1 1
    • 1 1 1 1 1


    A noter que l'on souhaite des ensembles, il n'y a donc pas de doublon (on a une seule fois (3,2), et pas : (3,2) et (2,3) par exemple).

    Il n'y a pas de règle sur le format de sortie. Le format standard pour les langages fonctionnels pourra par exemple être une liste de liste :
    [[5], [4,1], [3,2], [3,1,1], [2,2,1], [2,1,1,1], [1,1,1,1,1]]

    Pour un langage impératif, la sortie pourra simplement être écrite sur la sortie standard.


    Les règles

    Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :
    • la maintenabilité
    • la simplicité
    • le fait qu'il soit optimisé


    Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.

    Pour répondre, il vous suffit de poster à la suite.

    A vos claviers
    de votre participation.

    __________________________
    Sujet proposé par Jedaï
    Je ne répondrai à aucune question technique en privé

  2. #2
    LLB
    LLB est déconnecté
    Membre expérimenté
    Inscrit en
    Mars 2002
    Messages
    967
    Détails du profil
    Informations forums :
    Inscription : Mars 2002
    Messages : 967
    Points : 1 410
    Points
    1 410
    Par défaut
    Solution en F# :
    Code F# : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    let sums n =
      let rec sumrec = function
       | 0, _ -> [[]]
       | n, m -> [for i in 1 .. min n m ->> [for j in sumrec((n - i), i) -> i :: j]]
      sumrec(n, n)

    Exemple d'appel :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    > sums 5;;
    val it : int list list
    = [[1; 1; 1; 1; 1]; [2; 1; 1; 1]; [2; 2; 1]; [3; 1; 1]; [3; 2]; [4; 1]; [5]]

  3. #3
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Effectivement, c'est l'algorithme le plus naturel à mon avis, et les "list comprehension" permettent de l'exprimer de façon compacte :
    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    sums n = csums n n
        where
          csums 0 _ = [[]]
          csums n m = [x:xs | x <- [1..min n m], xs <- csums (n-x) x ]

    J'explique la solution :
    On utilise une fonction auxiliaire csums() qui prend deux paramètres n et m et renvoie la liste des ensembles de nombres inférieurs à m dont la somme est n.
    Cette fonction marche de la façon suivante :
    Si n = 0, on considère que l'ensemble vide est la seule solution (dans ce problème on n'utilise pas le 0 dans les solutions, sinon il y en aurait une infinité), d'où le :
    (le _ peut reconnaître n'importe quoi, on ne se soucie pas de la valeur de m dans ce cas)
    Sinon si n > 0 (on ne vérifie pas ici à vrai dire, mais la structure de la fonction fait que si n < 0, elle renverra [], la liste vide, ce qui est correct), alors on utilise un générateur de liste par compréhension, qui ressemble beaucoup à une définition d'ensemble en mathématiques.
    En gros la définition mathématiques correspondante serait :
    ensemble des "x suivi de xs" tels que x appartient à l'ensemble des entiers de 1 au minimum de n et m et xs appartient à l'ensemble des ensembles de nombres inférieurs à x dont la somme est (n - x).
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    csums n m = [x:xs | x <- [1..min n m], xs <- csums (n-x) x ]
    le (:) rajoute x au début de la liste xs, vous pouvez voir <- comme "appartient à", et [a..b] signifie "l'ensemble des entiers de a à b" (ça marche aussi avec les autres types énumérables).
    En notation mathématique :


    Cette algorithme s'appuie donc sur une récursion dont le cas de base est n = 0, ce qui est correct puisqu'à chaque appel récursif le n est diminué mais reste supérieur ou égal à 0. De plus il génère des listes triées dans l'ordre décroissant, ce qui évite les doublons.

    --
    Jedaï

  4. #4
    Rédacteur/Modérateur
    Avatar de Trap D
    Profil pro
    Inscrit en
    Septembre 2003
    Messages
    4 942
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2003
    Messages : 4 942
    Points : 6 498
    Points
    6 498
    Par défaut
    Une solution Prolog, simple mais pas optimisée puisqu'elle balaie toutes les solutions, le nettoyage se faisant par un tri puis une élimination des doublons avec le setof.
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    % le Predicat d'appel
    % N : le nombre a decomposer
    % L : la liste des décompositions possibles
    decomposition(N, L) :-
    	% le setof permet la collecte de tous les resultats
            % et le nettoyage des doublons
    	setof(L1, une_decomposition(N,L1), L).
    
    % Le predicat qui fournit une decomposition en somme 
    % N : le nombre a decomposer,
    % L : la liste resultat triee dans l'ordre naturel croissant
    une_decomposition(N, L) :-
    	% Le predicat central qui cree la decomposition en somme
    	% N  : le nombre à decomposer
    	% LN : la liste resultat
    	somme(N, LN), 
    	% tri de la liste obtenue
    	msort(LN, L).
    
    % La condition d'arret du prédicat recursif somme
    % Le nombre 0 possède une decomposition vide.
    somme(0, []) :- !.
    
    
    somme(N, [N1 | LN]) :-
    	% on prend un nombre quelconque entre 1 et N
    	% premier élément de la liste résultat
    	between(1, N, N1),
    	N2 is N - N1,
    	% on complete la liste résultat avec la décomposition
    	% du complément à N du premier nombre
    	somme(N2, LN).
    "La haine seule fait des choix" - Koan Zen
    "Il ne faut pas être meilleur que les autres, il faut être meilleur que soi." Albert Jacquard
    "Ceux qui savent où ils ont posé leur parapluie ne sont pas alcooliques." - pgibonne.
    Faites du Prolog, ça vous changera les idées !
    Ma page Prolog
    Mes codes sources commentés

    Mon avatar : La Madeleine à la veilleuse de Georges de La Tour

  5. #5
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Les plus exigeants d'entre vous auront peut-être remarqué que pour l'instant aussi bien ma solution que celle de LLB répètent inutilement certains appels à la fonction auxiliaire (csums dans mon cas, sumrec dans le cas de LLB) durant la récursion... Ces appels pourraient être éliminés en mémorisant les résultats intermédiaires.

    Voici une solution utilisant cette optimisation en Haskell :
    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    sums n = a ! (n,n)
        where
          a = array ( (0,0), (n, n) ) 
              $ ( (0,0), [[]] ) : populateList
          populateList = [( (k,l), [x:xs | x<-[1..l], xs<-a!(k-x, min (k-x) x)] )
                              | k<-[1..n], l<-[1..k]]

    a est un tableau (array), ou plutôt une matrice, dont les indices vont de (0,0) à (n,n) (le premier argument de la fonction array donne les bornes de ses indices), et dont les valeurs sont données par la liste associative en second argument.
    Une liste associative est une liste de paire (a,b) où a est la clé et b la valeur associée à la clé. Si (a,b) se trouve dans la liste associative, le tableau produit par array() aura la valeur b à l'indice a.
    Ici tout le travail est effectué dans cette liste associative : à l'indice (k,l) (pour k variant de 1 à n et l variant de 1 à k), elle associe le résultat de csums k l, sauf qu'au lieu d'appeler récursivement une fonction, elle récupère directement les résultats intermédiaires dont elle a besoin dans le tableau a...

    Nous voyons ici l'une des force d'Haskell puisque la définition du tableau a utilise le tableau a. Ceci n'est possible que grâce à la paresse d'Haskell, qui ne calcule une valeur que s'il en a besoin. En conséquence de quoi, les éléments de ce tableau a ne sont calculés qu'à partir du moment où on les utilises, ce qui est le cas lorsqu'on demande "a ! (n,n)" (l'équivalent de a[n][n] ou a[n,n] dans d'autres langages). L'ordre des éléments dans la liste associative n'a aucune importance (bien qu'ici ils soient "dans le bon ordre" par pure coïncidence, cela n'a aucune influence sur l'ordre d'exécution).

    Cette version bien que légèrement plus compliquée (mais néanmoins tout à fait abordable puisque j'ai écris cette fonction en moins d'une minute), a des performances très nettement supérieur à la précédente.

    Je précise que cette fonction reste complètement dans le paradigme fonctionnel, d'ailleurs le tableau a est fonctionnel puisque immuable.

    --
    Jedaï

    PS : Certains d'entre vous auront peut-être remarqué que la moitié du tableau reste inoccupée et inutile. Il est facile de remédier à cela en définissant un nouveau type Pair x y où x >= y et en en faisant une instance de la type class Ix (Index), mais il s'agit là de sujets avancés d'Haskell, qui ne relèvent pas vraiment du sujet.

  6. #6
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    Une implémentation "triviale" en OCaml... histoire de donner un exemple

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    let rec build_list n m = if n>m then [] else n::(build_list (n+1) m);;
    
    let rec sumrec n =
    	match n with
    		0 -> [[]]
    		|1 -> [[1]]
    		|n -> 
    			let intervalle = build_list 1 (n-1) in
    			List.concat 
    				(List.map 
    					(fun i -> List.map 
    							(fun l -> (n-i)::l) 
    							(sumrec (n-i))) 
    					intervalle)
    ;;
    
    let rec print_list l =
    	match l with
    		[] -> ()
    		|a::q -> Printf.printf "%d " a ; print_list q
    ;;
    
    let rec print lst = 
    	match lst with
    		[] -> ()
    		|a::q -> Printf.printf "[ " ; print_list a ; Printf.printf "] \n" ; print q
    ;;
    
    let main () =
    	print (sumrec (int_of_string Sys.argv.(1)))
    ;;
    
    main ();;
    nb: seule la fonction en gras est nécessaire... mais le reste vous permettra de le compiler, de l'exécuter et de visualiser le résultat tel quel



    la complexité temporelle est exponentielle en le premier argument, et l'occupation mémoire l'est aussi (mais c'est le problème qui le veut ) => j'arrive à calculer jusqu'à 17 puis stack overflow

    si j'ajoutais la mémorisation des résultats précedemment calculer (on se sert en effet de toutes les valeurs de sumrec i pour 0<i<n pour calculer sumrec n), le temps de calcul serait linéaire, mais la mémoire exploserait plus tot
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  7. #7
    LLB
    LLB est déconnecté
    Membre expérimenté
    Inscrit en
    Mars 2002
    Messages
    967
    Détails du profil
    Informations forums :
    Inscription : Mars 2002
    Messages : 967
    Points : 1 410
    Points
    1 410
    Par défaut
    Gogonite > j'ai testé ton code, mais ça marche pas vraiment (ou y a un truc que j'ai pas compris ?).

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    $ ocaml sum.ml 3
    [ 2 1 1 ]
    [ 1 1 ]
    Si certains veulent tester ma version F#, il faut ajouter "#light" (pour prendre en compte l'indentation) et ajouter à la fin la ligne :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    Sys.argv.(1) |> int_of_string |> sums |> print_any
    Pour l'explication de mon code, je renvoie à celle de Jedai : c'est la même chose (des list comprehensions).

  8. #8
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Bon, en dehors de quelques petits problèmes dans la fonction (genre (n-i) à la place de i), quelques remarques :
    la complexité temporelle est exponentielle en le premier argument, et l'occupation mémoire l'est aussi (mais c'est le problème qui le veut ) => j'arrive à calculer jusqu'à 17 puis stack overflow
    Comme on cherche les ensembles et non les n-uplets, la complexité n'est pas aussi catastrophique que ça... Et de mon côté j'arrive à calculer au moins jusqu'à 70 (en 12 secondes en interprété pour ma fonction utilisant un tableau, elle utilise à peu près 500 Mo de RAM). Mais bien sûr ta fonction trouve les n-uplet, elle, ce qui effectivement est nettement plus méchant...
    De mon côté j'ai la fonction suivante pour les n-uplets, elle monte jusqu'à 24 en 18 secondes (toujours en interprété) et avec 500 Mo de RAM au moins d'occupé... Là je n'ose pas la pousser plus loin ! (on notera bien sûr que pour 24, il y a 2^23 n-uplets solutions, l'occupation en RAM est plutôt honnête et même étrange, compte tenu que cela fait 8_388_608 liste de longueur moyenne 12.5... Autrement dit 104857600 * 8 octets (en espérant que les Int soient boxés, ce qui en mode interprété Haskell n'est pas probable)... Impossible n'est-ce pas (cela fait déjà plus de 500 Mo) ? Nous y reviendrons).
    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    nsums = [[]]:[[x:xs | x <- [1..n], xs <- nsums !! (n - x) ] | n <- [1..]]

    Ma fonction n'en est pas une, c'est une liste infinie (mais paresseuse, donc tout va bien ne vous inquiétez pas). Pour trouver l'ensemble des n-uplets de nombres dont la somme est 24, il suffit de regarder au 24ème indice de cette liste :
    ( liste !! 0 renvoie le premier élément d'une liste, tableau ! i renvoie la valeur à l'indice i d'un tableau en Haskell)

    Mais la mémoire devrait éclater avec toutes les listes intermédiaires, non ? En fait il y a un "truc" (dont devrait aussi bénéficier Gorgonite, c'est pourquoi je suis étonné qu'il ait un problème à 17 éléments), réfléchissez bien !!


    --
    Jedaï

  9. #9
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    La fonction de Gorgonite en Haskell (ou du moins sa copie conforme, l'algorithme est strictement le même) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    nsums 0 = [[]]
    nsums n =  concatMap (\m -> map (m:) $ nsums $ n-m) [1..n]
    le $ est l'opérateur d'application, autrement dit il fait la même chose que l'espace, "f $ x" est strictement équivalent à "f x", mais son intérêt réside en sa très faible priorité (la plus faible de tous les opérateurs Haskell), qui permet de se passer de parenthèses dans nombre de cas, comme ici autour de "sums $ n-m" et de "n-m". Pour ceux qui ont fait du shell, vous pouvez voir ça comme un pipe à l'envers : "n-m" passe à "sums", qui passe à "map (m:)".

    Cette fonction est légèrement plus lente que la liste infinie et occupe à peu près autant de place.

    --
    Jedaï

  10. #10
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Puisque tout le monde mets une version compilable de son programme, je vais en mettre une également :
    Code Haskell : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    module Main where
    import System -- pour getArgs
    import Data.Array
     
    main = do
      argv <- getArgs
      print $ sums $ read $ argv !! 0
     
    -- ou si vous préférez le style "point-free" (autrement dit sans variable)
    -- main = getArgs >>= print . sums . read . (!! 0)
     
    sums n = a ! (n,n)
        where
          a = array ( (0,0), (n, n) ) 
              $ ( (0,0), [[]] ) : populateList
          populateList = [( (k,l), [x:xs | x<-[1..l], xs<-a!(k-x, min (k-x) x)] )
                              | k<-[1..n], l<-[1..k]]

    Notez bien que cette version ne pourra pas vous servir de benchmark : tout ce que vous mesurerez c'est la vitesse des IO sur votre console... Rajoutez plutôt un length après le print si vous voulez mesurer les vitesses d'exécution.

    read() est une fonction qui prend une chaîne en argument et essaie de la parser de façon à produire le type exigé par le contexte (ici il s'agit de Int).

    --
    Jedaï

  11. #11
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    > Mais la mémoire devrait éclater avec toutes les listes intermédiaires, non ?
    > En fait il y a un "truc" (dont devrait aussi bénéficier Gorgonite, c'est
    > pourquoi je suis étonné qu'il ait un problème à 17 éléments), réfléchissez
    > bien !!

    Le 'truc' me semble être le partage implicite des listes.

    Comme tu travailles sur une liste paresseuse, si pour deux mêmes valeurs de (n - x), la liste renverra bien le même élément (physique), il y aura donc partage des queues de liste.

    Cependant, je pense que contrairement à ce que tu dis, Gorgonite n'en profite pas :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    List.map (fun l -> (n-i)::l) (sumrec (n-i))
    Les listes l (au passage, mes yeux te remercieraient de mettre "li" la prochaine fois, gorgonite) ne sont pas les mêmes à chaque application de cons, il n'y a pas de partage (et les têtes sont dupliquées).
    Pour obtenir un partage des listes, il faudrait construire la fonction "à l'envers", en passant (n-i) en argument supplémentaire à sumrec, comme on le fait pour les fonction tail-récursives, afin qu'il l'ajoute au *fond* de toutes les listes générées, où il pourrait effectivement être partagé.
    (En gros, ses listes formes un arbre implicite, mais dans le mauvais sens : il faut le retourner, pour que la racine coincide avec les queues des listes)

  12. #12
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Histoire de vérifier ces histoires de partage, j'ai fait le test sur mon ordinateur.

    Voici ma version, que j'espère "avec partage".
    Attention, j'ai aussi fait joujou avec la syntaxe, histoire de (re)voir à quel point on pouvait faire aussi rigolo que père Curry. Je suis assez satisfait.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    open List
    
    let ( @$ )f x = f x
    let ( @@ ) f g x = f @$ g x
    
    let seq n = Array.to_list @$ Array.init n @$ ( + ) 1
    
    let sumrec = 
      let rec sumrec fond = function
        0 -> [fond]
      | 1 -> [1::fond]
      | n -> concat @$ map (fun i -> sumrec ((n - i) :: fond) (n - i)) @$ seq (n - 1)
      in sumrec []
    
    let () = 
      iter (print_newline @@ iter @$ Printf.printf "%d\t") @$ sumrec @$ read_int ()
    Sur mon ordinateur, compilé en natif, avec comme entrée "21", cette version met 10 secondes, alors que la version de gorgonite en met 14. Ma version consomme 43 Mo de mémoire, celle de gorgonite en demande 100.

    Je dois avouer que je suis un peu décu, je m'attendais à des résultats plus différents encore. Je dois avoir raté quelque chose.

  13. #13
    LLB
    LLB est déconnecté
    Membre expérimenté
    Inscrit en
    Mars 2002
    Messages
    967
    Détails du profil
    Informations forums :
    Inscription : Mars 2002
    Messages : 967
    Points : 1 410
    Points
    1 410
    Par défaut
    Citation Envoyé par Jedai
    Les plus exigeants d'entre vous auront peut-être remarqué que pour l'instant aussi bien ma solution que celle de LLB répètent inutilement certains appels à la fonction auxiliaire (csums dans mon cas, sumrec dans le cas de LLB) durant la récursion... Ces appels pourraient être éliminés en mémorisant les résultats intermédiaires.
    Tout à fait.

    Et juste pour exemple, j'ai traduit le code de Jedai en F# : (fichier complet et exécutable)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #light
    let sums n =
      let rec a = Array2.init (n+1) (n+1) populate
      and populate k l =
        lazy if k = 0 then [[]]
             else [for x in 1 .. min k l ->> [for xs in a.[k-x, x].Force() -> x :: xs]]
      a.[n,n].Force()
    
    Sys.argv.(1) |> int_of_string |> sums |> print_any
    Populate est le nom de la fonction d'initialisation du tableau. L'opérateur |> correspond en gros au pipe du Shell (donc, le $ de Haskell à l'envers ). Et comme on fait de la paresse alors que le langage est strict par défaut, il faut appeler la méthode Force (et le mot-clé "lazy").

    Utiliser l'évaluation paresseuse n'est pas dans mes habitudes, et je n'y aurais probablement pas pensé sans Jedai, mais je suis plutôt satisfait du résultat. Le code n'est finalement pas trop compliqué.

    (Évidemment, les solutions données pour OCaml fonctionnent aussi bien sous F#)

  14. #14
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Je trouve d'ailleurs qu'un tableau est plus adapté qu'une liste pour une solution de mémoization générique comme utilisé ici (évidemment, la définition récursive de la liste est très élégante, et si on a besoin de calculer sums plusieurs fois de suite la solution est bien meilleure).

    En écrivant concatMap à la main (et oui, pas de déforestation chez nous :p), la consommation mémoire passe à 33 Mo, soit trois fois moins que la version intiale.

    (Évidemment, les solutions données pour F# fonctionnent aussi bien sous OCaml)

  15. #15
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par bluestorm
    > Mais la mémoire devrait éclater avec toutes les listes intermédiaires, non ?
    > En fait il y a un "truc" (dont devrait aussi bénéficier Gorgonite, c'est
    > pourquoi je suis étonné qu'il ait un problème à 17 éléments), réfléchissez
    > bien !!

    Le 'truc' me semble être le partage implicite des listes.
    Tout à fait, le partage implicite des listes rend cette liste infinie moins chère temporairement que la fonction type Gorgonite (effectivement tu as raison, il n'y a pas partage dans son cas, non plus qu'avec ma fonction équivalente d'ailleurs).

    Malheureusement la fonction de bluestorm donne des résultats fantaisistes... pour l'instant.

    --
    Jedaï

  16. #16
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Citation Envoyé par bluestorm
    Je trouve d'ailleurs qu'un tableau est plus adapté qu'une liste pour une solution de mémoization générique comme utilisé ici (évidemment, la définition récursive de la liste est très élégante, et si on a besoin de calculer sums plusieurs fois de suite la solution est bien meilleure).
    Vu la taille réelle que pourra atteindre cette liste, j'ai jugé qu'une liste était parfaitement appropriée et puis une liste infinie c'est quand même nettement plus beau qu'un tableau, même fonctionnel, et comme tu le dis, c'est surtout approprié si on a besoin de refaire le calcul très souvent, sinon on localise la mémoization à une seule invocation.

    Citation Envoyé par bluestorm
    (Évidemment, les solutions données pour F# fonctionnent aussi bien sous OCaml)
    Hmm... Il n'y a pas de compréhension de liste sous OCaml, je ne suis pas sûr non plus que la paresse y soit implémenté exactement de la même façon (quoique ça soit probable), il va donc falloir modifier un peu le F# pour obtenir le même résultat en OCaml.

    Par ailleurs je répète ici que pour benchmarker vos fonction, il vaut mieux leur faire afficher la longueur de la liste résultat : si vous affichez la liste elle-même, la seule chose que vous benchmarkez c'est la vitesse d'affichage dans votre console...

    --
    Jedaï

  17. #17
    Membre éprouvé
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Points : 1 104
    Points
    1 104
    Par défaut
    Oui évidemment (enfin maintenant qu'on me le dit), ce n'est pas
    sumrec ((n - i) :: fond) (n - i)
    mais sumrec (i :: fond) (n - i)
    Et en plus, elle renvoie des solutions identiques, donc elle est vraiment à jeter

    Cependant, j'estime bénéficier de circonstances particulièrement atténuantes :
    1) la faute vient initialement de gorgonite, j'ai juste recopié son code;
    2) mes tests fort sérieux ont montré que pour 0, 1 et 2, le résultat était correct.

    Hmm... Il n'y a pas de compréhension de liste sous OCaml
    http://oandrieu.nerim.net/ocaml/#pa_compr
    (#light ressemble à une directive préprocesseur. Tous les coups sont permis !)

    si vous affichez la liste elle-même, la seule chose que vous benchmarkez c'est la vitesse d'affichage dans votre console...
    dans /dev/null ? ^^

  18. #18
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Ok, pas si tu rediriges la sortie vers /dev/null.

    Voici en tout cas une version correcte du code de bluestorm, bien qu'il génère encore les n-uplets et pas les ensembles :
    Code OCaml : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    open List
     
    let ( @$ )f x = f x
    let ( @@ ) f g x = f @$ g x
     
    let seq n = Array.to_list @$ Array.init n @$ ( + ) 1
     
    let sum = 
      let rec sumrec fond = function
        0 -> [fond]
      | n -> concat @$ map (fun i -> sumrec (i :: fond) (n - i)) @$ seq n
      in sumrec []
     
    let () = 
      iter (print_newline @@ iter @$ Printf.printf "%d\t") @$ sum @$ read_int ()

    --
    Jedaï

  19. #19
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Points : 18 679
    Points
    18 679
    Par défaut
    bon, c'était la saint gorgonite cette nuit on dirait... pour infos, le coup du (n-i) au lieu de i était une erreur de recopie (mon code était un peu plus moche, car je testais des listes mutables & cie pour éviter de dupliquer les bouts de listes )


    Code ocaml : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    let rec build_list n m = if n>m then [] else n::(build_list (n+1) m);;
    let min a b = if a<b then a else b;;
    
    let sums n =
    	let rec sumrec n m =
    		match n with
    			0 -> [[]]
    			|n -> 
    				let intervalle = build_list 1 (min m n) in
    				List.concat (
    					List.map (
    						fun i -> List.map (fun li -> i::li) 
    						(sumrec (n-i) i)
    					) 
    					intervalle
    				)
    	in
    	sumrec n n
    ;;
    
    let rec print_list l =
    	match l with
    		[] -> ()
    		|a::q -> Printf.printf "%d " a ; print_list q
    ;;
    
    let rec print lst = 
    	match lst with
    		[] -> ()
    		|a::q -> Printf.printf "[ " ; print_list a ; Printf.printf "] \n" ; print q
    ;;
    
    let main () =
    	Printf.printf "%d\n" (List.length (sums (int_of_string Sys.argv.(1))))
    ;;
    
    main ();;


    finalement, je suis revenu sur une solution proche de celle de Jedai et LLB (j'avais testé jusqu'à 2... et n'avait pas fait gaffe qu'au delà, ça renvoyait les nuplets et non les ensembles)

    pour infos, cela met
    + 19ms pour calculer le résultat pour 21
    + 10s pour 54
    + stack overflow pour 55
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  20. #20
    LLB
    LLB est déconnecté
    Membre expérimenté
    Inscrit en
    Mars 2002
    Messages
    967
    Détails du profil
    Informations forums :
    Inscription : Mars 2002
    Messages : 967
    Points : 1 410
    Points
    1 410
    Par défaut
    Citation Envoyé par bluestorm
    http://oandrieu.nerim.net/ocaml/#pa_compr
    (#light ressemble à une directive préprocesseur. Tous les coups sont permis !)
    En pratique, ce n'est pas un préprocesseur dans F# (il n'y en a hélas pas encore), c'est plutôt géré dans le parseur. Pour les différences avec Caml, il y en a un certain nombre dans mon code (alors que copier coller le code Caml dans F# fonctionne sans changer le moindre caractère). À titre indicatif, voilà les différences entre les 2 langages utilisées dans mon code :
    • #light pour utiliser l'indentation et s'affranchir de certains mots-clés ("in", etc.)
    • list comprehensions (à noter que le ->> fait un append d'une liste, alors que -> ajoute un élément)
    • l'opérateur |>, qui se définit par : let (|>) x f = f x. On peut donc l'avoir aussi en Caml, mais c'est une pratique très courante en F# (il y a également l'opérateur <| qui correspond au $ de haskell et << et >> qui servent à composer les fonctions).
    • a.Force() est utilisable à la place de Lazy.force a.
    • Petite différence dans la bibliothèque standard : on utilise Array2 pour les tableaux à 2 dimensions (et petite différence dans l'accès au tableau).
    • print_any, qui affiche n'importe quelle valeur
    • lazy (faut mettre des parenthèses autour dans Caml) a un comportement un peu différent. La récursion mutuelle que j'ai faite entre le tableau et sa fonction d'initialisation est acceptée dans F#. En Caml, ça me renvoie systématiquement un "This kind of expression is not allowed as right-hand side of `let rec'". Je ne sais pas si on peut le contourner simplement.

    L'esprit est le même, mais il y a quand même pas mal de raccourcis syntaxiques. Maintenant, si tu arrives à avoir le comportement de F# en utilisant Camlp4, je serais vraiment ravi.



    EDIT

    Non, décidément, je n'arrive pas à convenir ma fonction en Caml. Le problème vient de la récursion mutuelle entre le tableau et son initialisation. Même un code aussi simpliste que :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    let rec a = Array.init 10 foo
    and foo x = 0;;
    This kind of expression is not allowed as right-hand side of `let rec'
    est refusé. Quelqu'un a une solution (paresseuse et sans faire d'effet de bord) ?

Discussions similaires

  1. Réponses: 3
    Dernier message: 23/07/2015, 08h26
  2. Réponses: 8
    Dernier message: 20/03/2015, 16h21
  3. Réponses: 9
    Dernier message: 03/11/2009, 17h39
  4. Rechercher les nombres dont la somme est donnée
    Par TMuet dans le forum Intelligence artificielle
    Réponses: 2
    Dernier message: 17/08/2009, 18h17
  5. Extraire lignes dont le debut est identique
    Par Raoul555 dans le forum Shell et commandes GNU
    Réponses: 3
    Dernier message: 19/05/2007, 12h01

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo