[C/C++] Discussions de tout et de rien

[Morwenn]

En général, on trouve toujours quelque part sur le net les réponses aux questions que l'on veut poser sur le C/C++ tellement ces langages sont utilisés. Seulement, aujourd'hui, j'ai rencontré un problème que je n'ai pas pu résoudre. Explications :

J'étais en train de rédiger un .cpp permettant de faire de la géométrie dans des espaces à N dimensions (d'ailleurs, je ne vous raconte pas les maux de tête...). Du coup, bien entendu, il faut pouvoir créer un point dans un espace à N dimensions pour que tout soit utilisable assez facilement.
Mes points sont déterminés, va-t-dire, par la structure suivante :

Code: [Select]

typedef struct pNd
{
    unsigned int N; // Dimension
    double* Coords;
} pNd;
typedef pNd* PointNd;


J'ai donc ensuite créé une fonction de construction d'un point à N dimensions. Voici ce à quoi elle ressemble :

Code: [Select]

#include <stdarg.h>
PointNd Point(double N, ...)
{
    PointNd P = (PointNd) malloc(sizeof(pNd));
    
    P->Coords = (double*) malloc((int)N * sizeof(double));
    double coo;
    
    va_list args;
    va_start(args, N);
    
    for (int i = 0 ; i < N ; ++i)
    {
        coo = va_arg(args, double);
        P->Coords[i] = coo;
    }
    va_end(args);

    return P;
}

EDIT: Pour ceux qui passeraient ici par hasard en cherchant des trucs sur les fonctions variadiques, ce code marche !
Le problème décrit plus bas venait d'ailleurs.

Comme vous pouvez le voir, le principe est simple : un point est constitué de N coordonnées (x, y, z, w...) qu'on lui passe en paramètres quand on le crée, via une fonction variadique (de stdarg.h).

Seulement, lorsque je veux faire afficher les valeurs récupérées, le seul résultat que j'obtiens à chaque fois est 0.00000 pour chaque coordonnée. J'ai fait afficher des valeurs non récupérées avec va_arg() et tout marchait très bien. J'en déduis que c'est la fonction va_arg() qui ici pose problème, pour une raison que j'ignore. N'ayant trouvé aucune réponse à mes problèmes, je sollicite votre aide, en espérant que les adeptes du C/C++ puissent m'aider


P.S. : Le tout est compilé avec un compilateur C++, j'utilise 7 sur une architecture 64 bits. J'ai aussi essayé de remplacer stdarg.h par cstdarg, mais sans que cela ne change rien.

[Wouf]

J'ai jeté un petit coup d'oeil à ton code et mis à part le fait que tu oublies d'initialiser la variable membre N de pNd dans ta fonction d'instanciation, je ne vois pas de problème. J'ai testé, tout marche impec ^^

Pourrait-on voir ta fonction main ?

En tout cas, je te remercie, je viens d'apprendre un nouveau mot, ainsi que l'utilisation des fonctions à nombre variable d'arguments

Je te file mon code si ça peut t'aider (j'ai commenté les différences + fct main) :
[spoiler]

Code: [Select]

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>

typedef struct pNd
{
    unsigned int N; // Dimension
    double* Coords;
} pNd;

typedef pNd* PointNd;


PointNd Point(double N, ...)
{
int i = 0 ;
    PointNd P = (PointNd) malloc(sizeof(pNd));

// TODO : Tells I've Added this line
    P->N = N ;

    P->Coords = (double*) malloc((int)N * sizeof(double));
    double coo;

    va_list args;
    va_start(args, N);

// TODO : Tells I've changed ++i to i++
    for (i = 0 ; i < N ; i++)
    {
        coo = va_arg(args, double);
        P->Coords[i] = coo;
    }
    va_end(args);

    return P;
}

/**
 * Print a point to screen
 *
 * \param pnd Point to print
 *
 */
void printPoint(PointNd pnd)
{
int i = 0 ;

printf("Dimension : %ld\n\n", pnd->N) ;

for (i = 0 ; i < pnd->N ; ++i)
{
printf("Coordinate number %ld : %f\n", (i + 1), pnd->Coords[i]) ;
}
}


int main(void)
{

PointNd pnd = NULL, pnd2 = NULL ;

// Allocates two points.
pnd = Point(4, 1.0, 2.0, 3.0, 4.0) ;
if (pnd == NULL) printf("ERROR : pnd == NULL") ;

pnd2 = Point(2, 3.89, 4.78) ;
if (pnd2 == NULL) printf("ERROR : pnd2 == NULL") ;

// Prints to screen.
printf("pnd :\n===\n\n") ;
printPoint(pnd) ;

printf("\n\n") ;

printf("pnd2 :\n====\n\n") ;
printPoint(pnd2) ;


return EXIT_SUCCESS;
}
[/spoiler]

