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

**yan** · 13/12/2007, 15h49

ha oui tien,
en ajoutant l'optimization des 1+1+....+1, et en evitant plusieur appèle récurssive, j'améliore nettement les perf

je passe pour 100 de 30s à 5-6s

Code C++ :

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
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
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <iterator>
 
//#define AFFICHER
int nbvalue(0);
typedef unsigned int DecompType;
 
 
 
inline void afficher(const std::vector<DecompType> & myVect,const DecompType & nb)
{
    nbvalue++;
    #ifdef AFFICHER
	if (nb==0) return;
    std::cout<<"[";
    std::copy(myVect.begin(),myVect.begin()+nb-1,std::ostream_iterator<int>(std::cout,", "));
    std::cout<<myVect[nb-1]<<"]\n";
    #endif
}
 
//fonction récussive
inline void generate(std::vector<DecompType> & myVect,const DecompType & reste ,const  DecompType & nb_precedent,const DecompType & level)
{
if (reste ==1)
	{
	myVect[level]=1;
	afficher(myVect,level+1);
	}
else
	{
	//on interdit que le chiffre que l'on va traiter puisse etre plus grand que le précédent
		for (DecompType i=std::min(reste,nb_precedent);i>1 ;--i)
		{
		//on met le chii=ffre courant à i
		myVect[level] = i;	    
		//on traite le prochain chiffre avec le reste
		//si reste ==i alors la somme des chiffres est bien ègale au chiffre de dépard
		//sinon on passe au chiffre suivant
		if (reste==i) 
			afficher(myVect,level+1);
		else
			generate(myVect,reste-i,i,level+1);
		}
	//cas ou le nombre courant est mis à 1
	//td::vector<int>::iterator it = myVect.begin()+level;
	myVect[level]=1;
	myVect[level+reste-1]=1;
	afficher(myVect,level+reste);
	}
 
}
 
int main()
{
    clock_t t1=std::clock();
    DecompType n =100;
    std::vector<DecompType> myVect(n);
    DecompType level (0);
    generate(myVect,n,n,level);
    clock_t t2=std::clock();
    std::cout<<nbvalue<<std::endl;
    std::cout<<double(t2-t1)/CLOCKS_PER_SEC<<std::endl;
return 0;
}

**yan** · 13/12/2007, 22h46

j'ai comparé avec le code de Steki-kun:
pour 100
moi : 0m1.656s
Steki-kun: 0m2.304s

pour 130 :
moi : 0m56.012s
Steki-kun: 1m3.160s

**Steki-kun** · 14/12/2007, 00h39

Tu as pris ma version impérative compilée avec ocamlopt ?
En tout cas c'est intéressant, la différence augmente en proportion bien plus faible que le nombre de partitions donc les complexités sont sensiblement les mêmes. J'aimerais bien voir d'où vient la différence si la technique est la même : tu as le code de ta version là ?

**yan** · 14/12/2007, 00h56

Envoyé par Steki-kun

Tu as pris ma version impérative compilée avec ocamlopt ?
En tout cas c'est intéressant, la différence augmente en proportion bien plus faible que le nombre de partitions donc les complexités sont sensiblement les mêmes. J'aimerais bien voir d'où vient la différence si la technique est la même : tu as le code de ta version là ?

oui sous ubuntu. Par contre je ne sait pas si il faut ajouter des option a la compilation. je ne connait pas ocamlopt

Pour le code je l'ai mis juste avant.
[edit]
les résultats ne sont pas les même car ce n'est pas le même PC.

**Steki-kun** · 14/12/2007, 01h18

OK ! Pour les options, rien à rajouter à ocamlopt

-unsafe à la limite ca accélerera un chouia les acces tableaux...
Edit : Je viens de changer un chouia en remplaçant comme JMB le paquet de 1 dans l'implémentation impérative par leur nombre, je descends à 53s pour n=130, 2.1s pour n=100. A ce niveau là, time ne permet plus de faire la comparaison raisonnablement, je crois qu'on peut dire ex aequo

Les boucles à changer :

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
34
let visit a m q = 
  sol := add !sol one;
  let e = if m = q then q-1 else q in
    for i = 1 to e do
      Printf.printf "%d+" a.(i)
    done;
    if m = q then 
      print_endline (string_of_int a.(q))
    else
      (for i = 1 to m-q-1 do
	 Printf.printf "1+"
       done;
       print_endline "1")

