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

[LLB]

Depuis un mois, il y a un installeur .msi (je suppose qu'on ne peut pas l'utiliser sous Linux). Avant, il y avait un fichier zip avec tout dedans : sources, Makefile, README et même install-mono.sh.

Je regarde si c'est encore accessible quelque part. Sinon, je l'uploade dans l'après-midi.

[Jedai]

Envoyé par LLB

Code :

Fait gaffe, dans ta version tu utilises filter() là où j'utilise takeWhile()... Ca ne fait pas la même chose : takeWhile() va s'arrêter dès que la condition n'est plus vraie, filter() va tester tous les éléments de la liste. A l'origine j'utilisais un filter() (ou à peu près) et cette solution était particulièrement lente, même plus lente que la première solution !!
Par ailleurs, j'ai un petit doute, regarde ce qui se passe pour 4 avec ta fonction.

--
Jedaï

[gorgonite]

reçu, je testerai ce soir... ça complétera les tests


et pour prolog, personne ne sait comment lancer ce qu'il faut en une ligne de commande avec swi ou gprolog ?

[Trap D]

Envoyé par gorgonite

reçu, je testerai ce soir... ça complétera les tests


et pour prolog, personne ne sait comment lancer ce qu'il faut en une ligne de commande avec swi ou gprolog ?

Salut
I'm back
Si c'est pour mon programme naïf en Prolog, tu fais
time(decomposition(N, L)).
Je cherche à améliorer la rapidité de mon prog mais de toute façon, la méthode est lente, puisque je pars des listes déjà fabriquées et je dois vérifier avant de mémoriser que la liste n'esite pas déjà.
Au passage, j'ai corrigé une fuite mémoire

[Jedai]

Après petit test de la version F# avec tableau pour mémoization, on utilise 44s pour 70 (avec -O3), contre 5s sur ma machine pour la même version en Haskell.

--
Jedaï

[gorgonite]

Envoyé par Jedai

Après petit test de la version F# avec tableau pour mémoization, on utilise 44s pour 70 (avec -O3), contre 5s sur ma machine pour la même
version en Haskell.

au fait de quelle machine disposes-tu ?

perso, c'est un portable centrino 1,6Ghz (simple coeur), 2Go Ram sous Linux (le reste n'a pas vraiment d'influence )

[gorgonite]

Envoyé par Trap D

Si c'est pour mon programme naïf en Prolog, tu fais
time(decomposition(N, L)).

ben sur ma machine avec swiprolog, ça donne 140ms pour 15, et stack overflow au-delà...

Envoyé par Trap D

Au passage, j'ai corrigé une fuite mémoire

dans le programme prolog ou c ?
si c'est le prolog, je veux bien la correction

[LLB]

Envoyé par Jedai

Fait gaffe, dans ta version tu utilises filter() là où j'utilise takeWhile()...

Oui, merci !
Il n'y a pas de takeWhile dans la lib, je l'ai recodée. Et l'erreur, c'était juste dans la comparaison (j'ai pas dû poster la bonne version tout à l'heure).

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let rec takeWhile f = function
  | e::l when f e -> e :: takeWhile f l
  | _ -> []
let rec sums =
  let get x n =
    if x = n then [[]]
    else Seq.nth (n - x) sums |> Lazy.force |> takeWhile (fun k -> List.hd k <= x)
  let init n = lazy [for x in 1 .. n ->> [for xs in get x n -> x :: xs]]
  Seq.init_infinite init

> Seq.nth 5 sums;;
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]]

Pour les performances, ça se comprend que Haskell soit meilleur sur l'évaluation paresseuse. T'as testé sous Windows ou Unix ?

D'après un benchmark, les performances de F# sous Windows sont du même ordre que celles obtenues avec ocamlopt. Je pense donc qu'il est possible d'améliorer le temps (peut-être en utilisant un algo plus "classique", sans le lazy ?)

Ceux qui ont testé F# ont dû se rendre compte que mon code génère un warning. C'est dû à la récursion dans la définition de la valeur (liste ou tableau), puisque c'est potentiellement risqué (Caml l'interdit). Le warning peut s'enlever avec le flag --no-warn 40.