Sinon, faudra que tu m'expliques où t'as été cherché tes conventions de code
En général, les développeurs s'arrangent pour reconnaître un élément sur base de sa syntaxe, svt comme suit :

- une minuscule pour commencer et des parenthèses à la fin --> fonction
- une minuscule, sans parenthèses finales --> une variable
- une majuscule pour commencer --> un type
- rien que des majuscules --> une constante (define ou const)

Bien sûr, tu peux faire des noms composés : maVariableDeLaMortQuiTue ou MA_VARIABLE_DE_LA_MORT_QUI_TUE si c'est une constante

Fais gaffe aussi à ne pas confondre i++ et ++i. Dans ce cas, ils s'équivalent, mais ce ne sera pas toujours le cas.

Dernier détail, c'est davantage du C que du C++.
En C++, on préfère utiliser les oprérateurs new et delete pour l'allocation dynamique.
De même pour les structures qui sont souvent remplacées par les classes.
Enfin, tu n'as utilisé que des entêtes C (suffixe .h)

D'ailleurs, je me demandais si ce n'était pas pour imiter les constructeurs que tu nommais ta fonction d'instanciation comme si c'était un type ?

Enfin bref ^^
S'il y a d'autres problèmes, n'hésite pas à demander (histoire de rentabiliser la section, mdr).
Bonne chance pour la suite

PS : Je ne crois pas que ça t'aidera, mais j'ai trouvé ceci à propos de la fonction printf: "Use "%f" for both float and double; a float argument to a variadic function like printf is automatically promoted to double."

[yoshi04]

Bon Wouf tu as été plus rapide et j'ai pas grand chose à ajouter du coup : D
[spoiler]Ouais je sais ya une énorme différence entre les deux posts mais bon ça m'apprendra à ne pas lire tous les topics jusqu'au bout  [/spoiler]

Effectivement je ne connaissais pas cette appelation de fonction non plus, j'avais plutôt tendance à passer des tableaux pour ce genre de problème ^^
(d'ailleurs certaines personnes préconisent la combo template+ stl_vector pour le passage au C++ Lien )

De mon côté j'avais une petite erreur avec mes tests mais en même temps je refilais quelque chose comme "3" au lieu de "3.0" ><

[Morwenn]

Hum... il faut que je teste, mais c'est vrai que j'ai peut-être passé des entiers en paramètres plutôt que des float/double, l'erreur vient probablement de là, il faut que je vérifie...
Par contre, si ce n'est pas ça, je ne vois pas d'où peut venir l'erreur.

Sinon, Wouf, merci pour la petite erreur, je ne l'avais pas vue étant donné que j'étais bloqué sur le problème de mes arguments qui étaient tous égaux à 0.0000 quand je faisais un printf().


Maintenant, concernant le choix de la syntaxe, et les petites différences C/C++, expliquons-nous clairement : je voulais faire un programme en C, entièrement, d'où l'utilisation de fonctions "Constructeurs", d'allocation dynamique, etc... Je dirais même plutôt C99 pour pouvoir utiliser certains trucs supplémentaires, comme la déclaration de variable dans l'initialisation d'une boucle for.
Cependant, il me manquait toujours un truc : la surcharge des fonctions, que j'utilise beaucoup (j'avais jusque-là un module 2d/3d/4d, qui avaient tous des fonctions s'appelant Point(), et qui retournaient donc des types différents en fonction du nombre de paramètres passés, ou la fonction Intersection qui se démerde avec tout ce qui lui est passé en arguments. Mais sinon, il est vrai que dans l'esprit, le programme est écrit en C.

Pour la syntaxe, c'est plus compliqué :

• D'une manière générale, j'utilise exactement la syntaxe que tu as énoncé.
• J'ai décidé de faire une coupure dans mon programme entre les fonctions "informatiques", et les fonctions purement mathématiques (qui s'appelleront Quadratic, Prime, Point, Circle, Hyperplane, Intersection...).
• Les noms pNd, p2d, c3d, c2p2d, etc... qui sont les structures définissant les figures dans les dimensions données ne sont jamais utilisés tels quels ou presque, à part pour construire les objets de type PointNd, Point2d, Circle3d, Sphere3d, Couple2Point2d...
• Ah oui, je suis au courant des différences entre i++ et ++i, et je sais bien que ça ne change rien utilisé comme ça. Seulement, il est prouvé que l'opérateur préfixe est plus rapide que l'opérateur postfixe. La différence ne peut pas se remarquer sur des entiers, mais quand on utilise d'autres types (complexes, etc...), ça peut faire une différence. Comme ça ne coûte rien de plus, je préfère le mettre en préfixe dès que possible

