Temps d'acces aux elements de tableaux, vector, etc.

Bonjour,

Ma question porte donc sur le cout d'acces aux elements de differents conteneur. Pour un tableau, on a coutume de dire que c'est une complexité en O(1) mais cela ne signifie pas pour autant qu'il est plus rapide d'acceder 10 fois a un element comme suit:

Code:

---

1 2	... += tab [ligne][col]; //10x

---

plutot que

Code:

---

1 2 3

int tmp = tab[ligne][col]; ... += tmp; //10x

---

Ensuite, qu'en est-il lorsque l'on compare le temps d'acce dans un tableau bidimensionnelle et dans un vector analogue?

Merci:lol:

8O 8O 8O

Personne ? C'est assez inhabituel sur ce forum...:?

Salut,

Il n'y aura pas de difference flagrante entre tes exemples, ca depend de plusieurs choses :

- Comment le compilateur va optimiser ta variable temporaire dans le code assembleur genere
- Comment est faites la gestion de la memoire.

A priori le plus rapide pour acceder a une element d'un tableau est de travailler directement sur un buffer, et donc dans le cas d'un tableau bidimensionnel d'utiliser un offset. Mais le vecteur est presque aussi rapide. Dans l'ensemble tu peux tenir compte de la complexite du conteneur pour cette operation.

As-tu réellement besoin d'optimiser ce genre de chose ? Personnellement je n'ai jamais eu à me poser une question aussi "primitive", même dans des applications temps réel où les performances comptent.

Je suis sur une appli de vision temps reel -> pour du 15 Hz ca nous donne du 60 ms tout compris. L'utilisation massive de tableau/vector bidimensionnelle et les acces repetés (y a des boucles que l'on ne peut pas eviter malheureusement) me font dire qu'il serait peut etre possible de grapiller un peu de temps la dessus

Dans ce cas, pourquoi ne pas faire les tests directement dans ton application, tout simplement ? D'autant plus que ce sera la meilleure des réponse que tu pourras avoir.

l'accès d'un élément dans un tableau est équivalent à une addition et un déréferencement.

En général, on essaie d'avoir des algorithmes qui exploitent la séquentialité des éléments.
Le grand classique, ce sont les Numerical Recipies.
Après, tu as plein de BLASseries qui trainent à droite à gauche. Des liens depuis le wiki de boost.uBLAS et d'autres depuis le site du projet Blitz++.

Dans tous les cas, si tu veux faire des maths haute-perf, n'utilises pas des conteneurs de conteneurs (genre vecteur de vecteurs), mais des types matriciels dédiés.

Merci... je vais voire tout ca. D'une part en faisant des tests l'aide d'un profiler et au besoin aller voir du coté des Numerical Recipicies (j'avais completement zappé).

J'ai une autre question sur les perfs..... mmmmm... bon, je joue pas les paresseux et j'ouvre un autre topic.