Discussion :

[NiamorH]

Code :

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

tab[2] = var;

Une chose que tu ne semble pas avoir compris, c'est que ce code ne fait pas appel à l'opérateur = de ton tableau. tab[2] représente un int ici.

Code :

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

tab = autreTableau;

Dans ce code oui, il faudrait implémenter l'opérateur = car on affecte tout un tableau à un autre.

[rouliane]

d'accord je vois.
Mais j'ai fait un constructeur par copie, donc c'est suffisant, non ?
Le voici :

Code :

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

1
2
3
4
5
6
          tableau( const tableau & source ){
          n=source.n;
          nx=source.nx;
          // v=source.v; NON ! 
          for(int i =0;i<n;i++) v[i]=source.v[i];                 
                   }

[Pacorabanix]

Bonjour rouliane, alors désolé d'avoir supprimé le message que tu as mis en quote ! En le revoyant (et sachant qu'il était tard... euhh tot... euhh tard enfin bref), et voyant les 2 autres, je l'ai trouvé complètement inutile... Ravi qu'il t'aide!


Juste une précision sur une de tes dernière questions:

lvalue : une valeur "gauche" (left value) . C'est à dire un nom de variable (à entendre "l'adresse valide d'une variable" ). Bref une valeur qui permet d'en stocker une autre.

rvalue : une valeur droite, c'est à dire une constante, uns variable, l'adresse d'une variable, enfin bref : beaucoup plus de possibilité, mais ce n'est utilisé qu'en lecture.

par exemple :

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
 
int a, b;
 
b = 3; //valable
a = 5; //valable
 
b = 10; //valable
a = b; //valable
a = b+3; //valable
b+3 = a; // ERREUR ! b+3 n'est pas une lvalue
3 = b; // ERREUR ! 3 n'est pas une lvalue.
//[EDIT : ]
 
int &alias= &a;
// alias est maintenant un autre nom pour a (pas tout a fait sur de la syntaxe)
 
&a = &b; // erreur on ne peut pas modifier l'adresse attribuée a un nom de variable dans le code, &a est une rvalue mais pas une lvalue
 
// en général, toute constante ne peut etre que rvalue et pas lvalue

lorsqu'une fonction retourne un "&int", ça veut justement dire qu'elle doit renvoyer l'adresse d'une variable (valable, pas comme un *int qui peut être NULL), c'est à dire une valeur utilisable comme lvalue

[rouliane]

ah merci !

J'essaye d'avance un peu dans l'exo, et on me demande de donner la complexité de l'algorithme suivant :

Code :

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

1
2
3
tableau a;
for (int i=0; i<n; i++)
a.push_back();

où on a :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
          T * push_back( const T & t ) {
 
            if (nx==n) 
                { nx=nx+20;
                  T*w=new T[nx];
                  for (int i=0;i<n;i++) w[i]=v[i];
                  w[n++]=t;
                  delete [] v;                
                  v=&w[0]; 
                  return v;                         
                }
 
            else v[n++]=t;      
          }

je dirais que c'est en O(n²) car on aura 2 boucles, mais je n'en suis pas sur.
On em demande ensuite comment faire pour avoir une complexité en O(nxln(n) ).
La je sais pas trop, j'ai lu quelques papiers sur les tris, c'est lié à ça ?

[Pacorabanix]