let rec copy_loop a n m x =
  if n <= x then n, m
  else 
    (a.(m) <- x;
     copy_loop a (n-x) (m+1) x)

let rec main_loop a n m q =
  if !debug then visit a m q;
  if a.(q) = 2 then
    main_loop a n (m+1) (q-1)
  else
    if q = 0 then ()
    else
      begin
	let x = a.(q) - 1 in
	  a.(q) <- x;
	  let n,m = copy_loop a (m-q+1) (q+1) x in
	    a.(m) <- n;
	    main_loop a n m (if n = 1 then m-1 else m)
      end

**yan** · 17/12/2007, 01h10

j'ai réussi a diviser par 2.5/3 le temps

Code C++ :

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
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <iterator>
 
//#define AFFICHER
int nbvalue(0);
typedef int DecompType;
 
inline void afficher(const std::vector<DecompType> & myVect,const DecompType   & end)
{
    nbvalue++;
 
    #ifdef AFFICHER
 
    std::cout<<"[";
    std::copy(myVect.begin(),myVect.begin()+end,std::ostream_iterator<int>(std::cout,", "));
    std::cout<<*(myVect.begin()+end)<<"]\n";
    #endif
}
 
template <DecompType debut >
struct myFOR;
 
 
//class template qui empêche que le chiffre courant soit suppèrieur au chiffre d'avant
//et lance une boucle for pour décrementer le chiffre
//traite le cas chiffre == 1
template <DecompType reste >
struct generate2
{
    template<DecompType nb_precedent>
    static inline void faire(std::vector<DecompType> &myVect,const DecompType &   level)
        {
        //std::cout<<"generate2"<<std::endl;
        myFOR< reste<nb_precedent? reste:nb_precedent >::template faire<reste> (myVect,level);
        myVect[level]=1;
 
        myVect[level+reste-1]=1;
        afficher(myVect,level+reste-1);
        }
 
 
};
//SPECIALISATION
// si  le reste vaut 0 on affiche le résultat
template < >
struct generate2<0>
    {
 
    template<DecompType nb_precedent>
    static inline void faire(std::vector<DecompType> &myVect,const DecompType  &  level)
        {
       //    std::cout<<"generate2<1>"<<std::endl;
        myVect[level]=1;
        afficher(myVect,level+1);
        }
    };
//BOUCLE FOR "déroulé"
//decremente le nombre courant et demande une generation pour le chiffre suivant
// ou affiche quand le rest vaut 0
template <DecompType Valeur >
struct myFOR
{
    template<DecompType    reste>
    static inline void faire(std::vector<DecompType> &myVect,const DecompType & level)
    {
        myVect[level] = Valeur;
        if (reste==Valeur)
            afficher(myVect,level);
        else
           generate2<reste-Valeur>::template faire<Valeur>(myVect,level+1);
 
 
        myFOR<Valeur-1>::template faire<reste>(myVect,level);
 
    };
 
};
//SPECIALISATION
//quand Valeur vaut 1 la boucle est fini
template < >
struct myFOR<1>
{
 template<DecompType    reste>
    static inline void faire(std::vector<DecompType> &myVect,const DecompType   & level)
    {
    };
};
 
 
int main(int argc,char ** argv)
{
    const DecompType n =100;
    std::vector<DecompType> myVect(n);
    myVect[0]=n;
    nbvalue=0;
    clock_t t1=std::clock();
        generate2<n>::faire<n>(myVect,0);
    clock_t t2=std::clock();
    std::cout<<nbvalue<<std::endl;
    std::cout<<double(t2-t1)/CLOCKS_PER_SEC<<std::endl;
 
return 0;
}

Mais bon c'est à cout de déroulement de boucle (pseudo metaprog, je ne mis connait pas encore assez, c'est mon premier)... La je suis obligé de connaitre le nombre avant le lancement...
Mais cette méthode peut accélérer un morceau du calcul. Par exemple des qu'il reste 50, j'appel ce nouveau code

Je ne sait pas si d'autre langages permettent de faire ca..

surtout en fonctionnel

**Steki-kun** · 17/12/2007, 01h20

euh STOP je t'arrête là, avec les mêmes techniques je calcule la factorielle en O(1)... Là tu fais faire les calculs à ton compilo à la place de ton programme, alors évidemment il reste plus grand chose à faire en runtime. C'est pas le but de l'exercice

**yan** · 17/12/2007, 01h36

Envoyé par Steki-kun

