conversion de valeur "compile time"

Version imprimable

Bonjour

J'ai implémenté un systeme de conversions de grandeurs physiques (représentées en "double")
Je veux que les conversions se fassent autant que possible à la compilation.

voici l'implémentation actuelle (dans une en-tête):
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 46 47 48 49 50 51 class Converter { public: constexpr Converter(double factor, double offset) : factor_(factor), offset_(offset) {} constexpr double toHuman(double siVal) const { return (siVal - offset_) / factor_; } constexpr double toSI(double humanVal) const { return humanVal * factor_ + offset_; } private: double factor_; double offset_; }; // converts to and from Pa static Converter pressureHPa (100, 0); static Converter pressurPSI (6894.75729 , 0); // converts to and from m3 static Converter volumeL (1/1000.0, 0); static Converter volumeML (1/1000000.0, 0); static Converter volumeGal (0.00378541, 0); // converts to and from m3/s static Converter flowLPS (1/1000.0, 0); static Converter flowLPM (1/60000.0, 0); static Converter flowLPH (1/3600000.0, 0); static Converter flowCCM (1/60000000.0, 0); static Converter flowGPM (0.0000630901964, 0); // converts to and from °K static Converter tempC (1, 273.15); static Converter tempF (5.0/9.0, 459.67); // converts to and from s static Converter timeM (60, 0); static Converter timeH (3600, 0); static Converter timeD (84600, 0); // converts to and from kg static Converter massLb (0.453592, 0); static Converter massG (0.001, 0);
des variables statiques dans un en-tête ça ne me plait pas du tout, car l'allocation est faite dans toutes les unités de traduction.
Cependant déclarer ces variables "extern" va empecher la conversion en compiletime.

Idéalement j'aurais fait une classe template avec factor et offset passés en paramètres et les 2 fonctions statiques, mais on ne peut apparemment pas avoir de parametres autres que des entiers (j'ai besoin de double)

je pourrais m'inspirer de std::ratio, mais avec des valeurs comme 273.15, je suis bloqué.

Est-ce qqun connait un astuce ?
merci

14/04/2013, 07h17
koala01
Salut,

En fait, je vois mal comment tu pourrais obtenir un résultat "compile time" :aie:

Typiquement, on va lancer le convertisseur qui va nous demander:
- l'unité d'origine
- l'unité de destination
- la valeur d'origine
et le convertisseur nous indiquera alors la valeur dans l'unité de destination.

Mais tout cela sera, j'ai presque envie de dire, d'office "dynamique", parce qu'on ne peut jamais prévoir quelle sera l'unité d'origine ni quelle sera la valeur introduite.

La seule solution pour que ces valeurs soient définies à la compilation consisterait à modifier systématiquement le code pour indiquer l'unité de départ, l'unité de destination et la valeur à convertir, avant de compiler le tout... Tu avoueras qu'on fait mieux comme système :D

Mais peut etre est-ce ce que tu souhaites réellement :question:

Bonjour
merci pour ta réponse

pour l'aspect langage, j'ai trouvé l'astuce que je cherchais: passer par une class traits. j'aurais du y penser avant (voir code ci-dessous).

Pour l'aspect dynamique, c'est sur que si la valeur n'est pas connue à la compilation, ça va être tendu. Dans le pire des cas, la fonction est inline, et vu la grande complexité du calcul, c'est vraiment pas la mort !:mouarf:
J'ai quand même pas mal de cas de figure ou j'introduis une constante litterale en paramètre.
par exemple

Code:

timeM::toSI(2)

ne devrait-il pas générer la constante 120 dans le code compilé?

voici la nouvelle solution

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
template<class UnitsTraits>
class Converter {
public:
 
    static constexpr double factor = UnitsTraits::factor;
    static constexpr double offset = UnitsTraits::offset;
 
 
    static constexpr inline double toHuman(double siVal) {
        return siVal / factor - offset;
    }
 
    static constexpr inline double toSI(double humanVal) {
        return (humanVal + offset) * factor;
    }
 
};
 
 
 
#define DECL_UNIT_CONVERTER(name, fact, off) \
struct name##_traits { \
    static constexpr double factor = fact; \
    static constexpr double offset = off; \
}; \
typedef Converter<name##_traits> name;
 
 
 
// converts to and from Pa
DECL_UNIT_CONVERTER(pressureHPa, 100.0, 0.0)
DECL_UNIT_CONVERTER(pressurePSI, 6894.75729, 0.0)
 
// converts to and from m3
DECL_UNIT_CONVERTER(volumeL, 1/1000.0, 0.0)
DECL_UNIT_CONVERTER(volumeML, 1/1000000.0, 0.0)
DECL_UNIT_CONVERTER(volumeGal, 0.00378541, 0.0)
 
// converts to and from m3/s
DECL_UNIT_CONVERTER(flowLPS, 1/1000.0, 0.0)
DECL_UNIT_CONVERTER(flowLPM, 1/60000.0, 0.0)
DECL_UNIT_CONVERTER(flowLPH, 1/3600000.0, 0.0)
DECL_UNIT_CONVERTER(flowCCM, 1/60000000.0, 0.0)
 