Bref, j'ai juste réadapté la syntaxe à mes besoins, ne vous préoccupez pas trop pour ça, de toutes façons, je suis tout seul à utiliser mon code pour des raisons bien précises, et je n'arrivais pas toujours à bien me retrouver entre les différents modules de mon programme (mathématiques ou non), donc j'ai modifié la syntaxe pour mieux m'y retrouver


Bref, dans tous les cas, merci d'avoir proposé quelques trucs, je vais vérifier tout de suite, e espérer que ce ne soit qu'une erreur débile, comme des entiers passés en paramètres, ou un truc du genre



EDIT : Bon bah voilà, c'était tout con, j'avais juste passé des entiers en paramètres au lieu de passer des float/double, du coup, ça ne marchait pas correctement, je suis vraiment trop bête de m'être fait avoir par une erreur pareille^^"

[Wouf]

Ca arrive, les gars, j'ai fait la même erreur par le passé ^^
(pour ça que je fais attention, maintenant )

Ouais, je vois pour le C++.
Moi aussi, j'aime bien faire du C en C++ pour profiter de certains ajouts, tels que les namespaces

Concernant les fonctions "mathématiques", elles restent néanmoins informatiques et changer de syntaxe à l'intérieur d'un même programme me semble un peu douteux. Mais tu fais comme tu veux.
Message subliminal : définir un namespace mathematique ?

Sinon, il y a d'autres langages plus proches des mathématiques, si tu veux. Les langages fonctionnels, tels que Scheme ou Common Lisp. Ils ont l'avantage d'être des langages de scripts et sont ainsi plus pratiques :
- passage de fonction en argument (sans jongler avec des callbacks comme en C) [utile pour composer des fonctions] ;
- typage faible (idéal pour la sucharge/polymorphisme) [passer des int à la place de double fonctionnera quand même] ;
- ...
De plus, comme ils sont essentiellement basés sur les listes, la taille est dynamique et tu peux facilement définir des fonctions à nombre variable d'arguments.
En revanche, il faut s'habituer au paradigme : récursion (bye les boucles), pas d'affectation, éviter les séquences d'instructions (sauf cas spécial), ...
Mais tu gagnes en proximité avec les maths (définitions récursives)

Maintenant, je suis conscient qu'apprendre un nouveau paradigme est coûteux en temps, que tu as peut-être des contraintes scolaires (langage imposé, ...). Mais si tu fais ça de ton temps libre, pour faire des liens avec ton cours de math, alors je t'y encourage. De toutes, si tu suis des études d'info, tu y passeras tôt ou tard à ce foutu fonctionnel
Sans compter que le Lisp permet d'étendre les fonctionnalités de Maxima (Mathematica-like), un framework de calcul symbolique assez sympa qui te permet par exemple de dériver/intégrer une expression par rapport à une variable x, sans fixer une valeur à celle-ci.

Donc voilà, je suis sûr à 80% que tu continueras sur ta lancée, mais au moins, tu es courant qu'il y a une alternative particulièrement adaptée aux matheux ^^

Effectivement je ne connaissais pas cette appelation de fonction non plus, j'avais plutôt tendance à passer des tableaux pour ce genre de problème ^^

Oui, c'est aussi ce que je fais, voire une liste dans l'éventualité où l'on pourrait ajouter/enlever des élements tout au long du programme (liste d'affichage, ...).

Et en effet, en C++, les gens ont tendance à éviter les macros.

Niveau rapidité, j'ai ramé pourtant : j'avais bazardé les préférences de mon IDE sans faire exprès, avec mes colos et tout
Heureusement, j'avait une copie dans un autre workpath, *ouf*, mais j'ai quand même perdu presque 1h à éplucher les dates de modification pour trouver les plus récentes x3

@Morwenn :
Ah et merci pour la deuxième fois, je ne savais pas qu'il y avait un rapport de perfs entre pré et post incrémentation. De plus, j'ai appris pourquoi i = i++ et i = (i = 4) +1 sont des cas d'indétermination. Je n'avais jamais songé au problème de séquentialisation des effets de bord. [source]
Comme quoi, on en apprend tous les jours

[Morwenn]

Bah, si tu veux, voici ma référence en matière d'optimisation pour la langage C++. Je ne garde pas grand-chose en mémoire, mais le chapitre "Optimization as you go" permet de prendre de bonnes habitudes en contournant la formule "Optimization is the root of all evil", mais qui reste cependant plutôt vraie dans tous les autres cas