euh STOP je t'arrête là, avec les mêmes techniques je calcule la factorielle en O(1)... Là tu fais faire les calculs à ton compilo à la place de ton programme, alors évidemment il reste plus grand chose à faire en runtime. C'est pas le but de l'exercice

Oui et non

il donne et peut afficher toute les solution!!!

Envoyé par millie

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é

maintenabilité = bof
simplicité = bof
optimisé = beaucoup

Ici la boucle for et les appelles récursive sont déroulé.
Il reste donc le plus couteux : l'accès en mémoire!!!
Le but est juste de montrer ce que l'on peut faire en C++
En faite, je me demande surtout si c'est possible de faire ça en langage fonctionnelle.

Mais je suis d'accord que ce code n'apporte rien a part l'optimisation

**LLB** · 17/12/2007, 01h54

Envoyé par Mongaulois

En faite, je me demande surtout si c'est possible de faire ça en langage fonctionnelle.

Le système de templates de C++ est un langage fonctionnel (et turing-complet).

Common Lisp possède un système de macros puissants, il est peut-être possible de faire ça aussi, à la compilation.

**Steki-kun** · 17/12/2007, 02h07

Reste que l'utilisation de trucs de ce genre ne relève pas vraiment d'une opposition de style impératif / fonctionnel. C'est assez rarement un bon design de programmation puisque ça ne marche pas pour tout n et que l'air de rien ca fait méchamment grossir l'exécutable.
Et au risque d'être cynique, je dirais que si vraiment on veut dérouler des piles de 500 appels sans le faire "à la main", quel que soit le langage, on peut toujours étant donné un programme P qui fait un nombre constant de boucles et d'appels récursifs, faire un programme qui va écrire sur la sortie standard une version entièrement déroulée du programme P... Que le compilateur t'offre la possibilité de le faire pour toi -- moyennant incantations templatisantes de ton code original, c'est un autre problème

**yan** · 17/12/2007, 11h18

Envoyé par Steki-kun

Reste que l'utilisation de trucs de ce genre ne relève pas vraiment d'une opposition de style impératif / fonctionnel. C'est assez rarement un bon design de programmation puisque ça ne marche pas pour tout n et que l'air de rien ca fait méchamment grossir l'exécutable.

C'est un style de programmation a part entière que te permet le C++. Aprés il ne faut pas en abuser c'est sur. La c'est un gros abut de ma part, j'avoue. Mais je pourrai m'en servire pour optimiser qu'une partie du code. Par exemple des qu'un chiffre est à 5.

Envoyé par Steki-kun

Et au risque d'être cynique, je dirais que si vraiment on veut dérouler des piles de 500 appels sans le faire "à la main", quel que soit le langage, on peut toujours étant donné un programme P qui fait un nombre constant de boucles et d'appels récursifs, faire un programme qui va écrire sur la sortie standard une version entièrement déroulée du programme P... Que le compilateur t'offre la possibilité de le faire pour toi -- moyennant incantations templatisantes de ton code original, c'est un autre problème

Bien sur, mais je ne me voit pas dérouler a la main les 190 569 292 solutions. Qu'un language le permet, ajouter beaucoup d'interet.
Dans un code, il y as trés souvent des morceaux où les variables sont connu. Mais le compilot ne va pas spécialement dérouler les boucle.... mais avec ce style de programmation tu peut l'obliger. Dans le même style dans ce code :

Code C++ :

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

1
2
3
myTab tabres,tab1,tab2,tab3;//tableau avec N element
....//init de tab1,tab2 et tab3
tabres = tab1+tab2*tab3

avec ce même style de programmation, on peut obliger le compilot a le traduire par :

Code C++ :

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

1
2
3
4
5
6
 
tabres.resize(Tabtmp2.res());
for (int i=0;i<tab1.res();++i)
{
tabres[i]  = tab1[i] + tab2[i] * tab3[i];
}

au lieu de

Code C++ :

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
 
//multiplication
myTab Tabtmp1(tab2.size());
for (int i=0;i<Tabtmp1.res();++i)
{
Tabtmp1[i]  = tab2[i] * tab3[i];
}
//addition
myTab Tabtmp2(Tabtmp1.size());
for (int i=0;i<Tabtmp2.res();++i)
{
Tabtmp2[i]  = tab1[i] + Tabtmp1[i];
}
//egale
tabres.resize(Tabtmp2.res());
for (int i=0;i<Tabres.res();++i)
{
tabres[i]  =  Tabtmp2[i];
}