EDIT
J'ai ajouté lazy, c'est un peu mieux. Je viens de me rendre compte qu'il y a un type LazyList dans la lib standard. Je vais tester.

[Jedai]

Envoyé par LLB

Pour les performances, ça se comprend que Haskell soit meilleur sur l'évaluation paresseuse. T'as testé sous Windows ou Unix ?

Sous Windows (XP) avec le dernier F# et .Net2 .

Je dis tout de suite que OCaml est normalement plus rapide qu'Haskell sur les mêmes algorithmes en général (parce qu'Haskell est paresseux et que ça rajoute un cout réel à toutes les opérations, d'où d'ailleurs l'importance de la qualité du compilateur). Je ne doute pas qu'il soit possible d'écrire un code plus rapide en OCaml ou F# qu'en Haskell, mais nous regardons aussi l'élégance et la facilité de maintenance des programmes (sinon nous pouvons tout de suite jeter l'éponge comme le code de Millie nous l'a montré !). Et j'aime à penser que jusqu'ici, à l'exception peut-être du code "à itérateur" (et encore, comparé au C++ ou au C...), la plupart des programmes fonctionnels restaient élégants et compréhensible, et compact également, ce qui a son importance pour la maintenance.

--
Jedaï

[Jedai]

Envoyé par gorgonite

au fait de quelle machine disposes-tu ?

perso, c'est un portable centrino 1,6Ghz (simple coeur), 2Go Ram sous Linux (le reste n'a pas vraiment d'influence )

