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