Est-ce que big-O est vraiment pertinent quand on travaille dans l'industrie?

Lors de chaque entretien dans lequel j'ai participé, on m'a interrogé sur l'analyse mathématique de la complexité, y compris la notation big-O.

Quelle est la pertinence de l'analyse big-O pour le développement de l'industrie? À quelle fréquence l'utilisez-vous réellement et dans quelle mesure est-il nécessaire d'avoir un état d'esprit aiguisé face au problème?

Ma question est la suivante: quelle est la pertinence de ce test pour le développement de l'industrie?

Une solide compréhension de la théorie de la complexité informatique (par exemple, la notation Big O) est essentielle pour concevoir des algorithmes, des applications et des systèmes évolutifs. Étant donné que l’évolutivité est très pertinente pour l’informatique dans l’industrie, la grande notation O l’est aussi.

À quelle fréquence l'utilisez-vous réellement et dans quelle mesure est-il nécessaire d'avoir un état d'esprit aiguisé face au problème?

Cela dépend de ce que vous voulez dire par "utilisez-le vraiment". D'une part, je ne fais jamais de preuves formelles de la complexité informatique du logiciel que j'écris. D'un autre côté, la plupart des jours, je dois traiter avec des applications pour lesquelles l'évolutivité est un problème potentiel et les décisions de conception incluent la sélection (par exemple) des types de collection appropriés en fonction de leurs caractéristiques de complexité.

