J'ai vu des réponses ici pour des langages spécifiques, des commutateurs avec plus de 5 cas optimisés avec des tables de saut pour garantir une heure d'accès constante pour tout cas.
Est-ce que c'est vrai pour C / C ++?
Est-ce en particulier pour GCC? Pour Visual Studio?
Sinon, trierait des cas dans l'ordre de fréquence d'occurrence?
6 Réponses :
C'est ce que le compilateur fera pour vous. En cas de GCC, il utilisera une table de saut.
La norme ne garantit rien de la manière dont l'instruction de commutation sera mise en œuvre. Je n'ai jamais vu un compilateur produira une table de hachage, bien que très peu produira une table de saut. Sauf si ma mémoire ne fonctionne même plus que d'habitude, VS et GCC peuvent produire des tables de saut lorsque les cas sont suffisamment denses (pour différentes valeurs de «suffisamment»). Malheureusement, il est presque impossible de dire (ou nécessairement même de comprendre) lorsque le tri par fréquence d'occurrence aidera - il est différent non seulement entre les compilateurs, mais même entre différentes versions du même compilateur.
@PRutruza: Vous pourriez corriger votre message d'origine
C (et par extension C ++) n'allume que des types d'entiers, de sorte que le hachage n'est pas nécessaire. Le compilateur utilisera généralement un idiome approprié à l'architecture que vous compilez. Cela pourrait être l'adressage indexé (si une petite gamme est utilisée), des tables de saut ou quelque chose de tout à fait différent.
Le hachage n'est pas nécessaire, mais il est parfois possible d'optimiser une série d'éléments entier à l'aide d'un hachage parfait comme l'indice dans une table de saut - prenez essentiellement un ensemble de nombres non consécutifs et de les cartographier dans un espace consécutif plus rapidement que vous ne pouviez pas traverser un arbre de décision binaire. Que ce soit une optimisation, tout compilateur-écrivain peut être dérangé avec une autre affaire ...
@Steve: Je vais prendre votre parole pour cela, mais sur les architectures que j'ai connues assez d'assemblée pour mentionner même (surtout assez vieux ces jours-ci) une table de saut serait uniformément plus rapide. Même une table de saut à deux niveaux pour gérer des cibles clairsemées sur une grande gamme entières.
La seule exception que j'aurais pu être un hachage parfait pour un ensemble de drapeaux binaires. C'est à dire. Si toutes les "valeurs de cas" sont des pouvoirs de 2.
Ou supposons que les cas soient des multiples séquentiels de 147. Je m'attendrais fortement à ce que le hachage parfait «Divisez-vous de 147» (et le reste du reste est de 0), suivi d'une table de saut, d'être plus rapide que n'importe quel interrupteur générique. Mais je ne m'attendais pas non plus à un compilateur de venir avec ça. Il y a beaucoup de situations où un hachage parfait serait rapide, la difficulté trouve la fonction de hachage qui le fait. Et en C, des types énumérés ne font pas tout à fait ce que vous voulez, donc un hachage parfait sur les cas a besoin d'un chèque pour attraper d'autres valeurs.
pour la mise en œuvre de GCC Voir:
http: //old.nnglabble. Com / Optimisation-of-Switch-Stations-on-i386-to15366926.html # A15367662
Le lien est mort; Y a-t-il une autre copie quelque part?
Un hachage ne semble pas être un moyen efficace de mettre en œuvre un commutateur, car vous aurez des missions de cache supplémentaires en raison de la recherche.
On dirait que cela ferait que c un "go tueur" s'ils puissent optimiser une déclaration de commutation plutôt bien ...
Je serais très surpris si le hachage était plus rapide pendant 6 cas. Peut-être pour 25. Bien sûr, une table de hachage réduira probablement la variance dans l'heure d'accès, mais elle en ajoute une surcharge fixe.
Je suis sûr que vous comprenez que cela ne compte que si les branches de commutation ne font pas grand chose, et si le PC est réellement dans l'interrupteur une fraction importante de temps, comme 10% ou plus. Sinon, c'est fondamentalement du bruit quantique.