Est-ce un problème d'être un programmeur sans connaissance de la complexité informatique?

30

On m'a assigné un exercice dans mon université. Je l'ai ramené chez moi et j'ai essayé de programmer un algorithme pour le résoudre, c'était quelque chose lié aux graphiques, trouver des composants connectés, je suppose.

Ensuite, j'ai fait la chose la plus triviale qui me soit venue à l'esprit et je l'ai ensuite montrée à mon professeur. Après une brève observation, il a perçu que la complexité d'exécution de ma solution était inviable et montrait quelque chose de plus efficace. Et il y a une tradition de programmeurs qui n'ont aucune idée de ce qu'est la complexité de calcul (j'en faisais partie), est-ce donc un problème si un programmeur n'a aucune idée de ce qu'est la complexité de calcul?

Billy Rubina
la source
3
Avis du modérateur : veuillez ne pas utiliser de commentaires pour une discussion approfondie ou pour publier des réponses concises. Vous pouvez utiliser la salle de discussion pour discuter de cette question; les commentaires précédents y ont été déplacés.
Gilles 'SO- arrête d'être méchant'
4
Votre titre dit programmeur, mais votre question dit étudiant. Généralement, «programmeur» implique «programmeur professionnel» - demandez-vous donc si c'est un problème d'être un programmeur professionnel sans connaissance de la complexité informatique? Ou s'il est acceptable qu'un étudiant en programmation n'ait pas cette connaissance? Les deux questions sont différentes, même s'il s'avère qu'elles ont la même réponse.
corsiKa

Réponses:

42

Oui, je dirais que connaître quelque chose sur la complexité de calcul est un must pour tout programmeur sérieux. Tant que vous ne traitez pas d'énormes ensembles de données, tout ira bien sans connaître la complexité, mais si vous voulez écrire un programme qui s'attaque à de graves problèmes, vous en avez besoin.

Dans votre cas spécifique, votre exemple de recherche de composants connectés peut avoir fonctionné pour des graphiques de jusqu'à nœuds. Cependant, si vous avez essayé un graphique avec 100000 nœuds, l'algorithme de votre professeur aurait probablement réussi cela en 1 seconde, tandis que votre algorithme aurait (selon la gravité de la complexité) pris 1 heure, 1 jour, ou peut-être même 1 éternité.100100.000

Une erreur quelque peu courante que les étudiants font dans notre cours d'algorithmes est d'itérer sur un tableau comme celui-ci:

while array not empty
    examine first element of array
    remove first element from array

Ce n'est peut-être pas le code le plus beau, mais dans un programme compliqué, quelque chose comme ça peut apparaître sans que le programmeur en soit conscient. Maintenant, quel est le problème avec ce programme?

Supposons que nous l'exécutons sur un ensemble de données de éléments. Par rapport au programme suivant, l'ancien programme fonctionnera 50 000 plus lentement.100.00050.000

while array not empty
    examine last element of array
    remove last element from array

J'espère que vous convenez qu'avoir les connaissances nécessaires pour faire fonctionner votre programme fois plus rapidement est probablement une chose importante pour un programmeur. Comprendre la différence entre les deux programmes nécessite des connaissances de base sur la théorie de la complexité et des connaissances sur les particularités du langage dans lequel vous programmez.50.000

O(1)O(n)n1

12n2nn=100.000

Ce n'est qu'un exemple de jouet, mais cela nécessite déjà une compréhension de base de la complexité pour faire la différence entre les deux programmes, et si vous essayez réellement de déboguer / optimiser un programme plus compliqué qui a cette erreur, il faut une compréhension encore plus grande pour trouver où est le bug. Parce qu'une erreur comme la suppression d'un élément d'un tableau de cette façon peut être très bien cachée par des abstractions dans le code.

Une bonne compréhension de la complexité permet également de comparer deux approches pour résoudre un problème. Supposons que vous ayez trouvé deux approches différentes pour résoudre le problème des composants connectés par vous-même: afin de décider entre eux, il serait très utile d'estimer (rapidement) leur complexité et de choisir la meilleure.

Tom van der Zanden
la source
10
"So long as you are not dealing with huge data sets you will be fine not knowing complexity"C'est souvent vrai, mais pas toujours. Par exemple, un O(n!)algorithme ne sera pas viable même pour des ensembles de données relativement petits. Si vous utilisez un O(n!)algorithme où vous auriez pu utiliser O(n^2)votre programme, l'exécution prendra 36 288 fois plus longtemps avec une taille de données de 10 . Sur une taille de données de 20, vous regardez 2,4 quintillions d'opérations.
reirab
1
Je pense que l'exemple de @ reirab devrait être inclus dans la réponse. C'est plus dramatique et prouve votre point de vue de manière plus décisive. Et j'ai personnellement été mordu par de tels algorithmes, avant d'apprendre la complexité de calcul.
Siyuan Ren
2
Je pense qu'il y a un plus grand problème en jeu. Si vous ne savez tout simplement pas que vous choisissez vous-même les tâches où cela n'est pas nécessaire. Vous pouvez donc dire presque toutes les questions dont j'ai besoin pour savoir que X se retrouve avec, cela pourrait être utile. Donc, peu importe si son critique est toujours bon à savoir ou il pourrait finir par vous mordre.
joojaa
"Comprendre la différence entre les deux programmes nécessite des connaissances de base sur la théorie de la complexité" - je pense que pour cet exemple particulier, ce n'est pas le cas. Vous pouvez le profiler, observer que tout le temps est consacré à "supprimer l'élément", savoir (sans comprendre la théorie de la complexité) que la suppression du dernier élément est plus rapide que la suppression du premier, effectuer le changement et donc accélérer le programme. L'avantage de la compréhension de la théorie de la complexité est qu'elle vous permet de quantifier de manière lâche de tels problèmes sans les profiler, afin que vous puissiez les optimiser "prématurément".
Steve Jessop
.. et en général je soupçonne que tous ou presque tous les exemples pratiques peuvent être résolus, un par un, sans référence à la théorie de la complexité. Dans ce cas, sachant que copier beaucoup de données est plus lent que ne pas le faire, ce n'est pas de la «théorie de la complexité». Mais bien sûr, il est toujours utile dans la programmation (et dans n'importe quelle profession) d'avoir un bon modèle mental de principes qui revient souvent, car vous pouvez analyser, discuter et résoudre ces problèmes de manière routinière par principe au lieu d'un à la fois par des moyens ad hoc.
Steve Jessop
26

