Big O est-il vraiment important?

Dans le pire des cas, Big O est enseigné dans le monde universitaire . Comparé à la complexité de l'espace, l'analyse de cas normale, la simplicité par rapport à la complexité, etc.

En particulier pour la programmation de jeux et l'industrie, qu'est-ce qui compte vraiment et pourquoi?

Des références seraient très utiles.

Comme pour toutes les autres questions concernant «quel est le seul vrai chemin», ce sont tous des outils dans votre boîte à outils et il y a des cas où big-O l'emporte sur tout, et des endroits où cela n'a pas d'importance (tm).

Vous n'écririez "jamais" un solveur de physique sans vous soucier du big-O. Vous ne mettriez pas en œuvre un algorithme de tri (pour tout sauf le plus petit des ensembles de données) sans vous en préoccuper. Si vous écrivez un jeu en réseau, vous allez vous préoccuper de la façon dont les performances et le trafic réseau évoluent par utilisateur.

Vous pourriez ne pas être si préoccupé par le big-O quand, eh bien, je ne peux pas vraiment penser à un moment mais je suis sûr qu'il y en a. :) Heureusement, la plupart des choses que nous faisons dans les jeux évoluent de manière linéaire; vous souhaitez lire un fichier sur le disque? Cela prendra un temps linéairement proportionnel à la taille du fichier (en actualisant le facteur constant de recherche et les ramifications possibles de la taille du secteur).

Cependant, que se passe-t-il si vous souhaitez rechercher une entité spécifique dans la liste des entités? C'est une recherche linéaire à chaque fois que vous le faites. Si vous devez trouver le joueur une fois pour chaque entité dans le monde, cette approche vous tuera pour tous, sauf le plus trivial des jeux, et même alors, il vaut probablement la peine "d'optimiser" cette recherche pour qu'elle soit à temps constant (par exemple, stocker hors de l'index ou un pointeur vers le lecteur quelque part), ce qui vous donne plus de temps pour faire d'autres choses qui sont réellement visibles par le joueur.

Je suppose que cela résume, cependant; chaque fois que le processeur fait quelque chose qui n'est pas directement représentable pour le joueur, c'est une perte de temps. Maximiser le temps pendant lequel le processeur calcule les données qui seront montrées au joueur maximise le WOW! vous donnez au joueur.

Ma règle d'or est qu'à moins que vous ne soyez O (effrayant), vos autres problèmes sont plus pertinents.

Mon autre règle d'or est que les données sont roi. À moins que vous ne profiliez votre code avec un ensemble de données réalistes, vous faites des suppositions.

Edit: Pour entrer dans un peu plus de détails, votre grand O n'est pas si important car (au moins d'après mon expérience) la plupart de vos ensembles de données sont relativement minuscules. Vous ne vous souciez probablement pas de votre limite supérieure de performances lorsque vous travaillez avec une structure de données avec moins de quelques centaines d'éléments. Et si vos listes contiennent plus de 100k éléments, vous devez vraiment prendre en compte tous les aspects de vos algorithmes. Cela, et d'après mon expérience, la mémoire est plus un facteur limitant que la vitesse du processeur. Un algorithme de compression de mémoire plus rapide peut ne pas être aussi efficace qu'un algorithme plus léger mais plus lent en fonction de vos cas d'utilisation.

Le Big O est important la plupart du temps, mais parfois un algorithme apparemment "pire" en théorie s'avère beaucoup plus rapide dans la pratique.

Découvrez un excellent exemple de Tony Albrecht: http://seven-degrees-of-freedom.blogspot.com/2010/07/question-of-sorts.html

Vous trouvez cela partout dans le développement de jeux où le nombre d'éléments dans l'opération est soit si grand qu'un algorithme très différent est plus rapide, soit si petit qu'un algorithme plus stupide est suffisant (ou tient si bien dans le cache qu'il annule l'efficacité) du meilleur algorithme).

Le problème avec Big O est qu'il s'agit d'une désignation générique de la complexité de la tâche et ne prend pas en compte la complexité du matériel cible moderne, ni n'offre un aperçu du temps de configuration.

Dans de nombreux cas, la meilleure solution optimale est en deux étapes. Dans la pratique, les développeurs de jeux ont tendance à tendre vers des algorithmes à faible O mais équilibrés par rapport au coût de développement ou de débogage. Une fois que vous avez une solution raisonnable, vous devez toujours regarder comment le matériel gère la tâche et comment permettre au matériel de faire plus en moins de temps.

