Discussion :

[GLSpirit]

salut tout le monde,
Je chercheà optimiser mon code afin d'avoir l'éxecution la plus rapide (surtout en lecture).

Mes qestions serais les suivantes:
un tableau à plusieurs dimension est-il plus rapide qu'un "vecteur de vecteur"?

Quelles sont les différences entre HashMap / map en terme de performance?

En temre de performance lecture/écritre/parcours qelles sont les structures de données les plus rapides?
merci pour vos réposes

[smashy]

a priori , pour les faibles dimensions

question 1

le vecteur de vecteur est plus lent que le tableau multidimensionnel : en effet, il est necessaire de faire une double indirection avant d atteindre les donnees -> ce qui a pour effet de detruire les caches

avec un tableau multidimmensionnel, il suffit de faire des additions et multiplications pour avoir direction l adresse de l element recherche

par exemple pour 2 dimensions:

addresse(elem(x,y) ) = adresse_base + x + y * largeur


en revanche, si la dimension du tableau augmente genre 4 a 5 dimensions ca peux eventuellement etre plus long car le nombre de calculs augmente

pour 3dim

addresse(elem(x,y,z)) = adresse_base + x + y * largeur + z * largeur * hauteur

ici, a moins de connaitre largeur et hauteur a la compilation, a l execution le nombre d operations de multiplication augmente de facon exponentiel (??) avec la dimension donc, au bout d un moment les indirections peuvent devenir plus interressantes (cout = constant)

question 2:

une hash_map est finalement un vecteur de vecteur ...

il existe une fonction F qui pour tout element X te donne l indice du premier vecteur ou inserer / chercher l element. Ensuite, la recherche est lineaire

alors que pour la map, la recherche est logarithmique.

La reponse est donc ca depend (comme d habitude) du nombre d elements (et du choix de la fonction de hachage F)

Si tu as peu d element alors le hachage est meilleur car la recherche va tendre vers un acces immediat (cout = constant = 1 = acces quasi immediat)


pour les performances lecture/ecriture/parcours, il n y a pas de meilleur container dans l absolue : tout depend de l usage

[GLSpirit]

Merci pour ta réponse

Je cherche à optimiser des tableaux de 2 dimension à plus de 500 éléments.
Sachant que je ferais surtout des accés en lecture.
Le tableau me semblait être plus rapide que le reste, es-ce que je me trompe?

[GLSpirit]

La classe vector

Les vecteurs de la STL sont tout à fait semblables aux tableaux que l'on a l'habitude de manipuler en C++. Ils sont néanmoins encapsulés dans des classes pour leur fournir des capacités supplémentaires, en particulier, la croissance dynamique.

Leurs principales caractéristiques sont les suivantes :

* Accès indexé aux éléments en O(1)
* Ajout ou suppression d'un élément à la fin du vecteur sans redimensionnement en O(1)
* Ajout ou suppression d'un élément à la fin du vecteur avec redimensionnement en O(n)
* Ajout ou suppression d'un élément à la fin du vecteur en O(1) amorti
* Ajout ou suppression d'un élément au milieu du vecteur en O(n) où n est la taille du vecteur.

Il convient de mettre un bémol concernant l'ajout d'un élément à la fin d'un vecteur. En effet, les vecteurs sont à croissance dynamique. Autrement dit, si vous décidez d'ajouter un élément dans un vecteur déjà plein à l'aide de la méthode push_back, celui-ci sera agrandi, ce qui nécessite trois opérations :

* Allocation d'un nouveau vecteur
* Recopie des éléments depuis l'ancien vecteur vers le nouveau
* Suppression de l'ancien vecteur

Or, ces opérations peuvent être coûteuses, au pire en O(n). Se pose également la question du choix de la future taille. Andrew Koenig nous explique que la technique la plus efficace consiste à utiliser un redimensionnement exponentiel i.e. à chaque réallocation, la taille du vecteur est multipliée par un facteur (1 + a) où a est un nombre strictement positif. Ainsi, plus le vecteur devient grand, plus il s'agrandira rapidement.

Cette stratégie a l'avantage de rendre les redimensionnement de moins en moins fréquents au détriment d'un encombrement parfois exagéré de la mémoire. Du fait de la fréquence faible des redimensionnements, on peut considérer que la complexité asymptotique (ou amortie) de l'opération d'ajout d'un élément en bout de tableau est en O(1).

La classe deque

Les DQ sont la séquence élémentaire la plus délicate à cerner car intermédiaire entre une liste et un vecteur.

* Elle est très efficace dès lors qu'il s'agit d'ajouter ou de retirer une valeur à l'une de ses extrémités.
* Elle possède un opérateur d'indexation de complexité o(log(n)) amortie
* Les insertions en milieu de séquence sont plus rapides que sur un vecteur sans pour autant atteindre le niveau de performances des listes.