Je rajoute donc un conseil : il faut 2 versions de operator[]. Une qui retourne une lvalue Type& (celui que tu as essayé de faire, mais il faut retourner l'adresse de v[i] et non sa valeur).

Et une qui retourne une rvalue (on veut juste lire la variable) : const Type&.

Pour un int, la fonction [] qui lit pourrait simplement etre "const Type", voir "Type", mais pour rester général et permettre de faire un tableau avec des types plus compliqués il faut bien retourner un const Type&, pour éviter la copie complète de l'objet.

[Pacorabanix]

ah merci !

J'essaye d'avance un peu dans l'exo, et on me demande de donner la complexité de l'algorithme suivant :

Code :

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

1
2
3
tableau a;
for (int i=0; i<n; i++)
a.push_back();

...

je dirais que c'est en O(n²) car on aura 2 boucles, mais je n'en suis pas sur.
On em demande ensuite comment faire pour avoir une complexité en O(nxln(n) ).
La je sais pas trop, j'ai lu quelques papiers sur les tris, c'est lié à ça ?

La complexité peut etre étudiée pour tout algorithme (=série d'opérations) qui dépend d'un nombre (ici n). Les tris sont un exemple assez primaire d''algorithme, mais là le code que tu as c'est celui là qu'il faut étudier.

De façon assez simple : compte le nombre d'opérations.

Tu ne fais absloument pas toujours 2 boucles ! tu fais une deuxième boucle seulement si le n doit dépasser nx

donc jusqu'à n=20, il n'y a que 20 opérations !
Pour aller à n=21 par contre on en fait :
20 (celles d'avant), une réallocation (donc 20 copies), et un ajout. = 41 !
n= 22 -> 42
...
n= 40 -> 60
n=41 -> 60 (d'avant) plus une réallocation (60 copies) et un ajout, donc 121.

après c'est des maths pour trouver une formule qui exprime cela.

il y aura toujours n ajout. Mais tous les 20 n on fait encore n opérations. Il y a donc Ncarré/20 copie en tout selon moi (pas tout à fait sur). La formule est est de toute façon pas exacte, car j'insinue qu'il y a des "20ème de réallocations", mais globalement ça revient à ça mathématiquement (ça se trouve en écrivant des "sommes" et en simplifiant les formules, c'est des maths)

Ce qui fait qu'on "simplifie" : O(n+ncarré/20) = O(ncarré). Tu avais juste.


En fait, ce qu'il faut comprendre, c'est que malgré le fait qu'on économise pas mal d'opérations en faisant des réallocations par "paquet de 20" et non a chaque fois, au niveau de la *complexité* ça ne change rien, c'est toujours O(ncarré) comme tu dis, c'est toujours *désastreux* (si ton tableau a 10000 éléments... nb d'opérations = 10'000 + 1'000'000'000/20 = 500'010'000 ... n2 = 1'000'000'000, c'est donc une bonne approximation au niveau des ordres de grandeur)


L'idée pour obtenir une variation n * log(n) au lieu de ncarré, c'est de faire de moins en moins de réallocations au fur et a mesure que le tableau grossi. Ici on en fait en fait tous les 20, on en fait donc toujours autant. Il faudrait que le nombre que tu ajoutes à nx (20) dépende de sa taille actuelle.

Un indice : la solution a deja été proposée par quelqu'un ici

[EDIT] Beaucoup moins désastreux le n x log(n) : dans l'exemple donnée : (132 880 opérations seulement, 1000 fois moins, pour log en base 2...)

[Pacorabanix]

Pour te donner un exemple complet de calcul de complexité, et pour corriger mon estimation : je me suis mis au papier et au crayon pour calculer correctement le nombre d'opérations :


un exemple avec n=1000 :

1000 (affectations) + (20 + 40 + 60 + ... + 1000) (copies des tableau lors des réallocations)

ça donne avec des n :

n + (20 + 40 + 60 + ... + n)
= n + 20 * (1+2+3+...+ n/20)
= n + 20 * SOMME(de k=1 jusqu'à k=n/20) de k
ici j'utilise le fait que 1+2+3+...+QQCHOSE = QQCHOSE * (QQCHOSE + 1) / 2
= n + 20 * ( n/20 * (n+20 + 1) / 2 )
=n + nCarré/40 + n/2
= 3n/2 + nCarré/40

[HanLee]

Le push_back() de std::vector est en moyenne en O(1), donc n push_back() n'aura qu'une complexité linéaire, on peut faire mieux que le n ln(n) (d'ailleurs d'ou vient ce résultat ?), en allouant de manière géométrique.

[rouliane]

d'accord, je comprends mieux.
Je voyais bien qu'on ne faisait pas toujours n² boucle, mais on sent bien que ça va etre en n² même si c'est mieux de le vérifier parcque c'est pas si évident le calcul.
J'ai essayé de voir pour l'histoire de diminuer la valeur qu'on ajoute à chauqe fois. Il faut donc que la valeur qu'on ajoute ( appelons la val) soit fonction du nombre d'appels de la méthode push_back ?

[rouliane]

Le push_back() de std::vector est en moyenne en O(1), donc n push_back() n'aura qu'une complexité linéaire, on peut faire mieux que le n ln(n) (d'ailleurs d'ou vient ce résultat ?), en allouant de manière géométrique.

C'est une question qui m'est posée dans l'exercice.
je vais voir ce que sont les méthodes géométriques, merci.

[Pacorabanix]

J'ai essayé de voir pour l'histoire de diminuer la valeur qu'on ajoute à chauqe fois. Il faut donc que la valeur qu'on ajoute ( appelons la val) soit fonction du nombre d'appels de la méthode push_back ?

Non pas par rapport à la boucle, mais par rapport a qqchose d'interne au tableau. La boucle, c'est juste une utilisation du tableau avec plein de push back. A priori tu ne dois pas pouvoir savoir comment on utilise ton tableau.

Il faut que tu réalloues selon *la taille actuelle du tableau* (c'est justement cela "de manière géométrique")

[rouliane]

Non pas par rapport à la boucle, mais par rapport a qqchose d'interne au tableau. La boucle, c'est juste une utilisation du tableau avec plein de push back. A priori tu ne dois pas pouvoir savoir comment on utilise ton tableau.

Il faut que tu réalloues selon *la taille actuelle du tableau* (c'est justement cela "de manière géométrique")

Ca doit donc etre fonction de nx ?

[Pacorabanix]

exactement ! Après, de quelle façon c'est comme tu veux. val = nx, val = 2*nx, 3*nx ...


Donc la taille du tableau va évoluer en doublant (ou triplant, quadruplant) a chaque fois ! (de manière géométrique, comme les suites du meme nom )

[rouliane]

exactement ! Après, de quelle façon c'est comme tu veux. val = nx, val = 2*nx, 3*nx ...


Donc la taille du tableau va évoluer en doublant (ou triplant, quadruplant) a chaque fois ! (de manière géométrique, comme les suites du meme nom )

Je comprends pas : avec ce que tu me dis, si la taille de mon tableau croit, val croit aussi, donc la réallocation aussi.
Faudrait pas plutot diviser quelque chose par nx ?

[rouliane]

non oublie le message précédent, je viens de comprendre
Merci beaucoup !

[Pacorabanix]

Le push_back() de std::vector est en moyenne en O(1), donc n push_back() n'aura qu'une complexité linéaire, on peut faire mieux que le n ln(n) (d'ailleurs d'ou vient ce résultat ?), en allouant de manière géométrique.

Donc en effet, je me suis encore gouré (il *faut* toujours faire confiance aux maths plutot qu'à une simple intuition ), le fait de faire des réallocations de manière géométrique faitg qu'au final l'insertion de n nouveau éléments est de complexité O(n) = n et non pas n*log(n) comme je pensais !


Je suis très curieux de savoir quelle est la solution de ton prof, où si lui aussi a confondu (ce qui serait inquiétant). Si tu y penses rouliane, indique-nous stp!

[JolyLoic]

Ce qui est amusant, c'est que mathématiquement, c'est parce que l'ajout 1 à 1 de n éléments est en O(n) que l'on dit que l'ajout d'un élément est en O(1) amorti, et non pas parce qu'un ajout est en O(1) amorti que l'on pourrait déduire que n ajouts sont en O(n)...

Maintenant, un algo en O(n) est aussi en O(n ln n) ou en O(n^n) ou... donc le prof qui dit que la méthode avec l'allocation géométrique qui a une complexité en O(n) est en O(n ln n) n'a pas entièrement tort...

Le raisonnement erroné qui abouti à ça consiste à dire qu'avec la méthode indiquée, pour faire n ajouts, le nombre d'agrandissement du tableau sera en O(ln n), chaque agrandissement étant lui même en O(n), on a une complexité totale en O(n ln n). Mais les premiers agrandissements sont plus petits que les derniers, on peut donc avoir une meilleure approximation.

Le bon raisonnement est donc de dire que l'on part d'une taille initiale (mettons 1 pour simplifier, ça n'a pas d'importance, c'est juste un coefficient constant dans le calcul du O), et posons a comme facteur d'agrandissement. On va donc faire :
1 copie pour insérer
1 copie pour réallouer
a-1 copies pour insérer
a copies pour réallouer
a² - a copies pour insérer
a² copies pour réallouer
a^3 - a² copies pour insérer
a^3 copies pour réallouer
...
a^j copies pour réallouer
n -a^(j-1) copies pour insérer

Avec j le plus petit nombre tel que a^j > n (et donc de l'ordre de log_a(n))

En simplifiant, le nombre d'insertion est toujours plus faible que le nombre de copies pour réallocation, on ne va donc garder que ce dernier (avec un facteur 2 constant qu'on ignore). On a donc un nombre d'opérations total en :
O(1 + a + a² + a^3 + ... + a^j)
= O((1-a^(j+1)) / (1-a)) = O(a^j) = O(n).



Un point intéressant est le choix du coefficient d'agrandissement. Certaines valeurs ont pour propriétés de ne pas trop fragmenter la mémoire.