// converts to and from °K
DECL_UNIT_CONVERTER(tempC, 1.0, 273.15)
DECL_UNIT_CONVERTER(tempF, 5/9.0, 459.67)
DECL_UNIT_CONVERTER(tempR, 5/9.0, 0.0)
 
// converts to and from s
DECL_UNIT_CONVERTER(timeM, 60.0, 0.0)
DECL_UNIT_CONVERTER(timeH, 3600.0, 0.0)
DECL_UNIT_CONVERTER(timeD, 86400.0, 0.0)
 
// converts to and from kg
DECL_UNIT_CONVERTER(massLb, 0.453592, 0.0)
DECL_UNIT_CONVERTER(massG, 0.001, 0.0)
 
 
#undef DECL_UNIT_CONVERTER

14/04/2013, 18h26
koala01

Citation:

Envoyé par remitbo

Bonjour
merci pour ta réponse

pour l'aspect langage, j'ai trouvé l'astuce que je cherchais: passer par une class traits. j'aurais du y penser avant (voir code ci-dessous).

Pour l'aspect dynamique, c'est sur que si la valeur n'est pas connue à la compilation, ça va être tendu. Dans le pire des cas, la fonction est inline, et vu la grande complexité du calcul, c'est vraiment pas la mort !:mouarf:
J'ai quand même pas mal de cas de figure ou j'introduis une constante litterale en paramètre.
par exemple

Code:

timeM::toSI(2)

ne devrait-il pas générer la constante 120 dans le code compilé?

Pourquoi le devrait il :question: tu viens de dire qu'entre l'inlining des fonctions et la grande complexité des algorithmes, ce ne serait pas la mort ;)

@koala01: constexpr est là pour ca.

@OP: Ton dernier code me semble pas mal, il doit faire le travail que tu attends. On peut faire légèrement différement, mais le principe reste le même :

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
 
template<class Unit> struct factor;
template<class Unit> struct offset;
 
template<class Unit>
struct converter
{
  static constexpr inline double toHuman(double from)
  { return from / factor<Unit>::value - offset<Unit>::value; }
 
  static constexpr inline double toSI(double from)
  { return (from + offset<Unit>::value) * factor<Unit>::value; }
};
 
#define CONVERTER_UNIT(name, factor_value, offset_value) \
struct name {}; \
template<> struct factor<name> \
{ static constexpr double value = factor_value; }; \
template<> struct offset<name> \
{ static constexpr double value = offset_value; }; \
};
 
CONVERTER_UNIT(temp_F, 5/9.0, 459.67)
 
converter<temp_F>::toSI(2);

14/04/2013, 20h15
remitbo

@Flob90:ta solution me parait plus générique, cependant je préfère garder la mienne qui est un peu moins verbeuse à l'utilisation.