[modifier]
La classe list

Elles modélisent le type liste chaînée habituel. Contrairement aux vecteurs, elles ne possèdent pas d'opérateur d'indexation mais permettent d'ajouter ou de supprimer un élément à n'importe quelle position en O(1).

Bien qu'il n'y ait jamais de place morte dans une liste mais, du fait de la structure de chaîne, l'occupation en mémoire d'une liste est le plus souvent supérieure (mais très peu) à celle d'un vecteur pour le même nombre d'éléments stockés.

[albat0r]

Si tu n'as pas besoin de taille variable tu peux essayer MultiArray de la librairie boost qui est toujours plus rapide à utiliser qu'un "vector de vector"

Documentation Boost.MultiArray

[GLSpirit]

j'ai justement besoin d'un tableau à taille variable

[loufoque]

une hash_map est finalement un vecteur de vecteur ...

Pas vraiment.
Ce serait assez dommage, étant donné que les collisions sont censées être assez rares.
L'implémentation la plus populaire semble être plutôt que si la case i est déjà occupée, on utilise la case i+1.

[smashy]

L'implémentation la plus populaire semble être plutôt que si la case i est déjà occupée, on utilise la case i+1.

pour moi une hash-table c est quelquechose comme

Code :

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

1
2
3
4
5
6
7
vector<int> my_hash[10];
 
insertion :      
 
int i;
 
my_hash[f(i)].push_back(i);            ou f est une fonction de hachage

je ne comprends pas ton explication ...

j en comprend qu on a quelque chose comme

Code :

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

1
2
3
4
5
6
7
int i; /* element a inserer */
 
int my_hash[10];
 
int indice = f(i);
 
my_hash[premier_element_libre_a_partir_de(indice)] = i;

?????


a priori, je dirais plutot que l interet de ce container est de diviser le temps de recherche par une constante (la taille de la table de hachage)

[GLSpirit]

connaissez vous des références (livres) en c++ pour optimiser son code?

[smashy]

Pas vraiment.
Ce serait assez dommage, étant donné que les collisions sont censées être assez rares.
L'implémentation la plus populaire semble être plutôt que si la case i est déjà occupée, on utilise la case i+1.

je sais que certains dictionnaires sont implementes de la facon suivante :

-un buffer de taille fixe initialise a 0.

-lorsque l on ajoute un mot , en recherche l octet (ou bit) correspondant a myhash(mot) , et on met l octet a 1

quand on recherche un mot, on regarde l octet correspondant a myhash(mot)

-si il est a 0 , c est que le mot en entree n existe pas

-sinon on ne peut rien en deduire a cause de collisions


parles tu de quelques choses de similaire ?

[smashy]

connaissez vous des références (livres) en c++ pour optimiser son code?

il existe toute une serie de bouquins genre "exceptionnal C++" ... (tous dans la meme collection) qui permet de progresser en C++, mais je n en connais pas sur l optimisation...

d un autre cote, dans un programme les fonctions qui ont besoin d etre optimisee ne sont pas tres nombreuses en general ("premature optimisation is the root of evil")

Deja pour accelerer, mieux vaut connaitre les container que l on emploie (recherche donc des livres sur la STL)

C est un peu hors propos, mais je considere plutot que la vraie optimisation est celle qui permet de modifier le comportement de toute une application en ne modifiant que quelques lignes de codes.

[GLSpirit]

C est un peu hors propos, mais je considere plutot que la vraie optimisation est celle qui permet de modifier le comportement de toute une application en ne modifiant que quelques lignes de codes.

Bien au contraire c'est tout à fait dans le sujet.
Optimiser ça veut dire optimiser les structres de données, optimiser la modilisation d'un projet, optimiser le comportement de tes classes/fonctions et leur interactions entre elles etc...

J'ai déjà réfléchit sur l'optimisation du comportement de mon projet ("Recuit simulé").
Il me faut utiliser aussi la bonne strcture de données, elle est essentiel dans ce type de projet car on fait plusiers milliers voir plusieurs millions d'itérations dans lesquels dasn lesquels on manipule des données qui peuvent contenir plus d'n milier d'élément dans mon cas.

Donc dans mon algo du recuit simulé, chaque affectation, chaque choix de structure de donnée, chaque choix de comportement auras un impact important sur le temps d'execution voir sur le résultat.

[loufoque]

Je parlais d'une simple implémentation en linear probing.
Voici un exemple tout moche en pseudo code à la française.

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
coefficient = 0.7
 
