Quelle est la durée de la complexité d'une instruction switch?
J'aimerais savoir quelle est la pire cas d'exécution de la complexité d'une instruction switch est, en supposant que vous avez n cas.
J'ai toujours supposé que c'était O(n). Je ne sais pas si les compilateurs de faire quelque chose d'intelligent, si. Si la réponse est spécifique à l'implémentation, j'aimerais savoir pour les langues suivantes:
- Java
- C/C++
- C#
- PHP
- Javascript
- La réponse n'est pas seulement spécifique à une langue, pas même compilateur spécifique. Cela dépend de la code. Certaines instructions de commutation sont transformés en sauter tables par certains compilateurs.
- À l'autre extrême, les valeurs peuvent causer d'autres fonctions à appeler. En Ruby, par exemple, les valeurs sont vérifiées à l'aide de la
===de l'opérateur, qui peut faire n'importe quoi. Une utilisation commune de ce qui est d'expressions régulières, qui (dans certains cas) peut être très coûteux-et donc le coût de l'interrupteur est dominé par les valeurs elles-mêmes, et non pas par la façon dont il y en a beaucoup. - Est-il une situation où il pourrait être plus grande que O(n) (n cas dans la mode)?
- Gosh, je ne l'espère pas.
- peut-être comme une sorte de mal anti-optimisation de l'option de compilateur... ce serait un vilain poisson d'avril blague 😉
Vous devez vous connecter pour publier un commentaire.
C'est au pire en O(n). Parfois (et c'est le langage et le compilateur dépendante), elle se traduit par un saut de la table de recherche (pour "nice" commutateurs de ne pas avoir de trop grandes d'une affaire de gamme). Alors qui est en O(1).
Si le compilateur veut être funky, je peux penser à des façons que la complexité peut être mis en œuvre pour être quelque chose entre les deux (par exemple, effectuer une recherche binaire sur le cas, pour logn). Mais dans la pratique, vous allez obtenir eiher linéaire dans le temps ou à temps constant.
Le big-O de la complexité d'une instruction switch n'est pas vraiment le point important. Big-O notation se réfère à la performance en tant que n augmente vers l'infini. Si vous avez une instruction switch assez grand pour que l'asymptotique de la performance est un problème, alors il est trop grand et doit être refait.
En dehors de la lisibilité question, en Java et en C# je pense que vous serez bientôt atteindre certaines limites internes pour la taille maximale d'une seule méthode.
La petite taille des instructions de commutation que l'on appelle souvent, il serait sans doute plus instructif de mesurer la performance de l'instruction switch contre d'autres approches que vous pouvez utiliser à la place. Cette mesure pourrait être fait à plusieurs reprises d'effectuer l'opération dans une boucle.
Pour les plus grands les instructions switch je vous suggère de refactoring d'utiliser un dictionnaire ou d'une structure de données similaires d'environ O(1) performance a même n devient très grand et qu'il ne rencontrerez pas de problèmes avec le peu de méthode taille.
Compilateurs C++ peut basculer déclarations dans un saut de la table (c'est à dire construire un tableau de sauter des décalages, puis prendre de la valeur et de l'utiliser comme un index dans la table). Ce est O(1).
Le compilateur C# utilise une approche similaire, sauf qu'il peut assembler une table de hachage.
C avec le compilateur gcc a O(1) pour une gamme (saut de table) ou au pire en O(log N) pour les gamme (binaire de recherche).
Le pire des cas O(n), mais au moins pour les langages comme le C/C++, Java et C#, où les cas sont des constantes de compilation, un saut de table peuvent souvent être utilisés (et assez souvent est utilisé) pour obtenir de la complexité à O(1).
Je ne sais pas si le plus dynamique des langages comme PHP ou Javascript, essayez de sauter les tables ou pas.
switch(true) { case expr: doSomething(); }est valide, même si expr est pas constante. C'est, si je me souviens bien. Donc sauter tables de serait peu probable pour quelque chose comme ça.