Supposons que j'ai une chaîne si si / eus-si-si-if: Ce que je me demande, si je garde une carte, sera-t-il mieux en termes de performance? (en supposant que les clés sont des entiers)
7 Réponses :
Pourquoi n'utilisez-vous pas un commutateur AA?
swich(x.GetId())
{
case 1: /* do work */ break; // From the most used case
case 2: /* do work */ break;
case ...: // To the less used case
}
Juste pour info: certains compilateurs reconnaîtront un ensemble de cas «dense», c'est-à-dire un groupe d'entiers (principalement) consécutifs, et optimisez le commutateur dans un saut indexé. Ainsi, souvent «optimiser la main» les cas fréquents est superflu.
commutateur est la meilleure chose que je pense
Afaik, les déclarations de commutation ne sont pas significativement meilleures que si / sinon en termes de performance, n'est-ce pas?
Qui sait, pourquoi ne-tu pas le profil et voir? Deviner n'a pas de mérite. Si vous nous avez dit ce que vous faites (la grande image), nous pourrions donner de meilleurs conseils. Cela dit, les déclarations de commutation ont tendance à mieux performer, pour certains nombres de cas, IIRC.
@Perezvon: Non. Switch crée généralement une table de saut si les limites ne sont pas grandes, donnent à O (1) performance.
Qu'il s'agisse d'une prestation de performance ou non, étant donné le code exemple, un commutateur sera probablement plus facile à lire et à entretenir que d'une chaîne si / el / code> chaîne.
Le code d'origine a un getid () sur chacune des 50 branches du si ; Sauf si cela est optimisé (et ce n'est possible que si le compilateur peut reconnaître que getid () renvoie la même valeur sur chaque appel), une moyenne de 24 appels inutiles vers getid () aura un impact significatif sur la performance. Ainsi, commutateur est certainement mieux dans la performance.
La meilleure solution serait un Si vous voulez avoir une fantaisie, vous pouvez utiliser une structure de données contenant des pointeurs sur des fonctions qui gèrent tout ce que c'est que c'est dans les accolades. Si vos valeurs d'identification sont consécutives (c'est-à-dire des chiffres compris entre 1 et 50), un tableau de points de fonction serait le mieux. S'ils sont étendus, une carte serait plus appropriée. Switch instruction. Cela vous permettra de vérifier la valeur de x.getid () une seule fois, plutôt que (en moyenne) 25 fois pendant que votre code fait maintenant.
Les cartes (généralement) sont implémentées à l'aide d'arbres noirs rouges qui donnent des recherches O (log n) car l'arborescence est constamment maintenue en équilibre. Votre liste linéaire de si les déclarations seront o (n) les pires cas. Donc, oui une carte serait nettement plus rapide pour la recherche.
Beaucoup de gens recommandent d'utiliser une instruction de commutation, ce qui peut ne pas être plus rapide pour vous, en fonction de vos déclarations réelles. Un compilateur peut parfois optimiser le commutateur en utilisant une table de saut qui serait O (1), mais cela n'est possible que pour des valeurs indéfinies; Par conséquent, ce comportement peut être quelque peu non négligeé. Bien qu'il existe un excellent article avec quelques conseils sur l'optimisation des relevés de commutation ici Optimisation du code C et C ++ < /a >.
Vous pouvez même formuler une arborescence équilibrée manuellement, cela fonctionne mieux pour les données statiques et je devrais récemment créer une fonction pour trouver rapidement le bit dans un octet (ceci a été utilisé. Dans une application intégrée sur une interruption d'épingle d'E / S et devait être rapide lorsque 99% du temps seulement 1 bit seraient définis dans l'octet): ceci donne Une recherche constante en 3 étapes pour l'une des 8 valeurs qui me donne des performances très déterministes, une recherche linéaire - donnée de données aléatoires - une recherche en 4 étapes moyenne, avec un meilleur cas de 1 et pire cas de 8 étapes. C'est un bon exemple d'une gamme qu'un compilateur n'ophaberait probablement pas à une table de saut car les 8 valeurs que je recherche sont si éloignées: 1, 2, 4, 8, 16, 32 , 64 et 128. ça Âté devra créer une table de position très rare 128 avec seulement 8 éléments contenant une cible, qui sur un PC avec une tonne de RAM pourrait ne pas être une grosse affaire, mais sur un microcontrôleur, ce serait tueur.
Même si un commutateur ne peut pas en faire une table, je pense que le compilateur peut automatiquement commander des comparaisons pour la transformer en une recherche binaire pour vous.
Peut être le mot clé, bien sûr que le compilateur peut faire toutes sortes de choses, mais si ce n'est pas dans la norme et / ou votre compilateur n'est pas indispensable, vous devrez vivre avec le Nature non déterministe de "Can", "pourrait" ou "peut". Une construction fonctionnera rapidement, vous effectuez un changement et votre prochaine version est lente, vous devez ensuite déterminer pourquoi tout à coup votre commutateur se décomposait dans IF / Equivalent au lieu d'une table BST ou de saut. Une table de saut à base de carte sera plus lisible, déterministe, extensible et plus rapide dans la plupart des cas.
La réponse, comme avec la plupart des questions relatives aux performances, est peut-être.
Si les identifiants sont dans une plage fortunée, un commutateur peut devenir une table de saut, fournissant des recherches de temps constantes à tous les identifiants. Vous n'obtiendrez pas beaucoup mieux que cela, à court de refonte. Sinon, si les identifiants sont consécutifs, mais vous n'obtenez pas une table de saut hors du compilateur, vous pouvez forcer le problème en remplissant un tableau avec des pointeurs de fonction.
[à partir d'ici ON, a A La redédition peut vous permettre d'éviter la question de tous ensemble. Peu importe la manière dont vous le mettez en train de le mettre en œuvre, cela sent les problèmes. Je ne peux pas m'empêcher de penser qu'il y a une meilleure façon de gérer cela. Switch fait référence à un Generic si / else chaîne]
mappe fournit une recherche logarithmique pire cas pour tout identifiant donné, tandis qu'un commutateur ne peut garantir que linéaire. Toutefois, si les identifiants ne sont pas aléatoires, trier le commutateur des cas par utilisation pourraient vous assurer que le pire des scénarios est suffisamment rare que cela n'a pas d'importance.
mappe entraînera une surcharge initiale lors du chargement des identifiants et de les associer avec les fonctions, puis d'inclure une surcharge d'appeler un pointeur de fonction chaque fois que vous accédez à un ID. Un commutateur entraîne une surcharge supplémentaire lors de la rédaction de la routine et éventuellement une surcharge importante lors du débogage.
Si j'avais vraiment un commutateur potentiel de cinquante possibilités, je penserais certainement à un vecteur de pointeurs à fonctionner.
Un bon design: je voudrais initialiser statiquement la fonction Vecteur VP.
Dans certains cas, vous devrez peut-être avoir géré le cas (x.getid n'est pas compris entre 0 et max), il nécessitait également plus de mémoire que nécessaire (par exemple: nous voulons vérifier le cas pour juste x = 1-50, et x = 100 ... ou tout autre motif.
Si vous comparez à une carte, même avec des espaces vides, vous pouvez enregistrer la mémoire. En plus des pointeurs de fonction, il stocke les clés et toutes les données diverses nécessaires pour maintenir l'arborescence [une couleur et trois pointeurs, probablement]. Beaucoup de variables.
Merci pour vos commentaires. Oui, si les options ne sont pas contiguës, il ne s'agit pas d'une solution soignée, mais elle peut toujours fonctionner si vous êtes capable de convertir le X.getid () au domaine 0..max-1 avec une fonction plus ou moins simple ( S'il y a des lacunes "aléatoires", vous devrez équilibrer l'avantage d'un accès direct contre la mémoire inutilisée). À propos des limites, vous pouvez créer une fonction inline afin d'accéder au vecteur. Cela obtiendra le résultat souhaité sans des pénalités de performance (minimum).
Il y a beaucoup de suggestions impliquant un cas de commutation. En termes d'efficacité, cela pourrait être mieux, pourrait être la même chose. Ne sera pas pire.
Mais si vous ne définissez pas / retourner une valeur ou un nom basé sur l'identifiant, alors oui. Une carte est exactement ce dont vous avez besoin. Les conteneurs STL sont optimisés et, si vous pensez que vous pouvez optimiser mieux, vous êtes incroyablement intelligent ou stupéfiant. P>
Par exemple, un seul appel à l'aide d'une STD :: Carte appelée MyMap, P>
if(x.getID() == ...){thisvar = ...;}
Avez-vous sérieusement 50 déclarations d'affilée? Je pense qu'une "boucle" pourrait être en ordre ...
Vous devriez ajouter ce que vous faites dans vos déclarations si. À propos, pour le balisage de code, sélectionnez le code et utilisez le bouton
010 ou simplement indenter le code par 4 espaces.Vous pouvez le mesurer vous-même et voir lequel est plus rapide, si, si, si cela pourrait être une solution plus rapide que la carte dans votre cas. Exécutez un test de charge avec des itérations 1M et voyez combien de temps il faut pour chaque cas
Totalement dépendant de ce que vous faites à l'intérieur de chaque bloc, mais avez-vous considéré le polymorphisme pour éliminer ou réduire tous ces indicateurs laids SI-ESSES?