Pour les autres alternatives, c'est sympathique d'en parler, mais la raison pour laquelle j'utilise le C, c'est bel et bien parce que c'est rapide. En fait, je m'amuse à essayer de créer un petit langage de script, c'est là la clef du challenge. Et pour qu'il ne soit pas trop lent, je fais en sorte qu'il soit interprété en C, parce que le C est réputé pour sa rapidité
Le fait de développer des fonctions de calcul mathématique, c'est pour plusieurs raisons : déjà parce que ça me fait réviser mes mathématiques (et quoi qu'on en pense, ça n'a strictement rien à voir avec le programme de maths de l'IUT). Ensuite, si j'ai des fonctions mathématiques pré-construites de calcul dans l'espace 2d/3d/4d/Nd, ça donne déjà un petit avantage à utiliser ce langage de script ; mais ce ne sont pas les seuls modules, j'ai également un convertisseur de n'importe quel type de couleur vers n'importe quel autre type (en fait non, mais ça gère bien 6 ou 7 standards différents de représentation des couleurs)...

Bref, dans tous les cas, ça m'entraîne en maths, en C, et j'apprends de nouveaux trucs. Les variadiques par exemple, j'ai découvert ça en flânant au hasard des descriptions de la bibliothèque standard C. Enfin bref, je me perd, et je ne sais plus du tout de quoi je parlais à la base^^"


Dans tous les cas, je me doute bien qu'il doit déjà y avoir des bibliothèques C/C++ et d'autres langages qui font de base les calculs que je fais (OpenGL entre autres, qui en plus fait tout sur la carte graphique...). Mais bon, ça m'amuse bien, et puis je suis en train de réfléchir depuis deux jours sur les espaces à N dimensions, et j'ai mal au crâne, mais c'est marrant
Et puis je jetterai quand même un coup d'œil aux trucs dont tu as parlé, histoire de ne pas mourir idiot^^

[Wouf]

C'est pas plus mal, ça montre ta motivation

Il est clair que si ton but est de concevoir un petit langage de script, mieux vaut le construire par dessus un langage à perfs ^^
Je ne sais pas si c'est une bonne idée de s'attaquer à quelque chose d'aussi complexe aussi vite. Enfin, avant de s'être fait la main sur quelques langages de scripts existants, je veux dire. Mais dans tous les cas, ça reste un sujet assez intéressant dans le domaine du JA. Il existe d'ailleurs un excellent bouquin expliquant l'intérêt du scripting dans le game dev : Game Scripting Mastery, d'Alex Varanese. Après cette intro, l'auteur explique les différentes familles de scripts avant de s'attaquer à la réalisation de véritables machines virtuelles, de A à Z (2 langages si je me souviens bien). Ensuite, il termine par la description de quelques langages existants : Tcl, Python et Lua (+ comment les interfacer avec le programme hôte).
Ca peut tjs t'être utile si tu bloques sur un point ou l'autre de la réalisation

Bonne continuation ^^

[Morwenn]

Faudra que je jette un œil à tout ça alors

Normalement, j'étais parti sur un principe de "ramasse-miette", pas comme ceux qu'on connaît, mais j'aimais bien le terme : enregistrer les résultats des opérations coûteuses directement. Comme ça, le programmeur n'a pas à le faire lui-même, et quand il rappelle la fonction pour une valeur déjà connue, la valeur est juste directement prise dans un tableau. J'ai fait ça pour la fonction Prime(N) qui renvoie le Nième nombre premier, et je peux te dire que c'est peut-être la meilleure chose à faire pour ce genre de fonctions. Bref, le principe est de ramasser les miettes déjà calculées
Je compte le faire aussi pour tout ce qui est Fibonacci, et toutes ces fonctions qui demandent de connaître les valeurs précédentes. Pour les fonctions prenant plusieurs arguments, ou n'ayant pas besoin des valeurs supplémentaires, je m'étais posé la question d'utiliser des listes de hashage. Très compliqué à priori, mais j'ai trouvé un tuto basique pour comment en faire en C. Je ne l'ai pas lu, mais dans le pire des cas, ça ne peut qu'être intéressant =)

Mais finalement, j'ai commencé à m'interroger sur les espaces à N dimensions, et j'étais en train d'essayer d'imaginer un système permettant de faire quelques opérations de base avec des XObjets dans une dimension N. D'ailleurs, je vais probablement écrire quelques trucs là-dessus, ça peut être intéressant. Si j'arrive à des résultats satisfaisants, je les posterai^^


Dans tous les cas, que j'aille ou non au bout, j'aurai appris pas mal de trucs, juste en essayant de réaliser des fonctions complémentaires x)

[Wouf]

Hum .. L'idée de base est bonne et exploitée de long en large pour optimiser les fonctions récursives (terminales srtt)

Prenons justement ton exemple des nombres de Fibonacci :
Tu peux très bien te contenter de la définition mathématique

Code: [Select]

fib(n)
    if n < 2 : return n
    else : return fib(n-1) + fib(n-2)auquel cas, chaque étape de la récursion fait appel à 2 fonctions récursives (avant de sommer leurs résultats)