(Je ne sais pas s'il est possible de mettre en œuvre de manière cohérente des systèmes évolutifs sans une solide compréhension de la théorie de la complexité. J'aurais tendance à penser que ce n'est pas le cas.)

La raison en est que cela indique une évolutivité .

Un processus qui est O (n ^ 2) sera moins performant qu'un processus qui est O (n log n), mais meilleur qu'un dans O (n ^ 3) ou même O (n!).

Si vous ne connaissez pas les différences et si elles s’appliquent, vous serez moins bien placé pour choisir les bonnes implémentations de fonctionnalités et pour extrapoler les performances des tests en performances de production.

EDIT: Une comparaison de 48n avec n ^ 3 de http://www.codinghorror.com/blog/2007/09/everything-is-fast-for-small-n.html (qui provient de Programming Pearls)

Cela dépend de ce que vous faites.

Pour les développeurs Web (tels que moi), cela compte généralement beaucoup. Vous souhaitez que les applications Web évoluent. Si votre application présente un goulot d'étranglement qui évolue avec O (n ^ 2) et que vous pensez que cela convient, car votre serveur peut gérer 1 000 utilisateurs simultanés, il semble que vous n'en ayez pas besoin. Le fait est que, pour en traiter deux fois plus (ce qui est raisonnablement susceptible de se produire la nuit), vous aurez besoin de 4 fois plus de puissance de calcul. Idéalement, vous souhaitez que les applications Web évoluent en O (n), car le matériel est bon marché avec un ratio utilisateur / serveur constant et raisonnable.

Généralement, dans les applications, où vous avez 100 000 objets, le grand O viendra vous manger. Vous êtes énormément vulnérable aux pics. Par exemple, je travaille actuellement sur un jeu en 3D, une application qui gère des charges de données. Outre le rendu, vous avez la vérification des collisions, la navigation, etc. Vous ne pouvez pas vous permettre d'aller de la manière évidente. Vous avez besoin d'algorithmes efficaces, de beaucoup de cache pour que les moins efficaces amortissent. Etc.

Bien sûr, si vous faites quelque chose comme créer une application mobile en combinant une interface graphique dans un concepteur d’interface, connectez-le à certains services Web et le reste, vous n’aurez jamais de problèmes de complexité. Parce que les services Web que vous appelez en prennent déjà soin.

Je n'ai jamais appliqué formellement la règle dans ma vie professionnelle.

Cependant, vous devez connaître ce concept et l'appliquer de manière intuitive à chaque fois que vous concevez un algorithme.

La règle est la suivante:

Vous devez être suffisamment familiarisé avec la notation O pour pouvoir déterminer, pour une tâche donnée, s'il est nécessaire de la calculer formellement, ou s'il suffit de l'évaluer de manière intuitive, ou si vous pouvez simplement la sauter complètement. Juste comme beaucoup d'autres concepts mathématiques de base.

Eh bien, peut-être une petite histoire vous explique pourquoi elle est définitivement nécessaire:

Dans un projet auquel j'ai travaillé, il y avait un programme chargé d'imprimer tout type de documents (étiquettes, listes de choix, etc.). Ce programme était composé de deux parties, l'une lisant toutes les données nécessaires de la base de données et les écrivant dans un fichier. Fichier de style .ini, et une autre partie qui lit ces fichiers et les complète dans les modèles. Cela fonctionnait assez bien pour les étiquettes et les petites listes (avec seulement quelques champs), mais cela a duré près de 10 minutes lorsqu'il a fallu imprimer une "grande" liste d'environ 20 pages. Parce que l'accès à ces fichiers ini a entraîné O (n²) temps d'accès, n étant le nombre de champs à imprimer.

Si les programmeurs originaux de ce programme avaient compris la notation O, ils ne l'auraient jamais fait de cette façon. Remplacer cette stupidité par une table de hachage a rendu soooooooo beaucoup plus rapide.

La performance Big-O est importante, mais elle a été en grande partie internalisée.

Les performances Big-O en matière de tri et de recherche importent peu, car les utilisateurs utilisent généralement ceux fournis par le système. Certaines structures de données sont plus efficaces pour différentes choses, mais celles-ci peuvent généralement être sélectionnées sur des principes généraux (et sont généralement construites dans des langages modernes). Il existe un certain sens des algorithmes qui évoluent ou non.

Il en résulte que les problèmes formels sont rarement abordés dans la pratique, mais que la pratique repose sur les mêmes principes.

À mon humble avis, de nombreux programmes d’informatique laissent beaucoup d’élèves errer dans les mauvaises herbes. Ces programmes ne communiquent jamais vraiment la grande image de ce qu'est la science du calcul. Les étudiants entrent dans l’industrie, s’efforçant d’appliquer les concepts qu’ils ont appris, sans vraiment comprendre comment ils se rapportent au monde réel.

Je dirais que le cœur de la science du calcul est la capacité de raisonner à propos du calcul. Et vous apprenez diverses méthodes et techniques pour le faire, et les appliquez à des problèmes abstraits, qui sont des primitives prototypiques trouvées dans de nombreux problèmes du monde réel. L'astuce consiste à repérer ces primitives prototypiques dans le monde réel, puis à raisonner à propos de choses telles que la correction, la complexité, le temps, etc. Un aperçu du comportement des parties vous donne souvent un aperçu de la façon dont l'ensemble se comporte. Et les mêmes méthodes et techniques générales peuvent également être appliquées à l'ensemble, mais pas avec la même rigueur que celle offerte à des parties plus petites, bien abstraites et bien définies. Mais au final, la science du calcul vous dote de la capacité de rendre raisonnable des décisions sur la manière d’organiser votre calcul, avec un aperçu réel de la façon dont il se comportera dans diverses conditions.

Memo to self !:

Moi et beaucoup d’autres nous posons cette question régulièrement.

Je pense que la vraie raison pour laquelle nous posons cette question est que nous sommes devenus paresseux.

Cette connaissance ne sera jamais datée ni obsolète. Vous ne pouvez pas l’appliquer directement au jour le jour, mais vous l’utiliserez inconsciemment et cela aura un effet positif sur vos décisions de conception. Un jour, cela pourrait vous épargner, à vous et à d’autres, des heures et des jours de codage.

Au fur et à mesure que de plus en plus de problèmes sont encapsulés par des bibliothèques et des outils tiers et sont disponibles pour un nombre croissant de développeurs, vous devez connaître ces connaissances pour vous distinguer des autres et vous aider à résoudre de nouveaux problèmes.

Pas vraiment. En gros, la seule fois où j'y pense, c'est lors de l'accès à la base de données. En général, je regarde le code et dis: "Cela fait n + 1 requêtes, vous devriez le changer pour ne faire que 1 ou 2"

Parce que toutes mes données sont lues dans une base de données et présentées à l'utilisateur, j'essaie de minimiser la quantité de données sur laquelle je travaille au point que la différence entre un algorithme linéaire et un algorithme O (n ^ 2) est jolie. négligeable.

S'il y a un problème, nous allons profiler et résoudre le problème plus tard.

Trois questions que vous avez posées et je pense que des réponses abrégées pourraient aider les arguments plus longs avancés jusqu'à présent.

Quelle est la pertinence de ce test pour le développement de l'industrie?

Cela dépend de l'industrie.

Partout où la vitesse de code ou l'espace de code est un problème, cela est tout à fait pertinent pour l'industrie concernée. Vous avez souvent besoin de savoir combien de temps une routine prendra ou combien de mémoire (on / offline) sera nécessaire.

À quelle fréquence l'utilisez-vous réellement?

Cela dépend de l'industrie.

Si les performances et la mise à l'échelle ne concernent que très peu le travail à accomplir, cela est rarement le cas, même en cas de grave manque de performances. Si vous êtes ingénieur pour un système critique très utilisé, probablement chaque jour.

Dans quelle mesure est-il nécessaire d'avoir un état d'esprit aiguisé face au problème?

Complètement nécessaire.

Vous devrez peut-être l'utiliser tous les jours ou seulement dans des circonstances extrêmes. mais parfois il sera nécessaire. De préférence lors de la conception, avant l'arrivée d'un problème, plutôt que de profiler désespérément un système d'étouffement.

Je dirais que c'est très fréquent. Nous ne prouvons généralement pas que quelque chose a un big-O particulier, mais nous avons assimilé l'idée, mémorisé / familiarisé avec les garanties big-O de structures de données et d'algorithmes particuliers, et nous choisissons les plus rapides pour un usage particulier. Il est utile d’avoir une bibliothèque complète avec toutes les options, comme la bibliothèque de collections Java ou la STL C ++. Vous utilisez implicitement et naturellement big-O tous les jours lorsque vous choisissez d'utiliser une java.util.HashMap( O(1)recherche) au lieu d'une java.util.TreeMap( O(lg n)recherche) et que vous choisissez certainement de ne pas exécuter de recherche linéaire dans une java.util.LinkedList( O(n)recherche) pour quelque chose pour lequel vous n'avez pas besoin d'un accès trié.

Lorsque quelqu'un choisit une implémentation sous-optimale et que quelqu'un qui sait mieux se présente et voit son code, cela fait partie de notre vocabulaire pour le corriger "votre implémentation prend du temps, mais nous pouvons le réduire à n-log-n fois de cette façon au lieu de cela "aussi naturellement et automatiquement que nous utiliserions la langue anglaise pour commander une pizza.

Oui

Vous n’avez peut-être pas à faire d’analyses formelles, mais au moins une bonne compréhension de l’ordre de complexité des algorithmes - et de la comparaison de deux algorithmes autour de cet algorithme - est essentielle si vous souhaitez effectuer un travail non trivial et le rendre performant.

J'ai travaillé sur deux systèmes différents qui semblaient bien fonctionner au tout début du développement, mais j'ai mis le matériel à genoux lors des tests de production, car quelqu'un utilisait un algorithme O (n ^ 2). Et dans les deux cas, le correctif était un changement trivial à un algorithme O (n).

Il est probablement utilisé dans les endroits où ils développent des API pour la consommation. La STL C ++ est l’une des rares API à soumettre ses algorithmes à des restrictions de complexité. Mais pour les programmeurs / programmeurs principaux / concepteurs / architectes qui travaillent tous les jours, cela ne les traverse pas beaucoup.

Je n'ai pas trouvé cela aussi important que de communiquer des idées et je travaille dans des domaines critiques pour la performance (raytracing, traitement d'images et maillages, systèmes de particules, moteurs physiques, etc.) et j'ai dû concevoir de nombreux algorithmes propriétaires et structures de données. en travaillant dans la R & D. Dans ces domaines, une poignée de structures de données et d'algorithmes très efficaces peut donner lieu à de tout nouveaux produits de pointe, tandis que les algorithmes d'hier rendent les produits existants obsolètes, ce qui permet de toujours agir de manière plus efficace. Cependant, je n'ai jamais publié aucun article sur les algorithmes que j'ai conçus. Ils étaient tous propriétaires. Si c'était le cas, j'aurais besoin de l'aide d'un mathématicien pour formuler des preuves, etc.

