Discussion :

[alex_pi]

Sur le forum algorithmique (http://www.developpez.net/forums/d59...aison-tableau/), un gentil PO demande comment récupérer les sous ensemble d'un ensemble trié. Réponse de Jedai :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
{- Le code demandé calcule en fait les parties d'un ensemble 
modélisé comme une liste ordonnée .
Le nom anglais pour Parties() est powerset, nous l'utiliserons ici -}
 
-- powerset prend une liste d'élément et renvoie une liste de listes
powerset :: [a] -> [[a]]
-- la seule partie de l'ensemble vide est l'ensemble vide
powerset [] = [[]]
-- P( {x1} u {x2, x3, .. xn } ) = (U_{p in P( { x2, .. xn } ) {x1} u p) u P( { x2, .. xn } ) 
powerset (x:xs) = map (x:) psXs ++ psXs
  where psXs = powerset xs

On peut faire un peu plus rapide et moins gourmant en mémoire avec :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
powerset [] = [[]]
powerset (x:xs) = interleave (map (x:) psXs) psXs
  where psXs = powerset xs
 
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs

Je n'arrive pas à voir en quoi la seconde solution est plus efficace. D'un point de vue de Cameleux, elle me parrait moins efficace puisqu'on parcourt les deux liste completement au lieu de partager la seconde. J'imagine que ça doit venir de la paresse, mais je n'arrive pas à mettre le doigt sur un argument valable.

[SpiceGuid]

Le : est lazy en Haskell.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

interleave (x:xs) ys = x : interleave ys xs

Le (x:xs) n'est jamais évalué, donc on a moins de : qu'avec ++.
Joli cas de déforestation.

[alex_pi]

Ça ne vient pas de la parresse, ça vient de ce que ++ est List.append alors que interleave ressemble plus à List.rev_append.

Je ne suis pas sur de comprendre :-\ Ni interleave ni ++ ne sont monolytiques (enfin de ce que j'en comprends), et de toutes façons, à la fin, on force la liste finale completement (on voudrait la voir hein :-)), et donc (toujours si je ne m'abuse), toutes les listes intermédiaires.
J'arrive vraiment pas à voir :-\

[SpiceGuid]

Ok, ça vient de la paresse: le cons est lazy en Haskell.
(voir mon message édité)

edit: à mieux y réfléchir je ne vois pas en quoi c'est plus paresseux que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

append (x:xs) ys = x : append xs ys

mais bon Jedaï va nous éclairer hein ?

[alex_pi]

Le : est lazy en Haskell.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

interleave (x:xs) ys = x : interleave ys xs

Le (xs) n'est jamais évalué, donc on a moins de : qu'avec ++.
Joli cas de déforestation.

Oué, il est lazy, mais la "paresse" est utile quand tu n'évalues pas ou éventuellement plusieurs fois à des endroits différents. Si tu évalues exactement une fois (ce qui me semble être le cas), ça ne change rien par rapport à de l'évaluation stricte (par valeur). Et dans ce cas, la seconde version est moins bonne que la première. Mais tu as raison, attendons Jedaï :-)

[Jedai]

Je n'arrive pas à voir en quoi la seconde solution est plus efficace. D'un point de vue de Cameleux, elle me parrait moins efficace puisqu'on parcourt les deux liste completement au lieu de partager la seconde. J'imagine que ça doit venir de la paresse, mais je n'arrive pas à mettre le doigt sur un argument valable.

Tout dépend de l'utilisation de la fonction que l'on fait. Il est néanmoins très fréquent qu'on souhaite simplement parcourir l'ensemble des parties plutôt que de garder l'ensemble en mémoire (pour la raison fort simple que la mémoire nécessaire est énorme).

Dans la première version, psXs se retrouve entièrement en mémoire lorsqu'on atteint la moitié de la liste "powerset (x : xs)", ceci parce que le premier élément de psXs est toujours référencé par la suite de la liste. Autrement dit, quel que soit l'usage qu'on fait de powerset, la complexité mémoire est toujours O(2^n).
Dans la seconde version, le premier élément de psXs peut être libéré dès qu'on a consulté les deux premiers éléments de la liste produite par powerset, et ceci récursivement, il s'ensuit que la complexité mémoire de la seconde version dans le cas d'un parcours simple (un consommateur approprié, traitant la liste comme un flux) est en O(n), bien plus raisonnable.
Comme je l'ai dit, ce cas d'utilisation est de toute façon très fréquent, si ce n'est le plus fréquent dans les programmes réels, il fait donc sens d'optimiser la fonction pour cet usage quitte à sacrifier un peu de mémoire et de vitesse pour le cas rare (l'avantage de la première version est de toute façon insignifiant par rapport à la croissance démesuré d'une exponentielle).

C'est simple de toute façon :
testez :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
import Data.List
 
powerset = ...
 
main = print . foldl' (+) 0 . map length . powerset $ [1..23]

Avec les deux versions de powerset, et surveillez l'usage mémoire (vous pouvez lancez l'exécutable avec les options "+RTS -sstderr -RTS" pour avoir quelques statistiques utiles.

--
Jedaï

[alex_pi]

ok merci :-)

[Jedai]

Pour ceux qui auraient la flemme, je mets les statistiques sur ma machine avec le powerset de [1..24] :
Première version (avec ++) :

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
./powerset +RTS -sstderr 
201326592
1,550,096,572 bytes allocated in the heap
415,786,872 bytes copied during GC (scavenged)
      1,472 bytes copied during GC (not scavenged)
109,477,888 bytes maximum residency (8 sample(s))
 
       2957 collections in generation 0 (  0.77s)
          8 collections in generation 1 (  0.82s)
 
        211 Mb total memory in use
 
  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    4.88s  (  4.91s elapsed)
  GC    time    1.59s  (  1.77s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    6.46s  (  6.68s elapsed)
 
  %GC time      24.6%  (26.4% elapsed)
 
  Alloc rate    317,883,432 bytes per MUT second
 
  Productivity  75.4% of total user, 73.0% of total elapsed

Seconde version (avec interleave) :

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
./powerset +RTS -sstderr 
201326592
2,760,343,416 bytes allocated in the heap
  3,239,592 bytes copied during GC (scavenged)
        184 bytes copied during GC (not scavenged)
     40,960 bytes maximum residency (1 sample(s))
 
       5266 collections in generation 0 (  0.01s)
          1 collections in generation 1 (  0.00s)
 
          2 Mb total memory in use
 
  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    3.78s  (  3.76s elapsed)
  GC    time    0.01s  (  0.04s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    3.79s  (  3.79s elapsed)
 
  %GC time       0.3%  (0.9% elapsed)
 
  Alloc rate    730,203,798 bytes per MUT second
 
  Productivity  99.6% of total user, 99.5% of total elapsed

Juste une petite différence, comme vous le voyez

--
Jedaï

[alex_pi]

Et si tu conserves la liste en mémoire, empechant la magie du GC, ça donne quoi (à la rigueur avec des plus petites valeurs ;-))

[SpiceGuid]

À oui quand même... 2Mb au lieu de 211Mb

Franchement, Haskell c'est trop sioux pour moi.
Toute cette science du partage des données va à l'encontre de l'intuition du débutant (selon laquelle la question du partage c'est le problème du GC).

[Jedai]

Et si tu conserves la liste en mémoire, empechant la magie du GC, ça donne quoi (à la rigueur avec des plus petites valeurs ;-))

750 Mo d'occupation pour la première version, 14s
900 Mo pour la seconde, 16s

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
main = do
  let parts = powerset [1..24]
  print . sum . map sum $ parts
  print . sum . map length $ parts

Donc effectivement, sur des grosses listes à la limite de ce qu'il est possible de faire tenir en mémoire, si tu stockes l'intégralité de la liste en mémoire, la seconde version est plus lente (et c'est logique, comme tu l'as pointé, on fait 2 fois moins de (:) dans la première version). Evidemment si tu montes à 26 éléments, aucune des deux versions ne tiendra plus sur ma RAM... et la seconde version sera la seule utilisable quitte à oublier le partage et à refaire un appel à powerset à chaque fois qu'on en a besoin, méthode qui nous permet de redescendre à 9s et 2Mo de mémoire occupé avec le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
main = do
  print . sum . map sum $ powerset [1..24]
  print . sum . map length $ powerset [1..24]

--
Jedaï

[Garulfo]

Bon alors… si j'ai bien compris, en fait cela ne tient pas à la paresse mais à l'usage du GC surtout -_-

Mais je me demande, quid de la vitesse d'exécution ?
La mémoire est moins en demande, c'est clair, mais pourquoi la vitesse est-elle moindre ? En développant à la main, il me semble que j'ai plus d'appels. J'ai fait ça pour [1..2] et [1..3] bien sûr. Me suis-je trompé ? ou peut-être n'est-ce que plus tard que se voit la différence ? J'avoue que j'ai fait ça à la va-vite.

[Jedai]

Bon alors… si j'ai bien compris, en fait cela ne tient pas à la paresse mais à l'usage du GC surtout -_-

Plus ou moins, mais sans la paresse, tu ne pourrais pas commencer à parcourir la liste avant d'avoir fini de la calculer, et donc tu ne pourrais pas libérer le début de la liste avant d'avoir alloué toute la liste...

Mais je me demande, quid de la vitesse d'exécution ?
La mémoire est moins en demande, c'est clair, mais pourquoi la vitesse est-elle moindre ? En développant à la main, il me semble que j'ai plus d'appels. J'ai fait ça pour [1..2] et [1..3] bien sûr. Me suis-je trompé ? ou peut-être n'est-ce que plus tard que se voit la différence ? J'avoue que j'ai fait ça à la va-vite.

La vitesse est supérieure dans mes exemples, justement parce que la demande mémoire est inférieure (les collections nécessaires sont plus étalées et moins importantes, l'allocation nécessaire est inférieure).

Néanmoins il est vrai que dans un langage strict, où il n'y aurait pas de gain potentiel de mémoire, la seconde version est moins bonne parce qu'elle effectue plus de cons ( : ), elle effectue exactement le même nombre d'appel à powerset par contre.

--
Jedaï

[gorgonite]

Plus ou moins, mais sans la paresse, tu ne pourrais pas commencer à parcourir la liste avant d'avoir fini de la calculer, et donc tu ne pourrais pas libérer le début de la liste avant d'avoir alloué toute la liste...

faux... c'est assez courant de commencer le traitement avant d'avoir terminé la mise en place des données. (du moins dans les langages visant des bonnes perfs )

[GnuVince]

faux... c'est assez courant de commencer le traitement avant d'avoir terminé la mise en place des données. (du moins dans les langages visant des bonnes perfs )

Ça se fait, par contre, comme l'explique Hal Abelson dans le leçon 6a des vidéos SICP, la logique est entre-mêlée. Le programme a une bonne performance, mais son fonctionnement est plus compliqué à comprendre en un coup d'oeil qu'une version qui sépare les tâches. Pour atteindre de bonnes performances avec le second modèle, ils introduisent les streams (évaluation paresseuse) qui permettent d'obtenir les performances du premier modèle avec la clarté du second.

Edit: Grammaire douteuse

[gorgonite]

Ça se fait, par contre, comme l'explique Hal Abelson dans le leçon 6a des vidéos SICP, la logique est entre-mêlée. Le programme a une bonne performance, mais son fonctionnement est plus compliqué à comprendre en un coup d'oeil qu'une version qui sépare les tâches.

tout dépend du niveau d'abstraction de ton code... en C++, tu peux avoir énormement d'abstraction dans ton code, et pourtant une gestion très précise et bas niveau des perfs

les streams (évaluation paresseuse) qui permettent d'obtenir les performances du premier modèle avec la clarté du second.

ben je n'ai pas dit que ça ne revenait pas à faire des streams un peu accélérés

[Jedai]

faux... c'est assez courant de commencer le traitement avant d'avoir terminé la mise en place des données. (du moins dans les langages visant des bonnes perfs )

J'ai dit que tu ne pourras pas commencer à parcourir la liste avant d'avoir fini de la générer... Et ça c'est toujours vrai dans un langage strict avec des listes strictes.

Bien sûr que si un programmeur dans un langage strict doit parcourir l'ensemble des parties d'un ensemble de grande taille, il optera pour une approche mélangeant traitement et génération s'il n'est pas fou !

Cette approche a cependant le désavantage de sacrifier la simplicité et la modularité de ma solution. S'il a de la chance, il pourra au moins utiliser des "flots" pour simuler les listes paresseuses, mais cette solution est moins naturelle dans les langages stricts.

tout dépend du niveau d'abstraction de ton code... en C++, tu peux avoir énormement d'abstraction dans ton code, et pourtant une gestion très précise et bas niveau des perfs

Je serais curieux de voir une version C++ de cette solution.

--
Jedaï

[SpiceGuid]

c'est assez courant de commencer le traitement avant d'avoir terminé la mise en place des données.

Sans doute, mais ce qui est bluffant c'est de pouvoir réaliser cette optimisation en seulement 2 lignes à partir de la version naïve.
Pour moi c'est ça qui fait la différence entre un bon langage de prototypage (à la fin tout sera réimplémenté en C) et un excellent langage de prototypage (on zappe le C car à la fin on supprime les goulots d'étranglement de la performance).

[gasche]

Cette approche a cependant le désavantage de sacrifier la simplicité et la modularité de ma solution.

Je ne suis pas convaincu : en quoi cette approche est-elle plus modulaire ? Elle est pratique parce que Haskell possède une bibliothèque bien fournie sur les listes paresseuses, mais un langage "généralement strict" avec une riche bibliothèque pour les listes paresseuses (ou flots) aurait le même intérêt dans ce cas, non ?

[Jedai]

Je ne suis pas convaincu : en quoi cette approche est-elle plus modulaire ? Elle est pratique parce que Haskell possède une bibliothèque bien fournie sur les listes paresseuses, mais un langage "généralement strict" avec une riche bibliothèque pour les listes paresseuses (ou flots) aurait le même intérêt dans ce cas, non ?

Tu serais gentil de citer la phrase qui suit immédiatement ta citation :

S'il a de la chance, il pourra au moins utiliser des "flots" pour simuler les listes paresseuses, mais cette solution est moins naturelle dans les langages stricts.

En bref, exactement comme tu l'as dit, un bon langage fournira des "flots", mais la plupart des programmeurs stricts ne sont pas conscient de l'existence de cette solution, ce qui limite son emploi. Et ils emploient donc une approche mélant traitement et génération, moins modulaire et lisible... (je pense que le "moins modulaire" est évident dans ce cas non ? Tu ne peux réutiliser le consommateur ou le générateur dans un autre contexte, parce qu'ils ne sont pas séparés)

--
Jedaï