ainsi, tu te retrouves avec un schéma d'exécution en forme d'arbre binaire
                ___fib(4)___
              /                      \
        __fib(3)_             fib(2)
      /                \         /        \
   fib(2)         fib(1)  fib(1)  fib(0)
   /      \
fib(1) fib(0)
Mais comme tu peux le constater, on calcule plusieurs fois la même chose (les sous-arbres se recouvrent).
En réfléchissant un peu, on peut remarquer que la connaissance de 2 états passés suffit à progresser d'une étape à l'autre, en partant de 0,1 vers n. Si n1 est la valeur en n-1 ; n2, la valeur en n-2 ; et i, le nombre d'étapes restantes, on peut déduire cet algo :

Code: [Select]

fib2(n)
    if n < 2 : return n
    else : return fib2_a(1, 0, n - 1)

fib2_a(n1, n2, i)
    if i < 0 : return n1
    else return fib2_a(n1 + n2, n1, i - 1)Et le schéma de récursion devient linéaire :
fib2(4)
fib2_a(1, 0, 3)
fib2_a(1, 1, 2)
fib2_a(2, 1, 1)
fib2_a(3, 2, 0)
3
On a ainsi "ramassé les miettes" des étapes précédentes pour éviter de calculer 2 fois la même chose.

Tout ceci est valable pour la récursion, car on réutilise les valeurs précalculées juste après.
En revanche, si tu veux conserver la valeur pour plus tard, hors récursion, ça risque de gaspiller pas mal de mémoire au final. Si tu sais que tu vas souvent utiliser les fonctions sur les mêmes arguments, il peut être intéressant de mémoriser les résultats pour éviter de les recalculer. En fait, tu te rapproches d'une espèce de "cache".
Mais dans ce cas, il faudrait qu'il se vide dès que l'on en a plus besoin, histoire d'éviter d'encombrer la mémoire, ce qui risque d'être dur à déterminer. Quoique, tu pourrais simplement garder, au sein de chaque fonction coûteuse, un historique des x valeurs les plus calculées (tableau statique à la fonction), pourquoi pas
Ou encore construire des tables fixées à la compilation, qui contiennent des valeurs courantes ou points de départs racourcissant le nombre d'étapes nécessaire au calcul. En traitant au cas par cas, selon la fonction, il doit y avoir moyen, en effet

D'ailleurs, si tu veux intégrer à ton langage de script une espèce de cache générique, ça doit être faisable aussi ;
au moment où ton interprêteur identifie la fonction à partir de la chaîne de caractère (script), il peut consulter une table associative (hashage) qui contient elle-même des tables vers les résultats associés à des arguments particuliers.
Pas bête du tout, Morwenn, franchement, tu as de très bonnes idées

J'ai hâte de voir le résultat fini et son impact en pratique ^^

[Morwenn]

Oui, cette idée pour Fibonacci est la bonne, c'est chouette

Je viens de faire un petit test pour voir la différence entre les fonctions, voici globalement ce que j'ai pu observer avec la boucle suivante :

Code: [Select]

for (unsigned int i = 0 ; i < 100 ; ++i)
{
    printf("%llu\n", Fibonacci(i));
}

La méthode classique s'arrête avant d'avoir pu tout calculer, et le programme ne répond plus. J'ai essayé pour i = 50, et ce n'était même pas la peine, il ne voulait rien entendre^^"

La méthode que tu as donné marche très bien et calcule assez vite tout ça

Ma méthode, avec le "crumb collector" a tout calculé en en fraction de seconde. Pourquoi ? Déjà, parce qu'avec la boucle, la méthode que tu as donné devait tout recalculer à chaque fois. Ensuite, j'ai regardé les valeurs, et de toutes façons, les résultats obtenus (peu importe la méthode) après Fibonacci(93) dépassent la taille du unsigned long long int...
Donc bon, ça fait quand même 93 valeurs stockées en mémoire avec ma méthode, mais l'accès est instantané. Pour la factorielle, c'est encore plus efficace étant donné que les calculs deviennent inutiles après 21! car les valeurs dépassent aussi le type unsigned long long int.

Concernant les nombres premiers, la méthode du "crumb collector" est indispensable étant donné qu'il faut vérifier si un nombre est premier pour le renvoyer, et que le plus rapide moyen de le faire est de le diviser par tous les nombres premiers inférieurs. Là, la question ne se posait pas


Donc voilà pour les performances du système, et pour conclure ce sujet qui a totalement dérivé de son sujet de départ. Après, garder des valeurs en mémoire bouffe certes de la mémoire, mais le gain en rapidité en sans égal, c'est clair^^"

[Noxneo]

