Je suis arrivé ici deux programmes avec moi, les deux font exactement la même tâche. Ils sont simplement en train de définir une matrice booléenne / vecteur à la valeur true. Le programme utilisant le vecteur prend 27 secondes pour exécuter alors que le programme impliquant une matrice avec 5 fois plus de taille est inférieur à 1 s. J'aimerais connaître la raison exacte de pourquoi il y a une telle différence? Sont des vecteurs Vraiment cet inefficace?
Programme à l'aide de vecteurs p> exécution - 27 secondes p> programme à l'aide de tableau p> #include <iostream>
#include <ctime>
using namespace std;
int main(){
const int size = 10000; // 5 times more size
time_t start, end;
time(&start);
bool v[size];
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
v[i] = true;
}
}
time(&end);
cout<<difftime(end, start)<<" seconds."<<endl;
}
4 Réponses :
Vecteur de Bool est une spécialisation de modèle d'enfant bâtard qui ne devrait jamais avoir existé et stocke réellement 1 bool dans chaque bit. L'accès à celui-ci est plus compliqué en raison de la masquage et de la logique changeante, il sera donc certainement un peu plus lent. Cliquez ici pour certaines informations sur le vecteur de Bool. En outre, vous pouvez exécuter une construction non optimisée (presque certainement donné les temps que vous avez énumérés, 27 secondes est scandaleuse pour 4 millions d'itérations). La bibliothèque de modèles standard repose très fortement sur l'optimiseur pour faire des choses comme des appels de fonctions en ligne et des temporaires éloids. L'absence d'optimisation provoque une dégradation de performances particulièrement forte pour le vecteur de bool car elle doit renvoyer un objet proxy lorsque vous l'indiquez, car vous ne pouvez pas prendre l'adresse d'un peu, donc Cliquez ici pour plus d'informations sur des conteneurs proxotés (la dernière moitié est sur le vecteur de Bool) En outre, de nombreuses implémentations stl ont des bits de débogage utiles qui ne font pas partie de la norme qui vous aident à attraper des bogues, mais faites vraiment glisser la performance. Vous voudrez vous assurer que ce sont désactivés dans votre construction optimisée. Une fois que vous allumez l'optimiseur, posez les réglages appropriés (c'est-à-dire aucun débogage de stl activé) et teste la même chose dans Les deux boucles, vous verrez presque aucune différence. Je devais faire votre boucle beaucoup plus grande pour tester sur ma machine, mais voici deux buildes de votre vecteur de boucle Bool sur ma machine, montrant l'impact de l'optimiseur. Drapeaux sur le code STL
Ya je pense aussi. Je gère le même scénario et cela a fallu presque la même heure.
VC2005 + en particulier a une vérification liée à la vérification et à la validation des itérateurs des créances de débogage pour tous les objets STL.
Merci Don.neufeld, votre explication ainsi que le lien sont vraiment utiles. Bon d'apprendre quelque chose de nouveau :-)
Vous devriez également essayer un std :: deque
D'autres réponses sont très bonnes, mais vous pouvez facilement vous répondre vous-même par Ajouté: En réponse aux commentaires, laissez-moi vous montrer ce que je veux dire. Je passe à VC sous Windows, mais cela fonctionne sur n'importe quelle langue / système d'exploitation. J'ai pris votre premier programme et une taille accrue à 20000, il serait donc assez long. Ensuite, alors qu'il s'agissait de plusieurs pieux. Ils ressemblent tous à ceci: alors ce que cela dit est qu'il dépense essentiellement est ce code: qui appelle: Ce code (que j'ai reformaté un peu un peu): qui appelle: ce qu'il fait est d'écrire 68 octets de La fraction du temps qu'il dépense faire cela est près de 100%, car il le faisait sur chacun des nombreux échantillons prises. Pourriez-vous avoir deviné que c'est ce qu'il dépense presque tout son temps à faire? Je ne pouvais pas avoir. Ceci est, bien sûr, une construction de débogage. Si vous passez à une version de déverrouillage, mais activez les informations de débogage, toutes ces fonctions sont inlinées et optimisées, de sorte que cela dépasse 30 fois plus vite, et encore une fois, les packshots racontent exactement ce que ça fait. SO - Les gens peuvent vous dire ce qu'il pourrait faire faire, mais cela montre Comment savoir pour vous-même ce qu'il est sur votre environnement, il sera sans aucun doute différent. [] appelle l'opérateur commencer . Dans plus de détails: 0xcc sur la pile (pour certains Débogage Raison) Dans le cadre d'obtenir l'adresse Début du vecteur, dans le cadre de l'adresse de l'adresse de V [i] , avant de faire l'affectation.
Oui en effet. Plutôt que de comprendre les propriétés des données de données de bibliothèque standard, dirigez-le à des informations sur la manière de profiler votre code dans un autre système d'exploitation qu'il n'utilise réellement . Et si vous avez déjà essayé de déboguer ou de profiler ou de lire des conteneurs de bibliothèque standard, vous saurez que ce n'est pas exactement facilement lisible. Le profilage peut vous dire quelles lignes de code provoquent le ralentissement, mais cela ne répond peut-être pas à la question de ce qui se passe .
@jalf: Allez. Il est indépendant du système d'exploitation et le profilage car il est couramment compris peut ne pas vous dire ce qui se passe, mais Speckshots vous dira exactement ce qui se passe tant qu'il y a du code source de la bibliothèques.
... C'est la vieille scie à donner à quelqu'un un poisson par rapport à leur poisson.
Vous pouvez le tromper en utilisant std :: vecteur std :: vecteur
Correction de votre message pour utiliser le formatage du code. Les crochets ont disparu sans elle
Au lieu de vecteur vecteur sans signé caractère ou si le compilateur prend le support std :: uint8_t ). Aucune raison d'utiliser plus d'espace que nécessaire. Mais certainement pas vecteur
Une raison d'utiliser plus d'espace est une meilleure vitesse sur la plupart des architectures 32 bits.
La différence de vitesse entre int et char ne vaut probablement pas la peine d'utiliser 4X plus de mémoire pour (surtout que la cache manque beaucoup plus mal).
std :: vecteur n'est pas un conteneur. Lisez ceci: gotw.ca/publications/mill09.htm
Note importante: même si vous arrivez à la bonne conclusion, vous n'effectuez pas une comparaison appropriée. Vous exécutez n ^ 2 itérations de la boucle la plus interne (le
V [i] = true instruction), mais n est 2000 dans un test et 10000 dans l'autre, donc vous faites vraiment 25 fois plus tard Beaucoup de travail, pas 5 fois plus, mis à part la différence entre un vecteur et un tableau uni. Cela rend effectivement la différence encore plus prononcée.@ user235022 Avez-vous voulu dire
v [j] = true; au lieu dev [i] = true ? Sinon, il devrait être très simple pour le compilateur d'optimiser la boucle interne, car vos actions ne dépendent pas de la variable de boucle.