Pourtant, à mon avis, la quantité de travail de calcul par itération présente souvent un intérêt plus immédiat que l’évolutivité de l’algorithme, à moins que l’algorithme ne soit vraiment mal adapté. Si quelqu'un propose une technique de pointe pour le lancer de rayons, les techniques de calcul telles que leur représentation et leur accès aux données m'intéressent plus que la complexité algorithmique, car une évolutivité raisonnable est déjà une donnée dans ce scénario concurrentiel et innovant. Vous ne pouvez pas être concurrentiel en proposant des algorithmes non évolutifs.

Bien sûr, si vous comparez la complexité quadratique au linéarithmique, c'est une énorme différence. Mais la plupart des gens de mon domaine sont suffisamment compétents pour éviter d’appliquer un algorithme de complexité quadratique sur une entrée épique. L’évolutivité est donc souvent profondément impliquée, et les questions les plus significatives et les plus intéressantes deviennent: "Avez-vous utilisé GPGPU? SIMD? Est-il exécuté en parallèle? Comment représentez-vous les données? Avez-vous réorganisé les paramètres d’accès au cache? Comment Peut-il gérer ce cas de manière robuste? Reportez-vous certains traitements ou faites-vous tout en même temps? "

Même un algorithme linéarithmique peut surpasser un algorithme à temps linéaire si le premier accède à la mémoire selon un modèle plus optimal, par exemple, ou s’il est mieux adapté au multithreading et / ou au SIMD. Parfois même un algorithme linéaire peut surpasser un algorithme logarithmique pour ces raisons, et naturellement, les algorithmes à temps linéaire surpassent les algorithmes logarithmiques pour les entrées minuscules.