Y'a aussi un principe similaire, appellé "loop hoisting", qui consiste à sortir de la boucle tout code dont le résultat n'est pas dépendant de la boucle- n'importe quel compilo moderne le fait tout seul, mais c'est intéressant à connaitre:

Exemple (très) naïf pour comprendre le concept:

for (i=0;i<100;i++){
  tab[ i]=tab[i ]*une_fonction(une_constante)
}

Dans ce cas le compilo nous fera un truc du genre:

a=une_fonction(une_constante)
for (i=0;i<100;i++){
  tab[i ]=tab[i ]*a
}

http://en.wikipedia.org/wiki/Loop-invariant_code_motion

[Morwenn]

Ah bon, les compilos modernes font ça ?
Ben tant pis. J'ai tendance à faire partout des variables intermédiaires pour éviter de refaire deux fois la même division de manière générale, donc pour les boucles, c'est sûr qu'il vaut mieux en sortir tout ce qu'on peut aussi, ça évite d'avoir à refaire calculer 50 fois les mêmes choses

Depuis qu'on a fait du lancer de rayon en imagerie numérique, j'ai tendance à utiliser partout des petits trucs comme ça. Mais seulement après avoir écrit une première fois le code, parce qu'optimiser en écrivant, ce n'est juste pas possible (et très dangereux).

Ce qui optimise bien en général, c'est faire un bon choix de structures de données quand on veut stocker des trucs aussi. Là, par contre, il vaut mieux le faire avant de commencer à coder. J'ai vu récemment d'ailleurs que la méthode que j'utilise plus haut, ce n'est rien de plus que créer au fur et à mesure des Lookup Tables pour les réutiliser ensuite (rien de bien neuf, les romains faisaient déjà la même chose dans le temps). Par contre, pour les autres structures de données, c'est parfois difficile de savoir quoi utiliser pour être le plus efficace.

[Noxneo]

, c'est parfois difficile de savoir quoi utiliser pour être le plus efficace.

La route est longue, jeune padawan...

[Morwenn]

Attends, un exemple de truc qui m'embête un peu : je veux enregistrer des valeurs ayant pour clef la multiplication de plusieurs nombres premiers différents.

Ex : fonction(5, 7, 13), équivalente à fonction(7, 13, 5), etc...
Pour chaque couple de valeurs, j'ai une clef unique (ici 7*13*5), je veux stocker la clef, je dois donc choisir une structure de données.

• Je ne peux pas utiliser un tableau (même dynamique) puisque de nombreux champs seront inoccupés, ça fera de la mémoire perdue pour rien.
• Même problème avec un arbre binaire, où on fini par avoir des embranchements inutiles puisque de nombreuses valeurs n'existeront pas.
• Pour peu que les nombres premiers multipliés commencent à 3 au lieu de 2, on gagne du temps sur l'arbre binaire de base en enregistrant une valeur de moins, mais il reste beaucoup de vide.
• La skip list peut paraître être une solution intéressante, mais plus il y a d'éléments dedans, plus la recherche d'un élément à partir de sa clef est longue.
• Même problèmes avec les listes chaînées.
• Tables de hachage ? Peut-être, mais il faut avoir une bonne fonction de hachage pour que ça aille vite...

Bref... Pour le moment, j'utilise une espèce d'arbre binaire pseudo-amélioré, mais bon, plus les valeurs sont grandes, plus ça met de temps pour la recherche, et de nombreux nœuds ne servent pas à grand-chose, mais c'est difficile de s'en passer. Je pourrais essayer d'améliorer la structure pour me passer de certains nœuds, il y aurait ainsi moins de mémoire utilisée, mais je pense que ça ferait plus de vérifications, et donc une perte de vitesse...


Donc oui, comme tu dis, la route est longue, et parsemée de pointeurs

[Noxneo]

Quand tu as les mots "clé unique" et "couple de valeur", dans 99% des cas il te faut un tableau de hachage.

Sinon tu peux peut être aussi regarder du côté d'un arbre rouge noir (http://fr.wikipedia.org/wiki/Arbre_bicolore), ça pourrait peut être offrir des perfs légèrement meilleures.
Ça dépendra vraiment de ton code- y'a t-il plus d'insertions que de recherches? etc.

Je viens de me réveiller de ma sieste donc ce post n'est peut être pas très cohérent, je reviendrais plus tard

[Wouf]