**Garulfo** · 17/12/2007, 18h35

Envoyé par LLB

[...]
Common Lisp possède un système de macros puissants, il est peut-être possible de faire ça aussi, à la compilation.

C'est possible. Les macros récursives existent.
Mais c'est très peu recommandé d'en abuser.

Sérieusement mongaulois, il va falloir faire un effort sur l'orthographe

Vis-à-vis des tes optimisations, sais-tu que les performances sont rarement un problème sur des projets ? Et qu'il vaut mieux investir dans une bonne conception et une bonne documentation que dans une bonne performance ? Il me semble que tu n'as fait ça que pour le challenge cependant. Ce qui est fort bien dans ce cas. Mais la lisibilité est très basse aussi.

**Jean-Marc.Bourguet** · 17/12/2007, 18h39

Envoyé par Garulfo

C'est possible. Les macros récursives existent.
Mais c'est très peu recommandé d'en abuser.

L'abus serait moins grand que l'abus des templates...

Et si on veut citer d'autres langages complets a la compilation, il y a aussi au moins Forth, PL/I, la plupart des macro-assembleurs. Meme les macros du C peuvent etre poussee a bout pour faire bien plus que ce que croient la plupart des gens (voir par exemple la section de boost sur le preprocesseur).

**yan** · 17/12/2007, 19h08

Pour ce que ca interesse:
un petit bench sur un problème entre différents language
http://www.ffconsultancy.com/ocaml/r...languages.html

**millie** · 17/12/2007, 19h11

Envoyé par Mongaulois

Pour ce que ca interesse:
un petit bench sur un problème entre différents language
http://www.ffconsultancy.com/ocaml/r...languages.html

En même temps, les mini bench, ça montre tout et surtout n'importe quoi

**Jedai** · 17/12/2007, 19h34

Envoyé par Mongaulois

Pour ce que ca interesse:
un petit bench sur un problème entre différents language
http://www.ffconsultancy.com/ocaml/r...languages.html

D'un autre côté ce n'est pas non plus vraiment un "mini"-bench, c'est un moyen.

Comparaison avec Haskell :
http://augustss.blogspot.com/2007/11...askell-vs.html

--
Jedaï

**Garulfo** · 17/12/2007, 21h47

Envoyé par millie

En même temps, les mini bench, ça montre tout et surtout n'importe quoi

C'est un très bon exemple.
Ce code montre qu'on peut avoir élégance et efficacité avec un programme qui a besoin d'efficacité (c'est un ray tracer). Et l'exemple qui suit en Haskell (cf. le message de Jedai) montre que ocaml n'est pas le seul dans ce cas.

Je l'ai déjà posté. Flying Frog Consultancy utilise ocaml pour du calcul scientifique.

**millie** · 17/12/2007, 21h56

C'est un exemple sur un petit code... Je ne sais pas si ça vaut grand chose.

Par exemple, Java va forcement avoir de mauvais statistiques car Hot Spot ne va pas être vraiment utilisé puisque l'exécution est courte donc le résultat est forcement biaisé

Et dans l'industrie, je ne suis pas sûr que des applications aussi courtes courent les rues.

Si ce code était intégré à une vrai application et qu'il y aurait des milliers d'appels alors Hot Spot optimiserait/compilerait en natif le code donc les statistiques ne seraient plus les mêmes.

**Jean-Marc.Bourguet** · 17/12/2007, 21h58

Envoyé par Jedai

D'un autre côté ce n'est pas non plus vraiment un "mini"-bench, c'est un moyen.

200 lignes pour l'entrée la plus longue, moyen? C'est pas un mini-bench, c'est micro-bench.

**yan** · 18/12/2007, 12h26

Envoyé par Jean-Marc.Bourguet

200 lignes pour l'entrée la plus longue, moyen? C'est pas un mini-bench, c'est micro-bench.

Alors as tu un vrai bench??

Pour moi un bench entre languagene peut montrer que la relation verbosité-rapidité d'un language par rapport à un problème. Et c'est en ca que le lien que je donne me semble un bon bench. Tous comme les codes créé dans ce thread

Je pense que pour l'instant,
il y as toujours une solution plus rapide en C et C++,mais souvent avec un code plus verbeux, car ces compilateur est plus evolué,optimisé. Mais d'autre language seront toujours plus adapté à un problème donné, avec un code plus lissible et de trés bonne performance.

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

Défis langages fonctionnels

Discussions similaires

Partager

Partager