Ce qui compte davantage pour moi, c’est donc ce que certaines personnes appellent des "micro-optimisations", telles que les représentations de données (agencements de mémoire, modèles d’accès avec découpage en champs chaud / froid, etc.), le multithreading, le SIMD et, occasionnellement, le GPGPU. Dans un domaine où tout le monde est déjà suffisamment compétent pour utiliser des algorithmes de pointe décents pour tous avec de nouveaux articles publiés tout le temps, votre avantage concurrentiel pour vaincre les assistants algorithmiques ne provient pas d'une amélioration de la complexité algorithmique, mais d'une approche plus directe. efficacité de calcul.

Mon domaine est dominé par de brillants mathématiciens, mais pas toujours par des connaisseurs du coût en calcul de ce qu’ils font ou de nombreuses astuces de niveau inférieur pour accélérer le code. C'est généralement mon avantage sur eux en concevant des algorithmes et des structures de données plus rapides et plus stricts, bien que le mien soit beaucoup moins sophistiqué. Je joue avec ce que le matériel aime, en bits et en octets, et chaque itération de travail est beaucoup moins chère, même si je fais un peu plus d'itérations de travail que l'algorithme très sophistiqué - le travail dans mon cas est considérablement moins cher. Le code que j'écris a aussi tendance à être beaucoup plus simple. Si les gens pensent que les versions micro-optimisées d'algorithmes simples et de structures de données sont difficiles à comprendre et à maintenir,

À titre d’exemple de base, j’ai mis au point une structure de grille simple qui surperformait un arbre KD dans notre entreprise en matière de détection de collision et d’élimination de points redondants. Ma stupide grille brute était tellement moins sophistiquée sur le plan algorithmique et je suis bien plus bête mathématiquement et algorithmiquement que le gars qui a implémenté KD-tree avec sa nouvelle façon de trouver le point médian, mais je viens d’ajuster l’utilisation de la mémoire et les modèles d’accès, et c'était suffisant pour surperformer quelque chose de beaucoup plus sophistiqué.

