Etude de la complexite memoire en C

**barbsbou** · 12/12/2007, 11h04

bonjour,

Lors d'un projet en C que j'ai du implementer avec un binome, nous devons etudier la complexite temps et memoire de notre algorithme. La complexite temps a été réalisé grace a la fonction clock() dans la librairie time.h.

En ce qui concerne l'etude de la complexite memoire je ne sais pas comment faire.
Auriez-vous une idee??

Merci d'avance.

**souviron34** · 12/12/2007, 14h09

alors déjà la complexité temps n'EST PAS la mesure du temps...

C'est le facteur de proportionalité entre un nombre N de données et le temps que ça prend à faire le calcul.. La notation est O()

Même chose pour la mémoire...

C'est une mesure pour l'ALGORITHME (que tu pourrais faire sur le papier), pas sur l'IMPLANTATION et la mesure machine...

En gros : si tu fais une boucle : O(n), un tri (du style quick sort) : O(n log n), etc etc..

Pour la mémoire, tout dépend des structures, tableaux intermédiares, etc...

Pour N données , combien prenez vous de place mémoire lors de l'algo ?

**laconi87** · 12/12/2007, 17h07

alors dans ce cas la existe t-il une fonction qui permettrer de connaitre la memoire prise pour pour effectuer le calcul. Ansi il serait ensuite possible de calculer le rapport invoquer: N/(Qte memoire utilse)

**Thierry Chappuis** · 12/12/2007, 17h14

Envoyé par laconi87

alors dans ce cas la existe t-il une fonction qui permettrer de connaitre la memoire prise pour pour effectuer le calcul. Ansi il serait ensuite possible de calculer le rapport invoquer: N/(Qte memoire utilse)

Je ne vois pas le besoin d'utiliser une fonction pour étudier la complexité mémoire d'un algorithme. Comme l'a dit souviron34, ce n'est pas un problème de C, mais l'algorithmique. Une feuille de papier et un crayon suffisent à cette analyse. Le forum adapté pour discuter de cette question est: http://www.developpez.net/forums/forumdisplay.php?f=60

Thierry

**barbsbou** · 13/12/2007, 08h18

bonjour,

Je suis tout a fait d'accord avec votre définition de complexité mémoire et temps. Ceci dit il est bien d'étudier la complexité d'un point de vue théorique mais également pratique. Il est clair que je ne viens pas chercher sur ce forum de l'aide theorique mais bien pour m'aider a a calculer la complexité pour des données expérimentales. Je suis en Master deuxieme année recherche mathématiques et c'est comme cela que mes profs souhaitent qu'on aborde l'informatique.
Maintenant mes motivations développées pourriez-vous m'aider a trouver un moyen en C d'étudier la complexité mémoire expérimentale.

Je vous remercie par avance de vos interventions qui nous ferons avancées.

**Emmanuel Delahaye** · 13/12/2007, 11h15

Envoyé par barbsbou

Je suis en Master deuxieme année recherche mathématiques

Ca en jette...

Je vous remercie par avance de vos interventions qui nous ferons avancées.

Et tu as passé le BAC avec une orthographe comme ça ?

**Thierry Chappuis** · 13/12/2007, 12h20

Envoyé par barbsbou

bonjour,

Je suis tout a fait d'accord avec votre définition de complexité mémoire et temps. Ceci dit il est bien d'étudier la complexité d'un point de vue théorique mais également pratique. Il est clair que je ne viens pas chercher sur ce forum de l'aide theorique mais bien pour m'aider a a calculer la complexité pour des données expérimentales. Je suis en Master deuxieme année recherche mathématiques et c'est comme cela que mes profs souhaitent qu'on aborde l'informatique.
Maintenant mes motivations développées pourriez-vous m'aider a trouver un moyen en C d'étudier la complexité mémoire expérimentale.

Je vous remercie par avance de vos interventions qui nous ferons avancées.