Il s'agit d'une réfutation de la réponse de Tom van der Zanden , qui déclare que c'est un must.

La chose est, la plupart du temps, 50 000 fois plus lente n'est pas pertinente (sauf si vous travaillez chez Google bien sûr).

Si l'opération que vous effectuez prend une microseconde ou si votre N n'est jamais au-dessus d'un certain seuil (une grande partie du codage fait de nos jours), cela n'aura JAMAIS d'importance. Dans ces cas, penser à la complexité de calcul ne fera que vous faire perdre du temps (et probablement de l'argent).

La complexité informatique est un outil pour comprendre pourquoi quelque chose peut être lent ou mal évoluer, et comment l'améliorer, mais la plupart du temps, c'est une surpuissance totale.

Je suis programmeur professionnel depuis plus de cinq ans maintenant et je n'ai jamais trouvé la nécessité de penser à la complexité de calcul lors d'une boucle à l'intérieur d'une boucle O (M * N) car toujours l'opération est vraiment rapide ou M et N le sont petit.

Il existe des choses beaucoup plus importantes, généralement utilisées et plus difficiles à comprendre pour quiconque effectue des tâches de programmation (le filetage et le profilage sont de bons exemples dans le domaine des performances).

Bien sûr, il y a certaines choses que vous ne pourrez jamais faire sans comprendre la complexité du calcul (par exemple: trouver des anagrammes sur un dictionnaire), mais la plupart du temps vous n'en avez pas besoin.