Un autre avantage qui me permet de survivre dans un domaine dominé par des personnes beaucoup plus intelligentes que moi est simplement de comprendre le fonctionnement de l'utilisateur, car j'utilise le logiciel que je développe de la même manière. Cela me donne des idées d’algorithmes qui s’alignent vraiment très immédiatement avec les intérêts des utilisateurs. À titre d’exemple fondamental, la plupart des gens essaient d’accélérer des processus tels que la détection de collision en utilisant l’indexation spatiale. Il y a près de vingt ans, j’ai fait une simple observation de la carrière pour les modèles organiques: par exemple, si un personnage pose ses mains sur son visage, une structure d’indexation spatiale voudra avoir à scinder des nœuds et à effectuer des mises à jour coûteuses si le personnage puis enleva sa main de son visage. Si, à la place, vous partitionnez sur la base de données de connectivité plutôt que de positions de sommet, vous pouvez vous retrouver avec une structure hiérarchique stable qui se met à jour très rapidement et qui n'a jamais besoin de scinder ou de rééquilibrer l'arbre (il suffit de mettre à jour les cadres de sélection pour chaque image d'animation) ... Ce genre de chose - des algorithmes pour un enfant sans arrière-plan mathématique important pourraient venir s’ils comprenaient le concept de base, mais ceux qui ont échappé aux mathématiciens, car ils ne pensaient pas aux choses de manière aussi proche de la façon dont les utilisateurs travaillaient et pensaient trop aux propriétés de la géométrie et non à la façon dont la géométrie était couramment utilisé. Je m'entends assez bien en m'appuyant davantage sur les connaissances informatiques générales et les connaissances des utilisateurs finaux que sur la magie algorithmique. Donc de toute façon, je n'ai pas vraiment trouvé important de se concentrer sur la complexité algorithmique.

Oui, la complexité compte dans l'industrie. Si vous décidez de créer quelque chose où un chemin critique est redimensionné en tant que N-carré (doubler le nombre de quelque chose, le système est quatre fois plus chargé), vous obtiendrez votre goulot d'étranglement d'échelle beaucoup plus rapidement que si vous aviez quelque chose qui redimensionne à N.

Cependant, cela n'est généralement pas fait comme une preuve formelle et adéquate que quelque chose a une complexité donnée, alors avoir une bonne intuition quant à la complexité d'un modèle d'opérations est un bon début.

Je ne pense jamais à Big O dans une perspective mathématique, je ne pense jamais à Big O du tout, à moins que demandé. Je vois juste un algorithme dans ma tête, et je peux dire s'il est mauvais, car il effectue plusieurs boucles dans la mémoire pour chaque N, ou s'il divise et conquiert ou quelque chose du genre. Si nécessaire, je peux traduire cela en grosse notation O en quelques secondes, mais il est plus facile pour moi de savoir comment fonctionne l'algorithme / conteneur avec la mémoire que de penser à une perspective mathématique.

Les questions posées lors des entretiens permettent de savoir si vous pouvez expliquer les choses et penser de manière logique . L'intervieweur essaie également de savoir si vous pouvez utiliser ce que vous savez pour résoudre un problème connexe .

Tous ceux qui ont fait des études intéressantes en génie logiciel auront rencontré «Big O». Pour répondre à une bonne question sur «Big O», vous devez également avoir une connaissance des structures de données et des algorithmes standard.

Lorsque vous interviewez un membre du personnel, vous recherchez une personne pouvant apprendre rapidement le travail, mais pas une personne connaissant déjà un ensemble de compétences détaillées. Il peut donc être très difficile de choisir des questions pour lesquelles l'intervieweur et l'interviewé ont une compréhension commune. de.

Donc, les questions sur le «grand o» peuvent être très pertinentes pour le processus d’entretien.

Au moins une fois par an, au cours de ma longue carrière en tant que programmeur, je devais corriger le code qui était lent en raison du fait que quelqu'un ne comprenait pas les structures de données et les algorithmes corrects à utiliser, mais vous pouvez résoudre ces problèmes sans avoir une compréhension détaillée de Big O. Cependant, ceux qui comprennent Big O tentent d'éviter ces problèmes en premier lieu.