@koala01: j'aurais du préciser que:
1: je suis seul utilisateur du code (ce n'est pas une bibliothèque, juste une petite API interne)
2: au moment de la compilation les unités sont connues (ce n'est pas un systeme dynamique) et l'une des unités est toujours du SI. Je fais des calculs en SI pour éviter les conversions et les possibilités d'erreurs associées, mais les valeurs présentées sont dans des unités plus lisibles que les °K ou les m3/s
3: la valeur à convertir n'est connues qu'en de rares occasions (ex valeurs par defaut).
C'est clair que le "compile time" n'est pas un must absolu, mais je ne vois pas de raison de m'en passer quand l'occasion se présente :mrgreen:

Merci à tous les deux
15/04/2013, 00h26
koala01

Citation:

Envoyé par remitbo

@Flob90:ta solution me parait plus générique, cependant je préfère garder la mienne qui est un peu moins verbeuse à l'utilisation.

@koala01: j'aurais du préciser que:
1: je suis seul utilisateur du code (ce n'est pas une bibliothèque, juste une petite API interne)
2: au moment de la compilation les unités sont connues (ce n'est pas un systeme dynamique) et l'une des unités est toujours du SI. Je fais des calculs en SI pour éviter les conversions et les possibilités d'erreurs associées, mais les valeurs présentées sont dans des unités plus lisibles que les °K ou les m3/s
3: la valeur à convertir n'est connues qu'en de rares occasions (ex valeurs par defaut).
C'est clair que le "compile time" n'est pas un must absolu, mais je ne vois pas de raison de m'en passer quand l'occasion se présente :mrgreen:

Merci à tous les deux

A vrai dire, dans le cas présent, je vois une raison de s'en passer dans le sens où tu vas perdre du temps à la compilation (même si l'on est d'accord pour dire que ce n'est pas grand chose ;)) pour gagner finalement très peu de chose à l'exécution :aie:

Comprenons nous bien: je ne suis pas, loin s'en faut, opposé aux constantes de compilation.

Mais de là à demander explicitement au compilateur d'en calculer alors que cela ne prend pour ainsi dire pas de temps au processeur de faire le calcul, je ne peux m'empêcher de penser que c'est peut être un peu exagéré :aie:

@Flob oui, constexprest là pour cela...

Mais n'oublie malgré tout pas que constexprest comme inline: cela ne fait que demander quelque chose au compilateur, libre à lui de décider de faire aboutir cette demande, ou non ;)

Si, pour une raison ou une autre (plusieurs return :question:) le compilateur ne peut pas considérer une expression comme étant constante, il considérera l'expression comme étant toute simple (en gros: l'appel de la fonction d'origine) ;)
15/04/2013, 17h21
Médinoc

Ah, il ne crache pas d'erreur si une fonction déclarée constexpr n'est pas "inlinable" (par manque de meilleur mot) ?

Edit: Attends, ça ne peut pas être vrai si on a le droit d'utiliser tout résultat de fonction constexpr là où des constantes sont attendues (case, paramètres template entiers...)
15/04/2013, 21h00
koala01
En fait, tu auras une erreur disant que le compilateur essaye d'utiliser une valeur qui n'est pas constante, uniquement si tu essayes d'utiliser une constexpr dans un contexte "constant".

Mais, si l'expression n'est pas "constantifiée" (ouahh, le joli mot que je viens d'inventer :mgreen:) et que tu l'utilise dans un contexte qui n'a pas besoin d'une constante de compilation, le compilateur devrait laisser passer la chose sans te faire le moindre reproche ;)

Par exemple (pour autant que j'ai bien compris le principe) la fonction
Code:

1 2 3 constexpr int factorial(int i){ return i>0 ? i*factorial(i-1):1; }
peut etre constantifiée, entre autre, parce qu'il n'y a qu'un seul return.

Par contre, la même fonction sous la forme de
Code:

1 2 3 4 5 constexpr int factorial(int i){ if(i==0) return 1; return i* factorial(i-i); }
ne pourra pas être considérée comme une expression constante, mais sera considérée comme une fonction "tout à fait classique".

La première version pourrait donc parfaitement servir dans un contexte dans lequel tu as besoin d'une constante de compilation (par exemple un switch casse), mais la deuxième ne provoquera une erreur que dans un contexte dans lequel tu as besoin d'une constante de compilation ;)

Dans tous les autres cas, ce ne sera "ni plus ni moins" qu'une fonction "tout ce qu'il y a de plus normal" (bien qu'utilisant la récursivité) ;)
16/04/2013, 01h45
Iradrille

Citation:

Envoyé par koala01

Mais, si l'expression n'est pas "constantifiée" (ouahh, le joli mot que je viens d'inventer :mgreen: ) et que tu l'utilise dans un contexte qui n'a pas besoin d'une constante de compilation, le compilateur devrait laisser passer la chose sans te faire le moindre reproche ;)

C'est le principe des constexpr : soit ça passe en "compile time" car tout est connu et il y a moins de récursions que le max fixé, soit c'est évalué à l'exécution (et ça ne passe pas en constexpr). ;)

Ici ça ne peut fournir qu'un gain de performance ;)
16/04/2013, 10h26
koala01

Citation:

Envoyé par Iradrille

C'est le principe des constexpr : soit ça passe en "compile time" car tout est connu et il y a moins de récursions que le max fixé, soit c'est évalué à l'exécution (et ça ne passe pas en constexpr). ;)

Ce que je voulais surtout dire à Médinoc pour qu'il comprenne, c'est que, soit ca passe en constante de compilation et tu peux l'utiliser partout (là où tu as besoin d'une expression constante, comme là où tu n'en as pas besoin), soit ca ne passe pas en constante de compilation, et tu ne peux l'utiliser que là où tu n'auras pas besoin d'une expression constante.

Citation:

Ici ça ne peut fournir qu'un gain de performance ;)

Je te l'accorde, mais...

Toutes choses étant au demeurant égales, il faut rester conscient que ce que tu reçois d'une main, tu le payes de l'autre.

Les gains de performances que tu observeras seront donc fortement contre balancés par l'augmentation du temps de compilation, la "compréhensibilité" du code et la complexité supplémentaire du développement.

Dés lors, je me demande sincèrement quel est l'intérêt de faire une "figure de style" à essayer de transformer une valeur "normale" en constante de compilation si ce n'est pas absolument nécessaire.

J'ai donc envie de comparer les constexpr essions à la récursivité : Toutes deux sont de très bonnes choses si elles sont utilisées à bon escient.

La récursivité par exemple n'a qu'un intérêt "stylistique" (et pédagogique éventuellement) lorsqu'elle est utilisée pour calculer une factorielle ou une exponentielle, parce qu'elle peut parfaitement être remplacée par une boucle qui serait sommes toutes plus naturelle mais présente un fort intérêt lorsqu'il est question de résoudre, par exemple, des tours de hannoï.

Les constexpr essions sont tirées du même tonneau: Les utiliser "pour la figure de style" ne présente, à mon sens, qu'un intérêt limité à cause de leur "cout" (tous problèmes confondus) par rapport à leur "gain".

Par contre, je reconnais parfaitement que le fait d'y recourir lorsque l'on en a réellement besoin est totalement justifié ;)

La question dans le cadre de cette discussion est donc "a-t-on réellement besoin des constexpr, ou n'est-ce qu'une figure de style:question:".

Mon sentiment personnel est que ce n'est, dans le cadre particulier présenté par remitbo, qu'une figure de style dont on porrait parfaitement se passer ;)
16/04/2013, 20h47
Flob90