fonction assigner(cle, element)
  si nombre d'éléments+1 > coefficient*taille du buffer
  alors
    creation d'un nouveau buffer plus grand, de taille multipliée par un certain facteur
    reinsertion de tous les éléments dans ce nouveau buffer
    libération de l'ancien buffer
  finsi
 
  i = hash(cle) % taille du buffer
  tant que vrai
 
    si est_vide(buffer[i])
       on sort
    finsi
 
    si buffer[i].cle == cle
      buffer[i].valeur = valeur
      retourner
    finsi
 
    i = (i + 1) % taille du buffer
  fintq
 
  buffer[i].cle = cle
  buffer[i].valeur = valeur
 
finfonction

Le problème c'est qu'il est nécessaire avec ce genre d'implémentation de pouvoir dire si une case est vide ou pas, avec par une exemple une clé par défaut.
Par contre, on évite les déréférencements et améliore la locality of reference.

Enfin personnellement, c'est comme ça que j'ai toujours implémenté ça en C. En C++, j'utilise simplement les outils déjà existants.

[smashy]

merci beaucoup pour l info (ce fut reellemetn tres instructif )

note : c est la premiere fois que j entends parler de cet algo, en revanche dans mes souvenir de fac (encore assez frais) , la table de hachage, c est quelque chose comme je l ai dit :

my_hash[f(i)].push_back(i);

[GLSpirit]

note : c est la premiere fois que j entends parler de cet algo

Le recuit simulé est une métaheuristique (une heuristique qui peut s'appliquer à plein de problèmes différent.
On étudi ça à un nivo bac+5 (et peut-être en dessous) et ça fait partie de la recherche opérationnelle

je préfère faire du copier collé plutôt que de longues explications pas forcéments convainqantes et pleine de fautes d'orthographe:

source : wikipedia

"Le recuit simulé est une métaheuristique inspirée d'un processus utilisé en métallurgie. Ce processus alterne des cycles de refroidissement lent et de réchauffage (recuit) qui tendent à minimiser l'énergie du matériau. Elle est aujourd'hui utilisée en optimisation pour trouver les extrema d'une fonction.

...

Déroulement du processus [modifier]

Le recuit simulé s'appuie sur l'algorithme de Metropolis, qui permet de décrire l'évolution d'un système thermodynamique. Par analogie avec le processus physique, la fonction à minimiser deviendra l'énergie E du système. On introduit également un paramètre fictif, la température T du système.

Partant d'une solution donnée, en la modifiant, on en obtient une seconde. Soit celle-ci améliore le critère que l'on cherche à optimiser, on dit alors qu'on a fait baisser l'energie du système, soit celle-ci le dégrade. Si on accepte une solution améliorant le critère, on tend ainsi à chercher l'optimum dans le voisinage de la solution de départ. L'acceptation d'une « mauvaise » solution permet alors d'explorer une plus grande partie de l'espace de solution et tend à éviter de s'enfermer trop vite dans la recherche d'un optimum local.

État initial de l'algorithme [modifier]

La solution initiale peut être prise au hasard dans l'espace des solutions possibles. À cette solution correspond une énergie initiale E = E0. Cette énergie est calculée en fonction du critère que l'on cherche à optimiser. Une température initiale T = T0 élevée est également choisie. Ce choix est alors totalement arbitraire et va dépendre de la loi de décroissance utilisée.

Itérations de l'algorithme [modifier]

À chaque itération de l'algorithme une modification élémentaire de la solution est effectuée. Cette modification entraîne une variation ΔE de l'énergie du système (toujours calculée à partir du critère que l'on cherche à optimiser). Si cette variation est négative (c'est-à-dire qu'elle fait baisser l'énergie du système), elle est appliquée à la solution courante. Sinon, elle est acceptée avec une probabilité e^{-\frac{\Delta_E}{T}}.

On itère ensuite selon ce procédé en gardant la température constante.

Programme de recuit [modifier]

Deux approches sont possibles quant à la variation de la température :

1. Pour la première, on itère en gardant la température constante. Lorsque le système a atteint un équilibre thermodynamique (au bout d'un certain nombre de changements), on diminue la température du système. On parle alors de paliers de température.
2. La seconde approche fait baisser la température de façon continue. On peut alors imaginer toute sorte de loi de décroissance. La plus courante étant Ti + 1 = X * Ti avec X < 1 (assez couramment X = 0.99).

Dans les 2 cas, si la température a atteint un seuil assez bas fixé au préalable ou que le système devient figé, l'algorithme s'arrête.

La température joue un rôle important. À haute température, le système est libre de se déplacer dans l'espace des solutions (e^{-\frac{\Delta_E}{T}} proche de 1) en choisissant des solutions ne minimisant pas forcément l'énergie du système. À basse température, les modifications baissant l'énergie du système sont choisies, mais d'autres peuvent être acceptées, empêchant ainsi l'algorithme de tomber dans un minimum local."