claudio495h
la source
3
Pour développer votre propos, il y a des cas où trop d'accent sur la complexité de calcul peut vous induire en erreur. Par exemple, il peut y avoir des situations où un «meilleur» algorithme est en fait plus lent pour les petites entrées. Le profileur est la source ultime de vérité.
Kevin Krumwiede
2
@Kevin Krumwiede, je suis entièrement d'accord avec vous qu'optimiser un tri pour un ensemble de données trivial est exagéré. Mais cela montre aussi qu'il est toujours important d'avoir au moins une compréhension de la complexité. La compréhension est ce qui vous amènera à prendre la décision qu'un tri à bulles est approprié par opposition à un autre algorithme plus complexe.
Kent A.
4
Lorsque vous savez que l'ensemble de données est petit dans tous les cas, vous pouvez vous en tirer avec ce genre de chose. Cependant, vous devez faire très attention à la complexité excessive des choses appelées dans les boucles - il n'y a pas longtemps, j'ai réduit une minute d'exécution à une seconde de cette façon. J'ai également rencontré un problème O (n ^ 8) une fois (validation des données). Beaucoup de soins l'ont réduit à 12 heures.
Loren Pechtel
7
Je n'ai jamais trouvé le besoin de penser à la complexité de calcul lors d'une boucle à l'intérieur d'une boucle O (M * N) car toujours l'opération est vraiment rapide ou M et N sont si petits. - Ironiquement, l'argument que vous donnez montre que vous avez pensé à la complexité du calcul. Vous avez décidé que ce n'était pas un problème pertinent pour ce que vous faites et peut-être à juste titre, mais vous êtes toujours conscient de l'existence de ce problème, et si cela devait poser un problème, vous pourriez y réagir avant que de graves conséquences ne se produisent sur le niveau de l'utilisateur.
Wrzlprmft
4
L'optimisation prématurée est la racine de tout mal, mais la pessimisation prématurée est la racine d'au moins une bonne partie des utilisateurs agacés. Vous n'aurez peut-être pas besoin de résoudre une relation de récurrence, mais si vous êtes, à tout le moins, incapable de faire la différence entre O (1), O (N) et O (N ^ 2), surtout lorsque vous 'imbrication des boucles, quelqu'un va devoir nettoyer le gâchis plus tard. Source: les dégâts que j'ai dû nettoyer plus tard. Un facteur 50 000 est si important que vous feriez mieux de savoir si vous pouvez vous le permettre plus tard , lorsque vos intrants auront augmenté.
Jeroen Mostert
14

Je développe des logiciels depuis une trentaine d'années, travaillant à la fois en tant qu'entrepreneur et employé, et j'ai plutôt bien réussi. Ma première langue était BASIC, mais je me suis vite appris le langage machine pour obtenir une vitesse décente de ma boîte sous-alimentée. J'ai passé beaucoup de temps dans les profileurs au fil des ans et j'ai beaucoup appris sur la production de code optimisé rapide et efficace en mémoire.

Quoi qu'il en soit, je suis autodidacte. Je n'ai jamais rencontré la notation O jusqu'à ce que je commence à interviewer il y a quelques années. Cela ne revient jamais dans mon travail professionnel SAUF lors des entretiens. J'ai donc dû apprendre les bases juste pour gérer cette question lors des entretiens.