Le problème de la mesure, c'est qu'elle est trop influencée par des détails d'implantation et d'environnement pour tirer de réelles conclusions généralement applicables (indépendante de l'architecture matérielle, du système, etc.) au sujet de algorithme étudié. Lorsqu'on mesure le temps d'exécution d'une fonction dans un environnement multitâches, par exemple, il faut tenir compte du surcoût engendré par l'exécution pseudo-parallèle de plusieurs processus et des changements de contexte qui en résulte. Idem pour la compexité mémoire. Prenons le code suivant:

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
#include <stdio.h>
 
struct MaStruct_1 {
    char a;
    int m;
    char b;
    int n;
    char c;
    int o;
    char d;
    int p;
};
 
struct MaStruct_2 {
    int m;
    int n;
    int o;
    int p;
    char a;
    char b;
    char c;
    char d;
};
 
int main(void)
{
    printf("La taille de MaStruct_1 est %u\n", (unsigned) sizeof (struct MaStruct_1));
    printf("La taille de MaStruct_2 est %u\n", (unsigned) sizeof (struct MaStruct_2));
 
    return 0;
}

Les structures MaStruct_1 et MaStruct_2 sont équivalentes du point de vue de l'abstraction qu'elles représentent (si on peut parler d'abstraction ici). Mais les contraintes d'alignements font que, sur ma machine, elles occupent une place en mémoire qui varie de façon substantielle.

Si tu mesures la complexité mémoire (ou de temps) d'un algorithme codé avec les pieds, je doutes que tu puisses en tirer une quelconque conclusion quant à son efficacité intrinsèque et utiliser ces résultats pour les comparer à d'autres algorithmes. Lorsqu'on désire étudier des algos trop complexes pour se prêter à une étude "théorique", l'environnement de test doit être défini avec beaucoup de soins. Il convient également de rester prudent sur les extrapolations qu'il sera possible de pourra faire à l'aide de ces mesures.

Thierry

**aoyou** · 13/12/2007, 12h43

En ce moment, il y a quelqu'un qui se pose la même question que toi dans le forum C++ http://www.developpez.net/forums/sho...d.php?t=455908
Si ça peut faire avancer ton "etude expérimentale"...

**souviron34** · 13/12/2007, 14h09

si tu ne comprends pas ce qu'on dit, et que tu penses que c'est "de la théorie", je te conseille vivement d'abandonner le "Mastère de mathématiques"...

Ce qu'on dit, c'est :

pour la complexité de l'algo :

si tu as par exemple une boucle simple ( for ( i = 0 ; i < N ; i++ ) ) le temps passé est directement proportionnel au nombre d'éléments, donc O(n). Si tu as 3 boucles imbriquées :

Code :

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

1
2
3
4
5
6
for ( i = 0 ; i < N ; i++ ) 
  for ( j = 0 ; j < N ; j++ ) 
     for ( k = 0 ; k < N ; k++ )
       {
            result = toto[i][j][k] ;
       }

le temps seras proportionnel au CUBE du nombre d'éléments, donc O(N^3)...

C'est si compliqué que ça, comme concept ??????????????

De la même manière pour la mémoire, si tu utilises la structure MaStruct_1 de Thierry ci-dessus tu auras en gros 4 int et 4 char par structure, c'est à dire sur une machine 32 bits 20 bytes par structure. Donc si ton algo ne se sert que d'une seule structure, tu occuperas 20 bytes mini. Si tu fais un tableau de 10000 structures, ce sera 200 0000 bytes. Donc tu analyses combien AU MAX tu utilises de mémoire (tu peux éventuellement compter les varaibles locales aussi), dans l'ALGORITHME...

par exemple, il y aura une belle différence à utiliser un tableau et faire de la réallocation par incrément (avec le nombre d'or par exemple) ou faire une liste chainée..

**barbsbou** · 13/12/2007, 19h03

A prioris le fait que je precise, que je sois en master 2 recherche en maths a fait couler beaucoup d'encre (enfin pixel devrais-je dire!!), j'ai juste apporté cette information pour situer un peu plus le cadre de mon projet. Peut-etre que je n'aurais pas du, je tiens tout d'abord a presenter mes excuses de mes fautes au pres d emmanuell qui a l'air d'etre tres sensible, mais je tiens a le rassurer j'ai bien eu mon bac, mais il est clair pas avec le francais (oui oui je sais ca prend un ç...).

Bon une fois ce petit detail preciser, je tiens a remercier egalement souviron 34 de son dedain et de la grande information qu'il m'a apporté NxNxN = N^3 Merki beaucoup.

Pour enfin repondre a la seul reponse constructive a mon sens c'est a dire celle de Thierry Chappuis, je compte (si jy arrive un jour) effectuer les releves memoire dans un environnement le plus ferme aux autres processus (mode recovery sous linux), et que tous les releves seront fait dans la meme periode ce qui pour moi peut avoir un peu de sens tout en relativisant sur le fait que c'est de l'experimentation (en tout cas ca en a pour mon prof).

Merci aoyou pour le lien je vais suivre attentivement le post merci. Pourquoi est-ce si terrible de poser ce genre question en C mais que ca l'est pas en C++?????????? (comprends pas!!!!)

Maintenant je tiens a remercier les personnes de bien vouloir poster des reponses a partir du moment que c'est constructif et arreter les agressions.

Merci d'avance

**souviron34** · 13/12/2007, 19h10

Envoyé par barbsbou

Bon une fois ce petit detail preciser, je tiens a remercier egalement souviron 34 de son dedain et de la grande information qu'il m'a apporté NxNxN = N^3 Merki beaucoup.

je te signale juste que ce n'est pas hautain, MAIS QUE C'EST LA REPONSE A TON PROBLEME !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

C'est ca, la complexite en temps d'un algorithme.........

Quant a la complexite en memoire, je te l'ai donnee aussi...

Alors avant de mettre au panier les avis comme dedaigneux, DAIGNE en tenir compte...

**barbsbou** · 13/12/2007, 19h20

Autant pour moi j'ai cru que

si tu ne comprends pas ce qu'on dit [...] je te conseille vivement d'abandonner le "Mastère de mathématiques"...

et

C'est si compliqué que ça, comme concept ??????????????

étais legerement dedaigneux, c'est vrai que ca l'est pas, vraiment desole!!

Sinon pensez vous que valgrind pourrait donner ces informations....? Je les trouve pas mais peut-etre que je ne les vois pas tout simplement.

Merci d'avance

**diogene** · 13/12/2007, 21h10

Au final, retournons (sereinement) à la question posée qui me semble être :

Existet-il en C un moyen d'obtenir la quantité mémoire utilisée pendant l'exécution d'un programme ?

L'interprétation de cette mesure n'est pas de notre ressort (même si il convient d'en souligner les limites).
La pertinence du choix du professeur d'utiliser cet intermédiaire pour initier ses étudiants à la programmation en C est également hors de notre jugement : On ne connaît ni la teneur ni les méthodes de son enseignement et la seule chose qui soit apparente est que ce n'est pas un enseignement dédié au langage C.

**aoyou** · 13/12/2007, 21h20

Envoyé par barbsbou

Sinon pensez vous que valgrind pourrait donner ces informations....? Je les trouve pas mais peut-etre que je ne les vois pas tout simplement.

Oui, ceci s'appelle Massif. Massif génère un fichier massif.xxx.ps qui représente l'utilisation de la mémoire en fonction du temps et massif.xxx.txt qui dit quel code utilise telle mémoire. Je n'en sais pas plus. A toi de t'amuser avec...

**barbsbou** · 14/12/2007, 08h11

Merci de vos reponse, je vais creuser ca avec attention et je posterais ce qui en resulte pour ceux que ca interesse.

Merki encore.

**souviron34** · 14/12/2007, 13h40

Envoyé par diogene

Existet-il en C un moyen d'obtenir la quantité mémoire utilisée pendant l'exécution d'un programme ?

bah si c'est ça sur unixoide il y a la commande "top"

**Jean-Marc.Bourguet** · 14/12/2007, 15h33

Envoyé par souviron34

bah si c'est ça sur unixoide il y a la commande "top"

C'est un moyen de connaître la quantité de mémoire allouée au programme. Connaître celle utilisée me semble beaucoup plus difficile, hors s'il veut faire des comparaisons entre des mesures et une détermination théorique, c'est la mémoire utilisée qui l'intéresse.

**barbsbou** · 14/12/2007, 18h57

Exactement Jean-Marc Bourguet,

Voila j'ai un tout petit peu creusé l'option (enfin juste pour l'intant gratter un peu!!) --tool=massif de valgrind proposé par aoyou et je pense que cela repondra a mes attentes...
Je vous tiens au courant pour ceux que ca intéresse a l'attendant je conseille un google : "valgrind massif" apporte pas mal d'information, car l'aide de valgrind est pas genial et deplus leur site est down.....mais il reste des bonnes indications merci
developpez.com + google.

Encore merci pour votre aide.

Etude de la complexite memoire en C

C

Discussions similaires

Partager

Partager