Moi c'est l'inverse, je vais me coucher xD
Je suis d'accord avec Guillaume pour les tables de hashage.
Le problème du choix de la structure se transforme alors en un problème de dimensionnement (choix des bons paramètres : capacité de la table et paramètres de la fonction de hashage).
On peut parfois se servir de propriétés mathématiques inhérentes à l'application considérée, mais on se base plus souvent sur l'analyse des résultats obtenus après une batterie de tests. Donc en gros, tu répètes l'expérience pour différentes valeurs des paramètres et tu choisis celles qui utilisent au mieux les ressources
(un peu comme tu l'as fait pour comparer les différentes méthodes pour calculer les nombres de Fibo ^^)

D'ailleurs, parlons-en justement. Ton test m'a un peu choqué au départ, car il représente un mauvais choix algorithmique : on s'arrange (idéalement) pour réutiliser les résultats qui se chevauchent ; aussi, il serait plus intelligent de créer une nouvelle fonction de Fibonacci plus adaptée à ce genre de problème. On pourrait rendre publique la fonction interne (fib2_a) de fib2, et lui passer les deux derniers résultats en argument. Ou tout simplement intégrer le printf dans une copie de la fonction de Fibonacci. Si tu veux à tout pris utiliser une boucle, tu peux toujours le faire à partir d'une version récursive terminale (Si je me souviens bien, il existe même toujours une bijection entre les implémentations itératives et récursives terminales d'une même spécification, si bien qu'on parle d'itération pour les 2).
Après courte réflexion, cet exemple est sans doute légitime dans le cadre private d'une division interface/implémentation. Le tout étant de savoir si l'on peut considérer l'information suivante comme élément de l'interface : "se base sur le calcul des valeurs précédentes, à partir du point (1,0) --> O(n)". On pourrait utiliser ton exemple pour justifier le choix de l'interface publique. J'ai déjà vu des débats à propos de la place de la complexité : Puisqu'elle est susceptible de changer avec l'implémentation, peut-on l'inclure dans l'interface, censée rester hermétique aux modifs ?
En plus, des systèmes tels que ton "crumb collector" pourraient avoir un impact sur la complexité, tout en étant extérieurs à l'implémentation ... Dingue
Enfin, tant que le système améliore la complexité, c'est bon puisqu'on parle de complexité dans le pire des cas, donc O(1) est inclus dans O(n) par exemple. M'enfin, ça fait quand même un peu frois dans le dos ^^'

Ah et aussi, j'avais tiqué en voyant que tu voulais à tout pris mémoriser toutes les valeurs déjà calculées, plutôt que de conserver les x valeurs les plus fréquemment demandées. Puis ... Ben non, 93 étant le maximum puisque la fonction renvoie des unisigned long long int. D'ailleurs, c'est quoi ça ? 64 bits ? Ouais, je sais, je suis traumatisé avec ça x3
M'enfin, si tu travailles avec des objets BigInt ou un truc du genre, ça ne marchera plus 
(entiers dont la taille n'est limitée que par ta ram dispo)

Sinon, je ne connais pas encore les skipLists, à peine lu un truc dessus, une fois. Si ça tombe, j'en utilise déjà sans savoir que ça s'appelle ainsi, comme ça m'est arrivé pour les files à priorité
Quant aux arbres, ... J'aime pas, mdr. Je sais que c'est puissant, mais j'ai eu une mauvaise expérience en cours ^^'
Limite, en scheme/lisp, c'est sympa sous forme de liste profonde. Un peu comme les graphes que je préfère sous Matlab, avec les matrices d'adjacence.
Oui bon, ma vie n'intéresse que moi, je sais où est la porte, merci ^^

@Guillaume >

Exemple (très) naïf pour comprendre le concept:

for (i=0;i<100;i++){
  tab[ i]=tab[i ]*une_fonction(une_constante)
}

*avalé un quartier d'orange de travers* Arg, tu veux ma peau d'orange ou quoi ?
J'espère que ça s'applique à des problèmes plus subtils que ça, parce que sinon, lol !
D'un autre côté, pour un langage de script destiné à des gens qui n'ont pas vraiment de connaissances en programmation (1), ça se tient.

(1) Un peu comme pour le système de cartes à protéines pour biologistes dont tu m'avais parlé un fois, avec le supercalculateur, la MS surface, le quadri écran et Matlab. Ils ont déjà assez à faire avec la bio et autres sans qu'on ait besoin de leur imposer des connaissances en info, les pauvres ^^

[Noxneo]

Quant aux arbres, ... J'aime pas, mdr. Je sais que c'est puissant, mais j'ai eu une mauvaise expérience en cours ^^'

Euh je te conseille de te replonger dedans alors, parce que les arbres c'est quand même surpuissant.

J'espère que ça s'applique à des problèmes plus subtils que ça, parce que sinon, lol !

Euh ben oui quand même, ce que j'ai montré était exprès super con pour donner l'idée de base.
La page wiki a un exemple un peu plus avancé avec des liens vers des trucs plus complets.

Un peu comme pour le système de cartes à protéines pour biologistes dont tu m'avais parlé un fois, avec le supercalculateur, la MS surface, le quadri écran et Matlab. Ils ont déjà assez à faire avec la bio et autres sans qu'on ait besoin de leur imposer des connaissances en info, les pauvres ^^

Pourquoi pas, mais je ne trouve pas ça exactement pareil- dans un cas on parle d'interfaces utilisateurs, et dans l'autre on parle d'optimiser la compilation "code écrit par un humain"-> "code machine"- cette optimisation est nécessaire parce que le modèle de la machine qu'a l'utilisateur programmant en Java ou quoi n'est pas aussi détaillé que ce qui se passe en réalité (donc réfléchir à des choses style prédictions de branche, déroulement de boucles, épluchage de boucles, etc. en Java ça n'a peu de sens si on applique une vision purement algorithmique aux choses).

Dans un monde parfait, la conception mathématique d'un programme et sa version optimale (au niveau hardware) seraient identiques- malheureusement ce n'est pas le cas, et c'est là que le compilateur peut nous aider avec des petits trucs.

Donc oui, y'a la même notion d'avoir une "couche d'abstraction" pour pas que l'utilisateur ait à réfléchir à tout ce qui se passe dans l'ordinateur, mais bon ça s'arrête là ^^

[Wouf]

Quant aux arbres, ... J'aime pas, mdr. Je sais que c'est puissant, mais j'ai eu une mauvaise expérience en cours ^^'

Euh je te conseille de te replonger dedans alors, parce que les arbres c'est quand même surpuissant.

Si nos ancêtres sont descendus des arbres il y a fort longtemps, c'est sûrement pour une bonne raison. Je dois avoir le gène récessif homozygote
Puis bon, j'ai pas encore mon brevet Tarzan, alors je plongerai dans la forêt plus tard
Plus sérieusement, j'ai zyeuté les quadtrees (2D ) et j'ai prévu de lire un bouquin sur les collisions dans le jeu vidéo .. Enfin, si j'arrive un jour à me libérer des exams/projets à répétition ^^

Donc oui, y'a la même notion d'avoir une "couche d'abstraction" pour pas que l'utilisateur ait à réfléchir à tout ce qui se passe dans l'ordinateur, mais bon ça s'arrête là ^^

Oui, ben c'est surtout là où je voulais en venir
Une analogie se base sur un aspect particulier, elle ne garantit pas l'équivalence en tout point. Un peu comme le fait que 2 mots ne soient jamais parfaitement synonymes ; ils ne le sont souvent que dans un certain contexte.
Ca m'arrive de faire des analogies peu évidentes, car poussées sur l'abstraction, mais je ne pense pas que ce soit le cas ici. Quoiqu'étant fatigué, je pars ptet dans mon trip ^^'

[Morwenn]

Les arbres, c'est chouette, c'est juste pas évident de savoir lequel choisir vu le nombre de possibilités proposées

@Wouf : bien sûr que le test de Fibonacci t'as choqué, il est fait de la manière la plus naïve possible, "histoire de voir", va-t-on dire. Bien entendu, d'une manière générale, c'est totalement inutile d'utiliser comme ça une suite de Fibonacci. Après, quand j'ai parlé des limites des types, du nombre de valeurs calculables, tout ça... je réfléchissais juste aux limites des systèmes utilisés. En fait, j'ai tellement plein de trucs qui me passent dans la tête ces temps-ci - et du temps pour les faire - que je teste à peu près tout ce qui me passe sous la main histoire de me faire ma propre idée des choses. Pour le coup des tables de hachage, j'avoue ne pas encore maîtriser (mais j'irai voir). J'avais entendu parler d'un autre truc, appelé "Judy Array", mais ça avait l'air terriblement galère, donc je préfère revenir sur des notions plus basiques avant de me plonger dans des structures de données aussi complexes (mais intéressantes !)

Le problème pour le moment, en fait, c'est de me faire une idée des systèmes pour savoir que proposer à l'utilisateur d'un langage de script : possibilités, ou facilité d'écriture, ou spécialisation, ou rapidité, etc...
Donc bon, après avoir déterminé les bases de la syntaxe, faut continuer le cahier des charges en pensant à tous les problèmes qui pourraient vite survenir. Enfin bon, je suppose que tu dois mieux t'y connaître que moi là-dedans de toutes façons

@Guillaume : le problème après, c'est de savoir ce que tu dois optimiser toi-même, et ce qui est fait automatiquement par le compilateur ; je sais que les compilateurs ont tendance à faire beaucoup plus de trucs automatiquement (dérouler des listes, calculer tout seul les calculs basiques pour éviter de le faire lors de l'exécution, etc...). Des fois, on se demande si on gagne vraiment du temps, ou si on ne fait que rajouter des lignes de code
Mais c'est vrai que de manière générale, il y a toujours une différence entre le code programmeur et le code machine.



EDIT : Ça part en cacahuète, j'ai renommé le topic