Quand je code dans le moteur, je ne m'inquiète souvent que d'un fixe n: j'ai déjà une partition spatiale limitant le nombre d'objets recevantupdate() , physics()et render()à peu près ceux sur l' écran et les régions avoisinantes. La taille maximale des lots est généralement assez bien définie par jeu, bien qu'elle soit invariablement un peu plus grande que ce que vous aviez prévu.

Dans ce cas, je ne suis pas autant préoccupé par le big-O que par le multiplicateur à facteur constant et les termes d'ordre inférieur. Pour une fonction avec un runtime comme a*n^2 + b*n + c(qui est O(n^2)), je suis souvent beaucoup plus concerné par la réduction aet éventuellement l'élimination c. Un coût d'installation ou de démontagec peut devenir proportionnellement élevé par rapport à un petit n.

Cependant, cela ne veut pas dire que big-O (ou plus particulièrement big-theta ) est un excellent indicateur d'odeur de code. Voyez O(n^4)quelque part, ou pire encore une O(k^n)heure géométrique, et il est temps de vous assurer que vous envisagez d'autres options.

Je suis généralement beaucoup plus préoccupé par l'optimalité du big-O et en sautant à travers des cerceaux pour trouver des algorithmes avec un big-O inférieur lorsque je traite des outils de création de données. Bien que le nombre d'objets dans un niveau / une zone de diffusion donné soit généralement bien défini, le nombre total d'objets / actifs artistiques / fichiers de configuration / etc. sur un jeu entier peut ne pas l'être. C'est aussi un nombre beaucoup plus important. Même en exécutant une marque de données parallèle, nous attendons toujours environ une minute (je sais, pleurnicher - la création de données pour les consoles peut prendre des heures - nous sommes principalement de petits jeux portables) pour passer par unjam data-clean && jam data cycle.

Pour donner un exemple spécifique: cela est vraiment devenu incontrôlable avec un algorithme de streaming de tuiles en arrière-plan qui diffuse 8x8 256 couleurs. Il est utile de partager des tampons de streaming entre des "couches" d'arrière-plan, et nous pourrions avoir jusqu'à 6 d'entre elles à un niveau donné partageant le même tampon. Le problème est que l'estimation de la taille du tampon nécessaire est basée sur les positions possibles des 6 couches - et s'il s'agit d'un nombre premier largeur / hauteur / taux de défilement, vous commencez rapidement à lancer une recherche exhaustive - qui commence à approcherO(6^numTiles)- qui est dans la catégorie "plus longtemps que l'univers ne sera autour" dans de nombreux cas. Heureusement, la plupart des cas ne sont que 2 à 3 couches, mais même dans ce cas, nous dépassons la durée d'une demi-heure. Pour le moment, nous échantillonnons un très petit sous-ensemble de ces possibilités, augmentant la granularité jusqu'à ce qu'une durée définie se soit écoulée (ou nous avons terminé la tâche, ce qui peut arriver pour les petites configurations à double couche). Nous augmentons un peu cette estimation en nous basant sur des statistiques antérieures de la fréquence à laquelle nous nous sommes trompés, puis nous ajoutons un peu de rembourrage supplémentaire pour faire bonne mesure.

Un autre exemple amusant: sur un jeu PC il y a quelque temps, l'ingénieur principal a expérimenté pendant un certain temps avec des listes de sauts . La surcharge de mémoire finit par provoquer plus d'effets de cache, ce qui ajoute une sorte de multiplicateur non constant à toute l'affaire - donc ce ne sont vraiment pas un bon choix pour les petits n. Mais pour les listes triées plus importantes où les recherches sont fréquentes, elles offrent un avantage.