Portable avec Pentium M 1.73GHz (simple coeur), 1 GO de Ram sous Windows XP (j'ai tendance à faire tourner beaucoup de programme en parallèle, la RAM est donc bien occupée habituellement, la plupart des tests se sont donc fait avec 450-500 Mo de RAM libre).
(Il n'est pas vraiment à moi, mais je le squatte régulièrement disons... )

--
Jedaï

[gorgonite]

Envoyé par Jedai

j'ai tendance à faire tourner beaucoup de programme en parallèle, la RAM est donc bien occupée habituellement, la plupart des tests se sont donc fait avec 450-500 Mo de RAM libre

perso, sur ma machine aussi... j'ai apache2, mysql, postgresql, nagios, munin, monit, openssh-server, vsftpd, cups ; divers gadgets gnome, des extensions firefox pour "tricher" à des jeux en ligne, etc

mais il doit bien rester 1Go de dispo

[Jedai]

Envoyé par LLB

D'après un benchmark, les performances de F# sous Windows sont du même ordre que celles obtenues avec ocamlopt. Je pense donc qu'il est possible d'améliorer le temps (peut-être en utilisant un algo plus "classique", sans le lazy ?)

Tu devrais peut-être essayer mon algorithme avec itérateur, il n'y a pas vraiment de paresse dedans (sauf le unfoldr, mais le genNext() lui-même est assez strict), et il est plutôt efficace normalement.

--
Jedaï

[Jedai]

Donc pour l'instant, j'ai quelques résultats de bench pour n=64 (ce qui est le maximum que je parviens à atteindre avec le ML de Gorgonite) :

LLB 1 (F#, algorithme naïf)

real 1m44s
---
Dividee 1 (algorithme naïf)

real 0m39.782 s
---
Dividee 3 (générateur)

real 0m36s
---
LLB 3 (F# avec itérateur)

real 0m24.212s
---
LLB 2 (F# avec matrice de mémoization paresseuse)

real 0m14.300s
---
Gorgonite 1 (algorithme de base)

real 0m11.542s
---
Jedaï 1 (algorithme de base, en Haskell)

real 0m5.1s
---
Gorgonite 2 (OCaml avec memoization dans une matrice (n+1)x(n+1) )

real 0m3.7s
---
Dividee 2 (avec memoization)

real 0m3.12s
---
Jedaï 2 (avec tableau de (0,0) à (n,m)

real 0m3.09s
---
Jedaï 5 (avec liste infinie)

real 0m2.1s
---
Jedaï 3 (avec itérateur et unfoldr)

real 0m1.7s
---
Jedaï 6 (avec itérateur et unfoldr, mais dans le bon sens !)

real 0m0.62s
---
TrapD 2 (itère, ne mémorise pas)

real 0m0.486s
---
Millie 2 (itère, ne mémorise pas, mais affiche (redirigé vers >nul bien sûr) -O3, l'algorithme employé a malheureusement été démontré faux depuis ces mesures)

real 0m0.300s

J'ai compilé le F# avec -O3, le Haskell avec -O2.
Je suis en train de corriger les temps pour le F#, dont la première exécution est nettement plus lente que les suivantes. (EDIT : Vous pouvez considérer que c'est fait)

Pour Jedaï 3 (avec itérateur et unfoldr), j'ai également 14s pour 80, 56s pour 90, contre 0.45s pour 80 et 0.62s pour 90 avec Millie 2 et 5s pour 80 et 19s pour 90 avec TrapD 2. Jedaï 6 améliore un peu les choses avec 4.8s pour 80 et 17.2 s pour 90.

Pour les version de Dividee, j'ai utilisé Python 2.5.1 et j'ai mesuré séparément chacune des versions de façon à éviter les problèmes d'allocation et de swap. La version 4 de Dividee est par contre impossible à mesurer sur mon ordinateur vu la place qu'elle prend en mémoire.

--
Jedaï

[LLB]

Voilà, je viens de traduire "bêtement" ton itérateur en F#. J'ai même pas essayé de comprendre le fonctionnement, je regarderai ça plus tard.

En effet, il est plus efficace que les autres que j'ai implémentés.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#light

let rec sums n =
  let first = List.init n (fun _ -> 1)
  let gen prec =
    match genNext(n, prec) with
     | Some x -> Some (x, x)
     | None -> None
  first :: (Seq.unfold gen first |> Seq.to_list)

and genNext = function
 | _, [] -> None
 | _, [x] -> None
 | n, li -> Some (aux(n, li, n) |> fst)

and aux = function
  | k, [x], _ -> if x = 1 then [], true else [x-1], true
  | k, x::xs, m -> match aux(k-x, xs, x) with
                    | nxs, true -> if x < m
                                   then (x+1) :: List.init (k-x-1) (fun _ -> 1), false
                                   else x::nxs, true
                    | nxs,false -> x::nxs, false

Sys.argv.(1) |> int_of_string |> sums |> List.length |> print_int

J'avais aussi fait quelques tests sur le principe de la matrice lazy, en utilisant les traits impératifs, mais ça n'apporte quasiment rien.

[millie]

J'ai ajouté des optimisations très sympatique qui devraient faire un peu gagner de temps :

Code C++ :

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
 
/*affiche un vecteur*/
void afficher(std::vector<int> & list)
{
    std::cout<<"[";
    for(int i =0; i <list.size()-1; i++)
        std::cout<<list[i]<<", ";
    std::cout<<list[list.size()-1];
 
    std::cout<<"], ";
}
 
/*calcul la somme d'un vecteur*/
int somme(std::vector<int> & list)
{
    int total = 0;
    for(int i=0; i<list.size(); i++)
        total += list[i];
    return total;
}
 
/*met tout le vecteur à 1 sauf le premier élément à n*/
void mettrePremierN(std::vector<int> & list, int n)
{
    list[0] = n;
    for(int i = 1; i<list.size(); i++)
        list[i] = 1;
}
 
/*genère la combinaison suivante suivant un critère très particulier*/
void genererSuivant(std::vector<int> & list)
{
    int currentMax = 0;
    int pos = 0;
 
    for(pos=0; pos<list.size()-1; pos++)
        if(list[pos+1]< list[pos])
            currentMax = pos+1;
 
    if(pos == list.size()-1)
        list[currentMax]++;
}
 
/*génère l'ensemble des solutions dont la taille du vecteur vaut taille*/
void generationSolution(int n, int taille)
{
    static std::vector<int> list;
    list.resize(taille);
    for(int i=0; i<taille; i++)
        list[i] = 1;
 
    for(int i=n/taille; i<=n+1-taille; i++)
    {
        int total = 0;
        mettrePremierN(list, i); //somme vaut i>=n+1-taille
                                    //dans la boucle, ça sera au maximum = taille * i
        while(total<=n && list[0]==i)
        {
            total = somme(list);
            if(total == n)
                afficher(list);
            if(total >=n)
                break;
            genererSuivant(list);
        }
    }
 
}
 
/*génère l'ensemble des solutions*/
void generationSomme(int n)
{
    for(int taille = n; taille>0; taille--)
        generationSolution(n, taille);
}
 
int main()
{
    generationSomme(5);
    return 0;
}

Notamment, la ligne : for(int i=n/taille; i<=n+1-taille; i++)
qui était avant : for(int i=1; i<=n; i++)

J'ai également dégagé les allocations dynamiques à chaque boucle avec std::vector.

[Trap D]

J'ai modifié le calcul et sans mémorisation des résultats, voici ce que j'obtiens
10 : 42 solutions durée 0.000 s
20 : 627 solutions durée 0.000s
30 : 5 604 solutions durée 0.000s
40 : 37 338 solutions durée 0.015 s
50 : 204 226 solutions durée 0.032 s
70 : 4 087 968 solutions durée 0.625 s
80 : 15 796 476 solutions durée 2.610 s
90 : 56 634 173 solutions durée 9.938 s
100 : 190 569 292 solutions durée 34.250 s

Le bon est important entre 90 et 100 je ne sais pas pourquoi.

[edit] on peut l'expliquer en remarquant que le nombre de décompositions de 100 est 933 fois plus grand que celui de 50, donc la durée est 900 fois plus importante pour 100 que pour 50
[/edit]

Le code de la fonction de calcul est très simple, c'est une simple boucle tant que

Code c :

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
38
39
void travail(int n)
{
	int total = n;
	int ptcur = n-1;
	int *tab = malloc(n * sizeof(int));
	int i;
	int nb = 0;
	// initialisation
	for(i = 0; i < n; i++)
		tab[i] = 1;
 
	while (tab[0] != n)
	{
		if (total >= n)
		{
			if (total == n)
			{
				// on a trouve une solution
				//edit(tab, ptcur);
				nb++;
			}
			// on revient un cran en arrière
			total -= tab[ptcur];
			ptcur--;
			tab[ptcur]++;
			total ++;
		}
		else
		{
			ptcur++;
			tab[ptcur] = tab[ptcur-1];
			total += tab[ptcur];
		}
	}
	nb++;
	//edit(tab, 0);
	printf("Nombre de solutions %d\n", nb);
	free(tab);
}

[edit] correction du nombre de résultats pour 100.

[Trap D]

En modifiant légèrement le code et en choisisssant les options de compilation pour optimiser la vitesse, (/O2) j'obtiens
pour 50 : 0.016 s
pour 70 : 0.250 s
pour 80 : 1.016 s
pour 90 : 3.781 s
pour 100 : 13.104 s (soit une durée divisée par près de 3).

le code :

Code :

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
38
39
40
41
42
43
44
45
void travail(int n)
{
	int total = n;
	int ptcur = n-1;
	int i;
	int nb = 0;
	int *tab = malloc(n * sizeof(int));
	// initialisation
	for(i = 0; i < n; i++)
		tab[i] = 1;

	while (tab[0] != n)
	{
		if (total > n)
		{
			// on revient un cran en arrière
			total -= tab[ptcur];
			--ptcur;
			++tab[ptcur];
			++total;
		}
		else
		if (total == n)
		{
			// on a trouve une solution
			//edit(tab, ptcur);
			++nb;
			// on revient un cran en arrière
			total -= tab[ptcur];
			--ptcur;
			++tab[ptcur];
			++total;
		}
		else
		{
			++ptcur;
			tab[ptcur] = tab[ptcur-1];
			total += tab[ptcur];
		}
	}
	nb++;
	//edit(tab, 0);
	printf("Nombre de solutions %d\n", nb);
	free(tab);
}

[dividee]

Personne n'a encore posté de version Python alors voilà:

sums1 = algorithme de base (celui de LLB)
sums2 = version avec mémoization
sums3 = un générateur (un peu comme une version lazy)
sums4 = version non récursive; programmation dynamique

Les temps que j'obtiens sur mon T2400 @ 1.83 Ghz:
sums1(64): 36 s
sums2(64): 2.5 s
sums3(64): 34 s
sums4(64): 8.7 s

Au niveau de l'utilisation mémoire, je n'ai pas fait de mesure précise, mais en gros sums4 demande plus de 1,2 GB de mémoire (!); sums2 environ 600 MB, sums1 200 MB, et sums3 est bien sur la plus économique, son utilisation mémoire ne dépendant que de la profondeur de la pile d'appels (tant qu'on n'a pas besoin de toutes les combinaisons en même temps).

Je suis étonné que la version 4 (prog.dyn.) utilise deux fois plus de mémoire et est plus lent que la mémoization; j'ai pourtant essayé de ne générer que les combinaisons qui seront utilisées. Il y a certainement moyen de faire mieux.

Code python :

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# version de base
def sums1(n):
  def sumrec(n,m):
    if n == 0: return [()]
    else:
      return [(i,)+j for i in xrange(1,min(m,n)+1) for j in sumrec(n-i,i)]
  return sumrec(n,n)
 
# avec mémoization
def memoize(f):
  mem={}
  def memo(*args):
    if args not in mem:
      mem[args] = f(*args)
    return mem[args]
  return memo
 
def sums2(n):
  @memoize
  def sumrec(n,m):
    if n == 0: return [()]
    else:
      return [(i,)+j for i in xrange(1,m+1) for j in sumrec(n-i,min(i,n-i))]
  return sumrec(n,n)
 
# avec un générateur
def sums3(n):
  def sumrec(n,m):
    if n == 0: yield ()
    else:
      for i in xrange(1,min(m,n)+1):
        for j in sumrec(n-i,i): yield (i,)+j
  return sumrec(n,n)
 
# version plus impérative (?)
def sums4(nn):
  mem = {(0,0): [()]}
  for n in xrange(1,nn):
    for m in xrange(1,min(n,nn-n)+1):
      mem[(n,m)] = [(i,)+j for i in xrange(1,m+1) for j in mem[(n-i,min(i,n-i))]]
  return [(i,)+j for i in xrange(1,nn+1) for j in mem[(nn-i,min(i,nn-i))]]
 
import timeit
print "sums1",
print timeit.Timer("sums1(64)","from __main__ import sums1").timeit(1)
print "sums2",
print timeit.Timer("sums2(64)","from __main__ import sums2").timeit(1)
print "sums3",
print timeit.Timer("for x in sums3(64): pass","from __main__ import sums3").timeit(1)
print "sums4",
print timeit.Timer("sums4(64)","from __main__ import sums4").timeit(1)

[Jedai]

Bon, je pense qu'on peut encore améliorer la mémoization avec liste infinie, mais en attendant voici le programme le plus rapide que j'ai créé pour l'instant, sur le principe de l'itérateur, mais meilleur que le précédent en cela qu'on n'a pas besoin de lire toute la liste à tous les coups car je donne les possibilités sous forme de n-uplet ascendant ce coup-ci :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
module Main where
import System
import Data.List

-- fonction générant la liste complète des possibilités
sums n = first : unfoldr (maybe Nothing (\x -> Just (x,x)) . genNext) first
    where first = replicate n 1

-- fonction pour passer d'une possibilité à la suivante
genNext [] = Nothing
genNext (x:[]) = Nothing
genNext li = Just $ aux 0 li
    where
      aux 0 (x:xs) = aux x xs
      aux n li@(x:y:xs) = if y > x
                          then replicate (n-1) 1 ++ (x+1 : tail li)
                          else aux (n+x) $ tail li
      aux n li@(x:[]) = replicate (n-1) 1 ++ [x+1]

main = getArgs >>= print . length . sums . read . (!!0)

Vous pouvez vous référer à mon post de bench pour constater que cette version est vraiment rapide...

--
Jedaï

[Jedai]

Envoyé par LLB

Voilà, je viens de traduire "bêtement" ton itérateur en F#. J'ai même pas essayé de comprendre le fonctionnement, je regarderai ça plus tard.

En effet, il est plus efficace que les autres que j'ai implémentés.

Pas selon mes tests... D'un autre côté mes tests ont révélé que le compilateur F# n'effectuait pas proprement la fusion du length et du unfold, ce qui signifie que tu perds l'avantage en place mémoire que te conférait l'itérateur. Essaie de compter les possibilités "à la main" plutôt qu'avec length . unfold.

--
Jedaï