@koala01: Dans le cas de conversion d'unité, tu admettras quand même que le compilateur est capable de l'évaluer à la compilation, si les paramètres sont connus à cette instant (ce n'est qu'un return après tout). Que ce cas de figure (paramètre connus ou non) puisse ou non se présenter c'est à l'op de le déterminer, et à priori il considère que c'est le cas :

Citation:

J'ai quand même pas mal de cas de figure ou j'introduis une constante litterale en paramètre.

Pourquoi s'en priver ?

Pour ce qui est de la récursivité, le caractère naturel ou non, je ne vois pas comment tu peux affirmer objectivement qu'une façon de faire est plus naturelle qu'une autre.
16/04/2013, 21h15
koala01

Citation:

Envoyé par Flob90

Pour ce qui est de la récursivité, le caractère naturel ou non, je ne vois pas comment tu peux affirmer objectivement qu'une façon de faire est plus naturelle qu'une autre.

Bien:

On est beaucoup plus souvent incité à travailler de manière itérative, grâce aux boucles, que de manière récursive: alors que tu auras particulièrement facile à "visualiser" le comportement d'une boucle, il te faudra fournir un effort d'abstraction supplémentaire pour visualiser le comportement de la même fonction implémentée de manière récursive.

Ce n'est d'ailleurs pas par hasard si tous les langages ne permettaient pas, au départ, d'implémenter la récursivité, ni si la récursivité a si mauvaise presse, alors qu'il est au demeurant "si facile" d'éviter une récursivité infinie (après tout, il n'y a "qu'à tester le cas de base" :D).

Enfin, il ne faut pas forcément chercher un hasard non plus dans le simple fait que l'approche récursive survient, dans l'apprentissage, systématiquement après celui des boucles et itérations ;)

Je le répète à nouveau, je suis le premier à reconnaitre les grandes qualité de certains concepts comme la récursivité, les expressions constantes ou de bien d'autres techniques, et je suis souvent parmi les premiers à en défendre un usage raisonné ;)

Par contre, ce que j'affirme haut et fort, c'est que, quelle que soit la technique envisagée, si on ne décide de l'utiliser que "pour la figure de style", on fait plus que vraisemblablement fausse route en introduisant de manière générale une complexité dont on n'a pas forcément besoin.

Finalement, le conseil d'Xp KISS devrait en tout état de cause toujours prévaloir ;)
16/04/2013, 21h40
Flob90

@koala01: Pour la "figure de style" je suis totalement d'accord, mais c'est clairement pas le cas de l'op, il dit clairement qu'il a un nombre signifiant de cas où le compilateur peut optimiser grâce au constexpr, ce n'est donc pas juste une "figure de style".

Citation:

On est beaucoup plus souvent incité à travailler de manière itérative, grâce aux boucles, que de manière récursive: alors que tu auras particulièrement facile à "visualiser" le comportement d'une boucle, il te faudra fournir un effort d'abstraction supplémentaire pour visualiser le comportement de la même fonction implémentée de manière récursive.

Je ne suis clairement pas d'accord, quand je vois un algo j'ai tendance à essayer de voir sa justesse, et c'est la pensée récursive qui me permet ça (tout simplement car le principe de récurrence m'assure une grande justesse). Et donc ce qui me demande le moins d'effort c'est le l'implémenter comme je suis certain qu'il sera juste : de manière récursive.

Citation:

Ce n'est d'ailleurs pas par hasard si tous les langages ne permettaient pas, au départ, d'implémenter la récursivité, ni si la récursivité a si mauvaise presse, alors qu'il est au demeurant "si facile" d'éviter une récursivité infinie (après tout, il n'y a "qu'à tester le cas de base" ).

Et à l'heure actuelle de nombreux langages ne proposent que la récursivité (typiquement les langages fonctionnels "récents"), la société à donc changé si fortement de mentalité en l'espace d'un demi-siècle ? Pour le côté "mauvaise presse", je trouve ceci totalement subjectif. Ton raisonnement est, je trouve, dangereux, en forçant le trait, tout ce qui a été ajouté aux langages de la premières heures ne sont donc que des abstractions qui demandent un effort plus important ? J'ai plutôt tendance à croire que les efforts qu'on demandés les ajouts des différents langages au cours du temps sont plutôt de l'ordre de l'implémentation que de la compréhension par l'homme.

Citation:

Enfin, il ne faut pas forcément chercher un hasard non plus dans le simple fait que l'approche récursive survient, dans l'apprentissage, systématiquement après celui des boucles et itérations

Ça dépend de ton apprentissage, celui qui à appris l'informatique en partant des mathématiques aura surement vu la récurrence bien avant les boucles.