(Je trouve souvent que l'algorithme naïf est un big-O plus élevé, plus rapide sur les petits ensembles de données et plus facile à comprendre; les plus intéressants / complexes (par exemple, trie patricia) sont plus difficiles à comprendre et à maintenir pour les gens, mais des performances plus élevées sur les plus grands ensembles de données.)

Cela peut être pratique, mais cela peut aussi ne pas être pertinent. Prenons, par exemple, mon jeu le plus récent, qui est en quelque sorte un clone de Smash TV. Jeu descendant, les monstres affluent par les côtés, vous les tirez.

Il existe maintenant de nombreuses façons intelligentes de déterminer les collisions. Vous pouvez utiliser KDtrees pour partitionner l'espace afin de ne pas tester les balles contre des monstres qu'ils ne pourraient pas toucher. Et, bien sûr, j'aurais pu être intelligent, et j'aurais pu le faire.

Mais je me sentais paresseux alors j'ai comparé chaque balle contre chaque monstre. Même dans les situations les plus mouvementées, le code de collision utilisait bien moins de 10% du processeur du jeu à 60 images par seconde. Big-O: sans importance.

De même, j'ai eu un jeu de style 4x où vous avez construit des villes sur des îles, et parfois les villes ont été détruites. J'aurais pu être intelligent et essayer de soustraire le revenu de la ville détruite des variables de revenu. Mais je ne l'ai pas fait. J'ai simplement effacé le revenu et l'ai recalculé à partir de zéro à chaque fois que quelque chose changeait. Totalement hors de propos en termes de CPU.

Big-O est tout aussi important dans les jeux que dans tout le reste: c'est-à-dire, absolument sans importance, jusqu'à ce qu'il devienne critique.

Allez écrire du code. Si c'est trop lent, profilez-le.

L'analyse Big-O est importante, mais ce n'est pas la première chose à penser dans le développement de jeux. Étant donné que la création de jeux impliquait beaucoup de code compliqué, je recommanderais toujours la simplicité du code comme premier critère d'un algorithme. Les algorithmes avec une comptabilité compliquée ne font que perdre votre temps.

Je pense qu'il est vraiment important que votre jeu tourne toujours à 60 ips pendant le développement. Lorsque vous descendez en dessous, la première chose que vous faites est d'exécuter un profileur. Une fois que vous avez trouvé le goulot d'étranglement, vous l'attaquez. La plupart du temps, vous devez faire des choses non codantes, comme dire aux concepteurs de niveaux de mettre moins de choses dans une zone (et de leur donner des outils pour cela).

Parfois, vous identifiez en fait un code qui doit être accéléré. Je trouve que c'est une ingénierie amusante! J'aimerais avoir plus d'occasions de le faire. Et bien sûr, vous voulez répéter le changement d'une chose à la fois et mesurer les performances. Les problèmes typiques que je trouve sont:

1. Assurez-vous que vous n'appelez pas new ou malloc chaque image (c'est toujours le problème n ° 1)
2. Réduisez le travail: moins de lancers de rayons, moins de gars, etc.
3. Problèmes de type d'algorithme Big-O
4. Cohérence du cache: placez les éléments dans des tableaux plutôt que dans de la mémoire dispersée
5. N'utilisez pas STL en mode débogage. (et vous voulez toujours que le mode de débogage fonctionne)

La notation Big-O est par définition une complexité asymptotique - c'est-à-dire qu'elle montre comment les échelles de temps lorsque N (ou toutes les variables que vous avez) deviennent "très" grandes. Pour réitérer le commentaire de Tetrad (que j'ai augmenté) "les données sont roi". Si N est "très grand" dans votre situation spécifique, cela compte, si N est "très petit", cela n'a pas d'importance. L'expérience et la pratique vous donneront une idée de la façon de quantifier «très grand» et «très petit».

Évidemment, profilez toujours en premier et optimisez en dernier (à moins que vous ne fassiez une étude de faisabilité des fonctionnalités).

L'importance de Big-O dans votre logiciel est O (N ² ). À mesure que N grandit, l'importance d'avoir le bon algorithme augmente encore. :)

Big-O n'est qu'un guide - quelque chose qui vous indique les performances approximatives que vous pouvez attendre d'un algorithme - et comment vous devez vous attendre à ce que les performances évoluent lorsque vous augmentez la taille de l'ensemble de données . Vous devez vous rappeler deux choses principales concernant Big-O:

1) Si vous avez deux algorithmes qui font principalement la même chose mais que l'un a un meilleur O, vous devriez probablement opter pour celui-ci (évidemment)

2) Big O s'intéresse à l'analyse asymptotique . Big-O n'entre vraiment en jeu que lorsque n est grand . Par exemple, un algorithme O (n) peut avoir des performances très similaires à un algorithme O (n ^ 2) .. pour les petits n . Si vous parlez d'un algorithme qui nécessite n ^ 2 opérations par sommet, mais n = 2 ou n = 3, alors il n'y a pas beaucoup de différence entre un algorithme O (n ^ 2) (en prenant 4 et 9 ops resp) et un O (n) un (2 et 3 ops resp.). Cependant, si n = 9, alors vous parlez soudainement de 81 opérations pour l'algorithme O (n ^ 2) et seulement 9 pour celui O (n) - une plus grande différence - et si n = 100, alors vous êtes parler de 100 ops vs 10000 - une différence beaucoup plus grande.