Je me sens comme le musicien de jazz qui ne sait pas lire les partitions. Je peux toujours jouer très bien. Je connais les tables de hachage (diable, j'ai inventé les tables de hachage avant d'apprendre qu'elles avaient déjà été inventées) et d'autres structures de données importantes, et je pourrais même connaître quelques astuces qu'ils n'enseignent pas à l'école. Mais je pense que la vérité est que si vous voulez réussir dans ce métier, vous devrez soit faire de l'indé ou apprendre les réponses aux questions qu'ils vous poseront lors des entretiens.

Soit dit en passant, j'ai récemment interviewé pour un rôle de développeur Web frontal. Ils m'ont posé une question où la réponse exigeait à la fois une connaissance de la complexité de calcul et des logarithmes. J'ai réussi à me souvenir de suffisamment de calculs d'il y a vingt ans pour y répondre plus ou moins correctement, mais c'était un peu choquant. Je n'ai jamais eu à utiliser de logarithmes dans aucun développement frontal.

Bonne chance à toi!

Scott Schafer
la source
2
Donc, votre réponse est "oui"?
Raphael
6
TL; DR: "oui". Cependant, d'après mon expérience, vous n'allez pas parler de complexité informatique dans la plupart des emplois après votre embauche. Oui, connaissez vos structures de données et leurs performances, mais sachez simplement qu'un algorithme est O (n) ou tout ce qui ne fait pas un bon programmeur. Il est préférable de se concentrer rapidement sur l'écriture d'un bon code, puis d'optimiser les points chauds plus tard. La lisibilité et la maintenabilité sont généralement plus importantes pour la plupart des codes que les performances.
Scott Schafer
3
Je pense qu'il peut arriver que la complexité surgisse dans un environnement d'entreprise, mais la première vraie préoccupation pour les entreprises est l' expédition : si cela fonctionne, c'est assez bien, jusqu'à ce qu'il y ait un budget disponible pour améliorer l'application, ou qu'un client revienne pour se plaindre des mauvaises les performances. Dans les situations B2B pour les projets adhoc, c'est probablement assez rare. En b2c, ou sur des marchés très concurrentiels (produits standard), il se présenterait probablement plus souvent, avec pour effet direct d'élever la barre d'entrée pour les nouveaux embauchés.
didierc
4
@didierc "Assez bien" est aussi ce qui casse tout le temps.
Raphael
1
@didierc 1) Eh bien, les personnes ayant une solide expérience dans CS ne (je l' espère) ont une bonne intuition pour ce qui est correct et ce qui est pas, alors que problème ad hoc solveurs peuvent commettre des erreurs de « simples ». S'assurer que l'exécution après des compilations multipliées est exactement ce qui était spécifié est très non trivial, et afaik un problème non résolu. 2) Non .
Raphael
9

La question est assez subjective, donc je pense que la réponse est que cela dépend .

Peu importe si vous travaillez avec de petites quantités de données. Dans ces cas, il est généralement bon d'utiliser par exemple la bibliothèque standard de votre langue.

Cependant, lorsque vous traitez de grandes quantités de données, ou pour une autre raison, vous insistez pour que votre programme soit rapide, vous devez comprendre la complexité de calcul. Si vous ne le faites pas, comment savez-vous comment résoudre un problème ou à quelle vitesse il est même possible de le résoudre? Mais comprendre la théorie ne suffit pas pour être un très bon programmeur. Pour produire du code extrêmement rapide, je crois, vous devez également comprendre comment fonctionne par exemple votre machine (caches, disposition de la mémoire, jeu d'instructions) et ce que fait votre compilateur (les compilateurs font de leur mieux, mais ne sont pas parfaits).

En bref, je pense que comprendre la complexité fait de vous un meilleur programmeur.

Juho
la source
1
Je pense que vous avez généralement une bonne idée, mais "subjectif" ne décrit pas ce problème de manière adéquate; «circonstanciel» serait un meilleur mot. De plus, on peut cependant écrire des programmes très lents qui ne fonctionnent pas sur beaucoup de données. J'ai récemment répondu à une question sur math.se à propos de la représentation / stockage polynomial. Cela implique généralement une assez petite quantité de données, par exemple, les polynômes à ~ 1000 termes sont typiques; Pourtant, il existe d'énormes différences de performances dans le monde réel (des centaines ou des milliers de secondes contre quelques secondes pour une multiplication) selon l'implémentation.
Fizz
4

C'est certainement un problème si quelqu'un qui développe des algorithmes importants ne comprend pas la complexité des algorithmes. Les utilisateurs d'un algorithme s'appuient généralement sur une bonne qualité d'implémentation qui présente de bonnes caractéristiques de performances. Bien que la complexité ne soit pas le seul contributeur aux caractéristiques de performance d'un algorithme, elle est importante. Une personne qui ne comprend pas la complexité des algorithmes est moins susceptible de développer des algorithmes avec des caractéristiques de performances utiles.

C'est moins un problème pour les utilisateurs d'un algorithme, en supposant que les algorithmes disponibles sont de bonne qualité. Cela est vrai pour les développeurs qui utilisent des langages qui ont une bibliothèque standard importante et bien spécifiée - ils ont juste besoin de savoir comment choisir un algorithme qui répond à leurs besoins. Le problème vient du fait qu'il existe plusieurs algorithmes d'un certain type (par exemple, le tri) disponibles dans une bibliothèque, car la complexité est souvent l'un des critères de sélection. Un développeur qui ne comprend pas la complexité ne peut alors pas comprendre la base pour choisir un algorithme efficace pour sa tâche à accomplir.

Ensuite, il y a des développeurs qui se concentrent (à défaut d'une meilleure description) sur des problèmes non algorithmiques. Par exemple, ils peuvent se concentrer sur le développement d'interfaces utilisateur intuitives. Ces développeurs n'auront souvent pas à se soucier de la complexité de l'algorithme bien que, encore une fois, ils puissent s'appuyer sur des bibliothèques ou d'autres codes en cours de développement de haute qualité.

Rob
la source
3

Cela dépend, mais pas de la quantité de données avec lesquelles vous travaillez, mais du type de travail que vous faites, des programmes que vous développez.

Appelons programmeur qui ne connaît pas la complexité conceptuelle du programmeur noobish.

Le programmeur noobish peut faire:

  • développer des bases de données Big Data - il n'a pas à savoir comment cela fonctionne à l'intérieur, tout ce qu'il doit savoir, ce sont les règles de développement des bases de données. Il sait des choses comme: ce qui devrait être indexé, ... où il vaut mieux faire de la redondance dans les données, où ce n'est pas ...
  • faire des jeux - il lui suffit d'étudier le fonctionnement d'un moteur de jeu et de suivre ses paradigmes, les jeux et l'infographie sont un gros problème de données. Considérez 1920 * 1080 * 32bit = cca 7,9 Mo pour une seule image / image ... @ 60 FPS, c'est au moins 475 Mo / s. Considérez qu'une seule copie inutile de l'image plein écran gaspillerait environ 500 Mo de débit de mémoire par seconde. Mais il n'a pas besoin de s'en soucier, car il utilise uniquement le moteur!

Le programmeur noobish ne devrait pas faire:

  • développer des programmes complexes très fréquemment utilisés, peu importe la taille des données avec lesquelles ils travaillent, ... par exemple, les petites données n'entraîneront pas d'impact notable d'une solution incorrecte pendant le développement, car elles seront plus lentes que le temps de compilation, etc. Donc, 0,5 sec pour un programme simple n'est pas tant du point de vue du programmeur noobish, Eh bien, considérez le serveur serveur, qui exécute ce programme vingt fois par seconde. Il faudrait 10cores pour pouvoir supporter cette charge!
  • développer des programmes pour les appareils embarqués. Les appareils intégrés fonctionnent avec de petites données, mais ils doivent être aussi efficaces que possible, car les opérations redondantes rendent la consommation d'énergie inutile

Donc, le programmeur noobish va bien, quand vous voulez simplement utiliser des technologies. Donc, quand il s'agit de développer de nouvelles solutions, des technologies personnalisées, etc. Il est préférable d'embaucher un programmeur non noobish.

Cependant, si l'entreprise ne développe pas de nouvelles technologies, elle utilise uniquement celles déjà fabriquées. Il serait inutile de recruter un programmeur compétent et talentueux. La même chose s'applique, si vous ne voulez pas travailler sur de nouvelles technologies et que vous êtes bien en train de mettre des idées de clients dans des conceptions et des programmes utilisant des cadres déjà créés, alors c'est une perte de temps, d'apprendre quelque chose dont vous n'aurez jamais besoin, sauf si c'est votre hobby et que vous aimez les défis logiques.

kravemir
la source
1
Cette réponse pourrait être améliorée si elle utilisait une étiquette plus neutre, ou pas d'étiquette du tout, tout comme l'autre réponse qui utilisait le terme «programmeur incompétent».
Moby Disk
1
Je ne sais pas ce que vous entendez par "complexité conceptuelle". D'après mon expérience, les personnes qui ne connaissent pas suffisamment les arbres ou les tables de hachage ne peuvent pas prendre de décisions intelligentes concernant la façon d'indexer (des parties d'une) grande base de données.
Fizz
3

J'hésite un peu à écrire une réponse ici, mais depuis que je me suis retrouvé à tergiverser sur plusieurs autres [certains de mes commentaires ont été déplacés pour discuter], voici comment je le vois ...

Il y a des niveaux / degrés de connaissances à beaucoup de choses dans l'informatique (et par ce terme, je veux dire à peu près l'union de l'informatique avec la technologie de l'information). La complexité du calcul est sûrement un vaste domaine (Savez-vous ce qu'est OptP? Ou ce que dit le théorème d'Abiteboul-Vianu?) Et admet également beaucoup de profondeur: la plupart des gens avec un diplôme CS ne peuvent pas produire les preuves expertes qui vont dans la recherche publications en complexité computationnelle.

n2

J'oserais honnêtement comparer la situation de savoir quand appliquer des concepts de complexité computationnelle (et savoir quand vous pouvez les ignorer en toute sécurité) avec la pratique quelque peu courante (en dehors du monde Java) d'implémenter du code sensible aux performances en C et insensible aux performances des choses en Python, etc. (En passant, cela a été appelé dans un discours de Julia le "compromis standard" .) Savoir quand vous n'avez pas à penser aux performances vous fait gagner du temps de programmation, ce qui est également un bien assez précieux.

Et un autre point est que la connaissance de la complexité de calcul ne vous permettra pas automatiquement d'optimiser les programmes; vous devez comprendre plus de choses liées à l'architecture comme la localisation du cache, [parfois] le pipelining, et la programmation parallèle / multicœur de nos jours aussi; ce dernier a à la fois sa propre théorie de la complexité et des considérations pratiques; un avant-goût de ce dernier à partir d'un article SOSP 2013 "Chaque schéma de verrouillage a ses quinze minutes de renommée. Aucun des neuf schémas de verrouillage que nous considérons surpasse systématiquement tout autre, sur toutes les architectures ou charges de travail cibles. Strictement parlant, pour rechercher l'optimalité, l'algorithme de verrouillage doit donc être sélectionné en fonction de la plate-forme matérielle et de la charge de travail attendue. "

Pétiller
la source
1
À long terme, le développement ou la recherche d'un meilleur algorithme est généralement plus avantageux que le changement de langage de programmation pour les bits sensibles aux performances. Je suis d'accord avec vous qu'il existe une forte association entre le manque de compréhension de la complexité et l'optimisation prématurée - car ils ciblent généralement les bits les moins sensibles aux performances pour l'optimisation.
Rob
1
En pratique, les algorithmes de Schlemiel the Painter (par inadvertance) sont beaucoup plus fréquents que le tri O (n ^ 2).
Peter Mortensen
-1

Si vous ne connaissez pas le big-O, vous devriez l'apprendre. Ce n'est pas difficile et c'est vraiment utile. Commencez par rechercher et trier.

Je remarque que de nombreuses réponses et commentaires recommandent le profilage , et ils signifient presque toujours l' utilisation d'un outil de profilage .

Le problème est que les outils de profilage sont partout sur la carte en termes d'efficacité pour trouver ce dont vous avez besoin pour accélérer. Ici, j'ai énuméré et expliqué les idées fausses dont souffrent les profileurs.

Le résultat est que les programmes, s'ils sont plus grands qu'un exercice académique, peuvent contenir des géants endormis , que même le meilleur profileur automatique ne peut pas exposer. Cette publication montre quelques exemples de la façon dont les problèmes de performances peuvent se cacher des profileurs.

Mais ils ne peuvent pas se cacher de cette technique.

Mike Dunlavey
la source
Vous prétendez que "Big-Oh" est utile, mais vous préconisez une approche différente. De plus, je ne vois pas comment l'apprentissage du "Big-Oh" (mathématiques) peut "commencer par la recherche et le tri" (problèmes d'algorithme).
Raphaël
@Raphael: Je ne préconise pas une approche différente - elle est orthogonale.Big-O est une connaissance de base pour comprendre les algorithmes, alors que trouver des problèmes de performance dans un logiciel non-jouet est quelque chose que vous faites après l'écriture et l'exécution du code, pas avant. (Parfois, les universitaires ne le savent pas, alors ils continuent d'enseigner gprof, faisant plus de mal que de bien.) Ce faisant, vous pouvez ou non trouver que le problème est l'utilisation d'un algorithme O (n * n), vous devriez donc être en mesure de reconnaître cela. (Et big-O n'est qu'une propriété mathématiquement définie des algorithmes, pas un sujet différent.)
Mike Dunlavey
"Et big-O est juste une propriété mathématiquement définie des algorithmes, pas un sujet différent." - c'est faux, et dangereusement. "Big-Oh" définit les classes de fonctions ; en soi, cela n'a rien à voir avec les algorithmes.
Raphael
Continuons cette discussion dans le chat .
Raphael