Que la pensée itérative soit la plus naturelle pour une personne lambda je le conçoit (la plupart des instructions de la vie courant me semble formées de manière itératives et non récursives, par exemple les recettes de cuisine ou les manuels d’assemblage pour un mobilier), qu'un développeur se tourne naturellement vers une méthode itérative me dérange un peu plus : c'est d'une certaine façon son "boulot" d'au moins envisager les deux et pas juste de se tourner bêtement vers l'un.
17/04/2013, 02h29
koala01

Citation:

Envoyé par Flob90

Je ne suis clairement pas d'accord, quand je vois un algo j'ai tendance à essayer de voir sa justesse, et c'est la pensée récursive qui me permet ça (tout simplement car le principe de récurrence m'assure une grande justesse). Et donc ce qui me demande le moins d'effort c'est le l'implémenter comme je suis certain qu'il sera juste : de manière récursive.

Comme je l'ai dit, il y a des algorithmes qui méritent amplement d'être implémentés de manière récursive...

Mais quand on voit l'algorithme de calcul d'une exponentielle ou d'une factorielle, en toute honnêteté, la récursivité n'est absolument pas nécessaire dans le sens où une simple boucle peut amplement suffire (dans "le cas de base" qui n'essaye pas d'implémenter une classe template en tout cas ;))

Citation:

Et à l'heure actuelle de nombreux langages ne proposent que la récursivité (typiquement les langages fonctionnels "récents"), la société à donc changé si fortement de mentalité en l'espace d'un demi-siècle ?

Il faut croire...

Par expérience, à tord ou à raison (enfin, dans mon cas, très certainement à tord :D), il y a deux choses pour lesquelles de nombreux développeurs seront ravis de te déléguer la tâche tant ils ont peur de se "vautrer": la récurisivité et la gestion des ruptures :D

Citation:

Pour le côté "mauvaise presse", je trouve ceci totalement subjectif.

Je peux te ressortir des débats (qui datent d'après 2000!!!!) qui montrent pourtant bel et bien la mauvaise presse de la récursivité ;)

Citation:

Ton raisonnement est, je trouve, dangereux, en forçant le trait, tout ce qui a été ajouté aux langages de la premières heures ne sont donc que des abstractions qui demandent un effort plus important ?

Bien sur que toute abstraction demande un effort supplémentaire et/ ou plus important !

Un simple exemple : la POO...

Le principe est pourtant simple : il s'agit de considérer les objets pour les services qu'ils sont susceptibles de rendre et non pour les données qu'ils manipulent.

Et pourtant, as tu déjà remarqué le nombre de sujets pour lesquels on se rend compte qu'il y a définitivement un problème de conception :question:

Dés que tu passes par une abstraction, tu passes par "une vue de l'esprit" (c'est, à peu près, la définition même d'une abstraction ;)).

Le problème, c'est que, si tu n'as déjà pas une idée claire de ce que tu veux abstraire, tu auras du mal à obtenir une abstraction cohérente ;)

Citation:

J'ai plutôt tendance à croire que les efforts qu'on demandés les ajouts des différents langages au cours du temps sont plutôt de l'ordre de l'implémentation que de la compréhension par l'homme.

Je suis très loin d'en être persuadé ;)

Citation:

Ça dépend de ton apprentissage, celui qui à appris l'informatique en partant des mathématiques aura surement vu la récurrence bien avant les boucles.

Désolé, mais, personnellement, j'ai appris l'informatique au départ de l'informatique... et je ne suis vraiment pas un matheux :aie:

Citation:

Que la pensée itérative soit la plus naturelle pour une personne lambda je le conçoit (la plupart des instructions de la vie courant me semble formées de manière itératives et non récursives, par exemple les recettes de cuisine ou les manuels d’assemblage pour un mobilier), qu'un développeur se tourne naturellement vers une méthode itérative me dérange un peu plus : c'est d'une certaine façon son "boulot" d'au moins envisager les deux et pas juste de se tourner bêtement vers l'un.

Mais comme tu le remarques si bien, chaque fois qu'il y a des instructions à respecter (cela va des simples recettes de cuisine au fait d'assembler une fusée spatiale :D), cela se fait de manière itérative.

Il est donc logique que ce soit le mode de pensée "naturel" de n'importe qui, développeur ou non.

Il n'y a absolument pas à trouver dérangeant cet état de fait, il y a "juste" à en être conscient.

Je t'accorde cependant qu'il pourrait être dérangeant d'imaginer qu'un développeur puisse ne pas s'interroger afin de savoir si la solution itérative "naïve" qu'il envisage est la mieux adaptée.

Mais je ne dis pas que tout développeur digne de ce nom ne s'interrogera pas sur la possibilité d'envisager d'autres solutions, je dis juste que la première solution envisagée sera, a priori, itérative et que toute autre solution non itérative demandera un effort d'abstraction supplémentaire.