Vous devez donc toujours considérer Big-O sous cet angle: il est destiné à comparer des algorithmes qui font la même chose en fonction des performances les plus défavorables lorsque n devient grand . Les différences entre les algorithmes peuvent être tout sauf négligeables lorsque n est très petit.

Je n'ai pas de références mais Big O est au moins pratique à prendre en compte lors de l'analyse d'un problème et d'une discussion. D'un autre côté, bien sûr, si la version O (log n) a un O beaucoup plus impliqué que la version O (n), c'est une comparaison théorique. Et comme pour tout, il y a toujours un compromis. La complexité de l'espace pourrait être un problème, bien que cela puisse également être exprimé en O en général. Analyse de cas normale ... moins, car vous ne voulez pas non plus que les valeurs aberrantes augmentent. La simplicité sur la complexité, à mon avis, est relativement inutile dans le développement de jeux car la vitesse est presque toujours un problème, donc à moins que la simplicité n'entraîne des accélérations (mais cela signifie que votre cas complexe était faux pour les mauvaises raisons), la simplicité devra aller par la fenêtre en faveur de la vitesse. Mais Big O est certainement utile,

Lorsque vous prototyper une fonction de jeu ou un aspect d'un jeu, vous ne devriez pas vous soucier de l' optimiser du tout .

Au cours du prototypage et de l'apprentissage des particularités de cette fonctionnalité, les optimisations nécessaires deviendront évidentes et entreront en ligne de compte dans la conception finale comme 2nd nature ... la plupart du temps.

Ne le transpire pas.

Ce ne devrait pas être le tout et le final. Mais cela aide à trier les problèmes évidents qui pourraient entraîner des problèmes de performances; pourquoi utiliser quelque chose en temps O (n ^ 2), alors que vous pouvez faire la même chose en temps O (log n)?

Je pense que cela s'applique aux jeux plus que la plupart des autres industries, car le marché est celui qui remarquerait le plus les problèmes de vitesse. Quelqu'un utilisant un traitement de texte ne se souciera pas s'il y a un délai d'une demi-seconde pour faire l'action X, mais les joueurs vont probablement `` omg omg game Y est si lent qu'il faut des siècles pour faire l'action Z ''.

Dans le développement de jeux (et la plupart des autres), nous nous plaignons d'une opération supplémentaire effectuée par boucle:

for (int i = 0; i < array.length; i ++) { /* ... */ }

contre.

for (int i = 0, l = array.length; i < l; i ++) { /* ... */ }

La plupart des jeux modernes ont de la physique, et vous trouverez la simulation à n corps problème de . Dans un algorithme naïf, c'est O (n ^ 2), mais il y a une optimisation qui le rend O (n log n) (mais sacrifie une certaine précision).

Vous pourriez dire que vous ne programmez pas les interactions de gravité et de particules, mais qu'en est-il du comportement en équipe d'une armée (de zombies) où ils se déplacent en fonction d'autres emplacements (en un mot plus spécifique: essaimage)?

Dans un algorithme de détection de collision conventionnel, la complexité temporelle est O (n ^ 2), comme le n-corps. Cependant, il existe un meilleur moyen: séparer le monde de nombreuses petites pièces afin que seuls les objets à l'intérieur de la même partie soient détectés par collision. Voir http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php .

Si votre jeu est scriptable, NE PAS obliger le scripteur à écrire des algorithmes de calcul de nombres O (n ^ 2) (et plus) dans le script, comme la recherche dans le sac de l'utilisateur. Créez plutôt une fonction intégrée dans le code.

Dans le monde réel, seules les performances brutes comptent. Maintenant, le Big-O d'un algorithme peut servir de première indication de ce qu'il faut utiliser, mais selon le matériel, l'implémentation peut être terriblement inefficace. Par exemple, une recherche linéaire peut souvent être plus rapide qu'une recherche binaire car vous obtenez un accès linéaire à la mémoire et aucune branche.

De plus, en raison de l'orientation actuelle des plates-formes et architectures multi-thread, Big-O perd beaucoup d'importance car il ne prend en compte que l'évolutivité verticale de la mémoire ou des touches de données par opération au lieu de prendre également en compte la façon dont l'algorithme échelles avec un plus grand nombre de fils.