Il faut en effet bien être conscient du fait que, même s'il a été "formé pour", même si c'est son job de tous les jours que de réfléchir à des solutions alternatives pour mettre un algorithme au point, le développeur n'est jamais qu'un être humain comme les autres qui a ses habitudes d'être humain comme les autres!

Et ses habitudes "naïves" (celles qui lui viennent le plus facilement à l'esprit), c'est de travailler de manière itérative car la récursivité n'intervient que très peu dans ce qu'il a l'habitude de pratiquer lorsqu'il n'est plus devant son clavier.
17/04/2013, 22h12
Iradrille

Citation:

Envoyé par koala01

Mais je ne dis pas que tout développeur digne de ce nom ne s'interrogera pas sur la possibilité d'envisager d'autres solutions, je dis juste que la première solution envisagée sera, a priori, itérative et que toute autre solution non itérative demandera un effort d'abstraction supplémentaire.

S’interroger sur la méthode la plus efficace, je suis totalement d'accord, mais la méthode "qui vient le plus rapidement à l'esprit" c'est (pour moi en tout cas, je sais pas si on peut avoir des stats objectives quelque part ?) la récursion.
Je commence souvent par un algo récursif, que je transforme en algo itératif par la suite.

Citation:

Envoyé par koala01

Et ses habitudes "naïves" (celles qui lui viennent le plus facilement à l'esprit), c'est de travailler de manière itérative car la récursivité n'intervient que très peu dans ce qu'il a l'habitude de pratiquer lorsqu'il n'est plus devant son clavier.

En pensant à un algo type tri par fusion par exemple, le premier truc qui me vient à l'esprit c'est un algo récursif (peut-être que c'est le bon choix ici, je sais pas de quelle façon cet algo est codé de façon optimale, mais c'est (pour moi, toujours) la façon la plus simple de coder ça.

La récursion à mauvaise réputation (en C/C++, d'autres langages comme le Lisp ont d'autres a priori sur la récursion) car un appel de fonction est souvent plus lourd que de mettre (et récupérer après) un pointeur dans une stack : -> fonctions inline), et du coup, bien souvent le même algo est plus rapide quand il est codé de manière itérative.
(En mettant de coté le nombre "d'itérations possible", qui est faible lorsque l'on utilise la récursion.)

Après disant tout ça.. je sais que ça reste de la théorie, que je devrais toujours me poser la question entre itératif et récursif, mais les a-prioris sont trop fort, j’essaierai en permanence de ne jamais avoir de code récursif
17/04/2013, 22h50
koala01

En fait, si la récursivité a mauvaise presse dans les langages impératifs, c'est, essentiellement, parce qu'il est sommes toutes "assez facile" d'exploser la pile d'appels du fait de la récursivité (tu penses : la fonction qui s'appelle sans cesses :D)

Et ce n'est, malheureusement, pas un a priori, c'est un fait : une fonction itérative ne place les données que d'un appel sur la pile d'appel, alors qu'une fonction récursive placera des données sur la pile d'appel à chaque fois qu'elle s'appellera elle-même.

Il est donc très facile, si tu ne prend pas soin de réfléchir de manière stricte au "cas de base" (celui qui provoque la sortie de fonction sans qu'elle ne se rappelle elle-même) d'arriver à surcharger la pile d'appels quelle que puisse être sa taille.

Et ce phénomène est encore aggravé avec les algorithmes utilisant la double ou la triple récursivité :aie:.

De plus, la récursivité représente une abstraction supplémentaire, quoi que tu puisses en penser.

Or, il suffit de voir le nombre de questions qui ne sont pas uniquement orientées sur des points du langage pour se rendre compte que l'abstraction n'est ni "naturelle" ni "instinctives" : une grosse majorité des questions sont essentiellement dues au fait que celui qui les pose est parti sur une mauvaise abstraction (ne serait-ce que parce qu'il n'a pas pensé à rajouter un niveau d'indirection supplémentaire ;)).

C'est tout cela qui fait que la récursivité est, je le répète, une technique qui mérite d'être connue et appliquée lorsque qu'il est intéressant d'y recourir (lorsque l'algorithme est clairement plus facile sous la forme récursive que sous sa forme itérative), mais dont le bénéfice mérite aussi d'être évalué et comparé aux "autres solutions" (qui viendraient, de plus, sans doute plus facilement à l'esprit).

Ceci dit, nous commençons à nous écarter fortement du sujet initial.

Ce qu'il faut absolument arriver à intégrer, c'est que toute technique, quelle qu'elle soit, ne vaut que par le bénéfice que l'on peut en tirer.

Si tu décides de recourir à une technique avancée, quelle qu'elle soit, uniquement pour "la figure de style", tu risques, bien souvent, d'obtenir un effet inverse de celui que tu essayes d'obtenir, à savoir : obtenir un code le plus compréhensible et le plus évolutif possible
18/04/2013, 01h12
JolyLoic

Citation:

Envoyé par koala01

Mais quand on voit l'algorithme de calcul d'une exponentielle ou d'une factorielle, en toute honnêteté, la récursivité n'est absolument pas nécessaire dans le sens où une simple boucle peut amplement suffire (dans "le cas de base" qui n'essaye pas d'implémenter une classe template en tout cas ;))

Et quand on voit l'algorithme de calcul d'une exponentielle ou d'une factorielle, en toute honnêteté, itérer n'est absolument pas nécessaire dans le sens où une simple récursion peut amplement suffire.
Et je ne dis pas ça simplement pour le plaisir de la contradiction. Pour moi, la définition mathématique de la factorielle, par exemple, est avant tout n! = n*(n-1)!. C'est ainsi que j'ai appris l’existence de cette fonction enfant, et une définition à base de boucle est plus complexe pour moi.

Citation:

Envoyé par koala01

Mais je ne dis pas que tout développeur digne de ce nom ne s'interrogera pas sur la possibilité d'envisager d'autres solutions, je dis juste que la première solution envisagée sera, a priori, itérative et que toute autre solution non itérative demandera un effort d'abstraction supplémentaire.

Je serais d'accord avec toi, si à la place de "tout développeur digne de ce nom", tu disais "je", voire "la majorité des développeurs". Je connais des développeurs totalement dignes de ce nom qui pensent différemment. En particulier ceux qui bossent plus sur des algorithmes fondamentaux que sur des interfaces d'accès à des bases de données.

En particulier, l'itération demande un état variable, ce qui est bien plus complexe à modéliser.

Citation:

Envoyé par koala01

En fait, si la récursivité a mauvaise presse dans les langages impératifs, c'est, essentiellement, parce qu'il est sommes toutes "assez facile" d'exploser la pile d'appels du fait de la récursivité (tu penses : la fonction qui s'appelle sans cesses :D)

Et une boucle infinie, est-ce vraiment mieux ? Ou une boucle qui va un cran trop loin ? Ou s'arrête un cran trop tôt ? Dans tous les cas, un bug est un bug.

Parmi les erreurs faites par les débutants, une des erreurs les plus fréquentes consiste à se planter dans les conditions d'arrêt des boucles. Au moins, avec une récursion, le programme explose vite, au lieu de tourner pendant des heures sans que tu saches si c'est normal ou pas ;)

Et mon ordre de préférence pour les bugs est le suivant :
- Erreur de compilation
- Déclenchement d'une assertion
- Plantage clair et net du programme
- Programme partant en boucle infinie
- Programme donnant l'air de marcher, mais donnant de mauvais résulats
- Programme donnant l'air de marcher, marchant la plupart du temps, mais donnant parfois le mauvais résultat.

Donc, en fait, je préfère un bug lié à une explosion de pile à un bug de boucle infinie ou d'autre erreur de type + ou - 1 (remarque : ces bugs sont aussi possibles avec la récursivité, mais je les pense moins courants).

Après, je veux bien croire que tu fais moins d'erreurs avec les boucles qu'avec la récursivité, parce que tu y es plus entrainé, parce que ça t'est plus naturel. Mais de ce que j'ai pu constater, les deux sont aussi complexes, et risquent toutes deux d'être mal implémentées.
18/04/2013, 10h22
koala01

Peut etre est-ce "simplement" parce que tu es plus mathématicien qu'autre chose, et que tu as l'habitude des formules qui peuvent s'avérer récursive, mais hors du domaine mathématique, chaque fois que tu vas vouloir donner des instructions à quelqu'un, tu vas "naturellement" les lui donner de manière itérative "fais ceci tant que", "fais cela jusqu'à" , "fait ca trois fois" ou encore "pour chaque ... dans .... ".

Je suis tout à fait d'accord que la mauvaise presse de la récursivité n'est très clairement pas justifiée (je l'ai d'ailleurs dit dés ma première intervention, et je l'ai répété de nombreuses fois par la suite ;)), et je suis tout à fait d'accord avec le fait que les boucles présentent leurs propres écueils auxquels il faut être particulièrement attentif, mais la manière "naïve" et "instinctive" que tu auras de représenter de telles instructions sera, forcément, itérative, pour la simple raison que les boucles que tu vas utiliser sont la traduction "littérale" de ce genre d'instructions.

Je ne dis absolument pas que c'est la manière de procéder à respecter, je dis juste que je suis convaincu que la première idée sera généralement itérative et que la solution récursive ne sera généralement envisagée qu'à cause de la complexité qu'il peut y avoir à mettre au point un algorithme itératif équivalent respectant l'ensemble des besoins, c'est tout ce que je dis, j'en suis personnellement persuadé, et vous aurez de toutes façons énormément de mal à me convaincre du contraire ;)
18/04/2013, 10h36
ternel
Citation:

Envoyé par JolyLoic

Pour moi, la définition mathématique de la factorielle, par exemple, est avant tout n! = n*(n-1)!.

Erreur, la définition mathématique récursive de la factorielle est:
Code:

1 2 3 4 pour tout entier n positif, n! = { si n=0, 1, si n>0, n*(n-1)! }
Tandis que la définition directe est plutôt (sachant que PI est l'opérateur aggrégant par multiplication)
Code:

1 2 3 4 pour tout entier n positif, n! = { si n=0, 1, si n>0, PI(i=1:n) i }
C'est d'ailleurs la définition que j'ai apprise en premier…
18/04/2013, 15h35
Flob90

Iradrille, Loic et moi même n'avons pas affirmer que vous deviez penser de manière récursive ou que "la" définition (*) de la factorielle doit être récursive (par exemple), seulement qu'affirmer que c'est naturel n'était pas objectif. Ça l'est peut-être pour vous, mais pas pour d'autre ...

Et si je suis prêt à admettre que si l'on considère une population lambda cette affirmation est vrai, je le suis beaucoup moins dès que cette population est à caractère scientifique.

Au début je voulais pointer sur des liens SO où les meilleurs réponses montrent bien que la récursion est naturel pour de nombreux développeur, cependant je suis tombé sur un autre article dont la conclusion me plait :
http://www.ibm.com/developerworks/li...urs/index.html

Citation:

Recursion is a great art, enabling programs for which it is easy to verify correctness without sacrificing performance, but it requires the programmer to look at programming in a new light. Imperative programming is often a more natural and intuitive starting place for new programmers which is why most programming introductions focus on imperative languages and methods. But as programs become more complex, recursive programming gives the programmer a better way of organizing code in a way that is both maintainable and logically consistent.

(NB: J'ai pas lu l'ensemble de l'article)

Citation:

La récursion est un art important, permettant de vérifier la justesse des programmes sans perdre de performance, mais elle demande aux développeurs d'adopter un nouveau point de vue. Les langages impératifs sont souvent plus naturel et intuitif pour les débutants, ce qui en font des langages et méthodes de choix pour les cours d’introduction. Mais plus les programmes deviennent complexes, plus la récursion apporte un meilleur façon d'organiser le code : il devient plus maintenable et logique.

Oui, pour une personne lambda / un débutant, naturellement il va penser itératif. Mais pour quelqu'un qui commence à avoir des besoins plus importants, quelqu'un qui aura été "formé" (**) la récursion peut être un mode de penser totalement naturel (***).

(*) leternel : C'est quoi une "définition directe" ? Et quand bien même tu arriverais à définir clairement ce concept, je vois mal comment tu pourrais l'appliquer avec certitude à une notion mathématique aussi ancienne.

(**) peu importe la méthode de formation, et peu importe que ce soit une formation au maths ou plus spécifiquement à l'algorithmie (en général il faut pas avoir fait beaucoup d'algorithmie pour avoir fortement intégré le principe de récurrence, typiquement avoir travaillé sur les algorithmes de base des structures de données basiques suffit pour ça).

(***) quand on a du se forcer 10 ou 20 fois à adopter un nouveau point de vue pour résoudre un problème, la 21° fois, ça a tendance à être naturel.
18/04/2013, 16h55
ternel

J'ai dis directe, par opposition à récursif, parce que la formule n'inclue aucun précalcul.
C'est le même style de formule que moyenne = (1/n) * somme(i=1..n) (mesure i)J'aurais pu expliquer que la factorielle d'un entier n strictement positif est le produit de tous les entiers entre 1 et n, et qu'elle est étendue par 0! = 1.

Cette définition n'est ni itérative ni récursive, elle est éventuellement qualifiable de métrique et ensembliste.
19/04/2013, 10h04
JolyLoic

Citation:

Envoyé par Flob90

Oui, pour une personne lambda / un débutant, naturellement il va penser itératif. Mais pour quelqu'un qui commence à avoir des besoins plus importants, quelqu'un qui aura été "formé" (**) la récursion peut être un mode de penser totalement naturel (***).

Et encore, je pense que ça dépend comment le débutant a débuté. Un prof avec qui je parlais hier me disait que depuis qu'il avait des élèves qui en prepa avaient fait un peu d'ocaml, quand ils commençaient le C++, ils utilisaient la récursion, même pour itérer sur une liste.

Citation:

Envoyé par Flob90

(***) quand on a du se forcer 10 ou 20 fois à adopter un nouveau point de vue pour résoudre un problème, la 21° fois, ça a tendance à être naturel.

+1
19/04/2013, 10h32
ternel

je reconnais là l'effet d'ocaml…
20/04/2013, 21h42
germinolegrand

Histoire d'apporter mon grain de sel : pour moi la récursion est quelque chose qui me demande beaucoup de réflexion la plupart du temps. J'ai dû m'y exercer pour utiliser les variadics templates.

En réalité j'ai l'impression qu'il n'y a pas de voie naturelle : quand il s'agit de maths, pour implémenter par exemple une factorielle, une puissance, la version récursive me semble couler de source. En revanche quand je fais autre chose que des maths (c'est à dire 99% du temps) c'est clairement la version itérative qui s'impose à moi.

Peut-être est-ce une question de paradigme ? Le fonctionnel tend à privilégier le récursif, l'impératif tend à privilégier l'itératif... Les mathématiques tendant à présenter globalement le fonctionnel, cela expliquerait bien des choses.