Un programmeur compétent devrait-il pouvoir proposer son propre algorithme de chemin le plus court?

58

Je subis une crise de confiance en mes capacités en tant que programmeur informatique.

Hier, j'ai essayé de créer mon propre algorithme de chemin le plus court pour un graphe et après quelques heures, j'ai simplement jeté l'éponge et appris l'algorithme de Dijkstra.

Est-ce le genre de chose qu'un bon programmeur devrait pouvoir "réinventer" en quelques heures ou suis-je irréaliste?

Eh bien, au moins j'ai été capable de réinventer le genre de bulle: D

Programmeur débutant
la source
7
Quelqu'un qui a eu recours à l'assurance-chômage pendant 20 ans aura probablement du mal à trouver une solution à un problème d'un autre domaine, dans peu de temps.
Coder
38
Passer beaucoup de temps sur les sites SE donne à chacun une crise de confiance, je pense! (Pas que ce soit une mauvaise chose). Le bonheur dans la vie, c'est de trouver l'équilibre parfait entre l'acceptation de ce qui est et le désir de le changer.
TrojanName
2
Je ne pouvais pas le réinventer moi-même, mais j'essayais de me rappeler comment cela fonctionnait. assurez-vous de bien comprendre cette animation: upload.wikimedia.org/wikipedia/commons/2/23/…
Emploi du
6
@Brian La tragédie du génie local. Vous ne pouvez presque plus être le meilleur de rien.
Rei Miyasaka
7
un bon ordinateur scientifique devrait , mais pas nécessairement un programmeur informatique ou ingénieur logiciel
Neil McGuigan

Réponses:

118

Un bon programmeur devrait se rendre compte qu'un bon algorithme a déjà été écrit pour résoudre un problème et ne perd pas de temps à réinventer les roues.

Je doute que Dijkstra ait mis au point l'algorithme du plus court chemin en quelques heures. Cela semble donc être un standard très élevé à utiliser pour déterminer si quelqu'un est un «bon programmeur».

GSto
la source
25
@Nakilon - Les programmeurs qui ignorent les solutions existantes perdent juste leur temps, et s'ils ne perdent pas leur temps, ils font une solution pire. Voir: Tout le monde fait son propre schéma de hachage de mot de passe contre bcrypt.
Rétablir Monica
10
@GSto: d'après wikipedia, Dijkstra a proposé l'algorithme en moins d'une heure: 20 minutes, selon la première note sur wikipedia: en.wikipedia.org/wiki/Dijkstra%27s_algorithm
woliveirajr
9
C'est un algorithme relativement simple, mais Dijkstra était très talentueux et avait suivi une formation en physique théorique et en mathématiques avancées. Il n'y a rien de tel que quelques années à rédiger des preuves pour améliorer sa capacité à concevoir des algorithmes.
kevin cline
19
@ woliveirajr - Eh bien, je suis sûr que Newton a mis autant de temps à proposer les lois du mouvement. Après y avoir réfléchi pendant 20 ans.
Rook
6
@Nakilon - Oui, c'est pour ça que tout le monde écrit tout en C, parce que sinon, vous n'êtes qu'un codeur, utilisant le langage de haut niveau de quelqu'un d'autre. Oh, attends, je veux dire assemblage, sinon tu utilises simplement le langage de bas niveau de quelqu'un d'autre. Oh, attends, je parle d'inversion des commutateurs pour changer les circuits électriques, sinon tu utilises simplement les instructions de quelqu'un d'autre. Ou vous savez, vous pouvez simplement utiliser ce qui existe déjà et travailler à créer quelque chose de nouveau . Pourquoi perdre du temps à réinventer l'algorithme de Dijkstra quand on peut inventer quelque chose de nouveau, comme un programme qui l'utilise?
Rétablir Monica
54

Est-ce le genre de chose qu'un bon programmeur devrait pouvoir "réinventer" en quelques heures ou suis-je irréaliste?

Tout d’abord, vous confondez peut-être programmation avec informatique théorique. Un programmeur fantastique a besoin d’une bonne base en informatique, mais il n’a pas besoin d’être fantastique. Dijkstra était fantastique en informatique.

Deuxièmement, je m'attendrais à ce que quiconque ayant une bonne compréhension des graphiques développe son propre parcours après un peu de réflexion. Mais pas un algorithme de chemin le plus court. L'algorithme de Dijkstra en particulier est très sophistiqué. Une fois que vous comprenez, c'est aveuglant. Mais la plupart des choses sont comme ça.

Vous pourriez probablement en déduire une sorte d'algorithme de chemin le plus court après avoir essayé quelques trucs et en avoir donné le temps. Mais ne soyez pas déçu si cela prend des heures, voire quelques jours. C'est complètement correct et normal.

(Attention, vous devriez être capable de résoudre le problème en quelques heures, mais cela ne produirait pas un algorithme fonctionnel, même sur des graphiques assez petits.)

Konrad Rudolph
la source
56
Ne vous inquiétez pas, si la force brute ne fonctionne pas, vous n'en utilisez pas assez.
Robbie
2
+1 pour souligner la différence entre CS théorique et programmation. La programmation est une résolution de problèmes du monde réel, et le CS théorique est là pour la soutenir. Cependant, la théorie théorique n'est pas indispensable à 100% dans la programmation quotidienne de la plupart des gens.
Phil
17

Est-ce le genre de chose qu'un bon programmeur devrait pouvoir "réinventer" en quelques heures ou suis-je irréaliste?

Absolument irréaliste. Les gens ne font pas que "monter" avec des algorithmes dans quelques heures. Cela demande beaucoup d'efforts et de travail. Pour citer ce blog:

Dans la programmation de Pearls, Bentley, citant Donald Knuth, a déclaré: "Alors que la première recherche binaire a été publiée en 1946, la première recherche binaire qui fonctionne correctement pour toutes les valeurs de n n’apparaît qu’en 1962."

et la version de Bentley était également problématique lorsqu’elle était mise en œuvre pour les grands ensembles.

De plus, un bon programmeur sait quels outils sont à sa disposition et quand utiliser ces outils. Vous n'obtenez pas de points supplémentaires pour votre originalité ou pour faire les choses différemment - vous voulez que cela fonctionne et fonctionne bien.

BlackJack
la source
1
BlackJack, je devais rejoindre ce forum pour signaler que Bentley n'avait pas dit ce que vous prétendiez avoir dit: Knuth l'a dit, et Bentley l'a cité. Lorsque j'ai lu votre commentaire, je pensais que vous aviez fait valoir un bon argument, mais j'aime bien vérifier mes sources et je n'avais jamais entendu parler de Bentley. J'ai cependant entendu parler de Knuth et je peux faire confiance à ce qu'il dit. S'il vous plaît vérifier vos sources mieux la prochaine fois.
Richard
8
@Richard - Le commentaire était "Dans Programming Pearls, Bentley dit ..." Knuth fut le premier à le dire, mais ma source est Programming Pearls, pas TAoCP, alors j'ai écrit ce que Bentley a écrit. Je n’ai pas prétendu que Bentley en était l’initiateur - j’ai simplement cité ce qui est dit dans le livre. Les auteurs eux-mêmes n’ont pas inventé une grande quantité de matériel dans les livres, alors je ne vois pas pourquoi vous le verriez de cette façon.
BlackJack
En attribuant la citation uniquement à Bentley, vous omettez de créditer Knuth et, si la déclaration de "Bentley" était fausse, vous mettez Bentley dans la position d'avoir produit des informations incorrectes, plutôt que simplement de les diffuser. Strictement parlant, vous n’avez pas dit ce que Bentley avait dit: si vous l’aviez fait, vous auriez dit: "Bentley a dit que Knuth avait dit cela ...". La citation est bien utilisée ici, mais elle est sortie du contexte dans lequel elle a été dite.
Richard
3
@Richard - La citation que j'ai citée provient directement du blog, qui cite directement du livre (littéralement, je pense que c'est la page 57 de la première édition). Si la déclaration vous pose problème, contactez l’auteur du blog et demandez-lui de le modifier.
BlackJack
1
@ Richard et BlackJack: Vous avez tous les deux raison, mais l'attribution à l'auteur d'origine ajoute crédibilité et contexte à la déclaration. Mon édition devrait suffire.
Steven Evers
9

Il est très peu probable que vous puissiez trouver une solution meilleure que celles que vous pouvez choisir.

Sortir avec un meilleur algorithme que celui considéré comme "le meilleur" (dans votre cas, le plus court) n'est pas quelque chose que tout le monde peut faire. Ce n'est probablement même pas possible.

Un bon programmeur devrait être en mesure de comprendre la logique de l’algorithme et de comprendre pourquoi il est meilleur ou pire (ou tout simplement inadéquat pour ce problème particulier) que d’autres algorithmes qui tentent de résoudre le même problème.

(s) Il devrait également être en mesure de savoir si c'est vraiment la meilleure façon de résoudre ce problème particulier.

Quoi qu’il en soit, si vous voulez vous exercer, vous pouvez toujours essayer d’écrire votre implémentation personnelle d’un algorithme, en essayant de résoudre un problème en utilisant votre esprit. Ce n'est peut-être pas le meilleur, mais c'est une bonne pratique pour résoudre les problèmes.

Jose Faeti
la source
6

Cela me rappelle quelque chose que j'ai lu sur la différence entre le "génie logiciel" (ce que j'appellerais la programmation) et les autres disciplines de l'ingénierie. En y réfléchissant, je pense que c’était le livre original Design Patterns. Je suis sûr que quelqu'un ici peut le citer par cœur.

Quoi qu’il en soit, le but (bien que pas tout à fait adapté à la conception d’algorithmes) était que les disciplines d’ingénierie sont codifiées; aucun ingénieur civil ne passera probablement du temps à essayer de réinventer le faisceau en I, mais les programmeurs le font tout le temps. Le problème (et je réalise que je ne fais que faire écho aux sentiments de nombreuses personnes) est que ce comportement est source de gaspillage et est sujet à des erreurs, et sert davantage l'ego que la solution.

L'informatique m'a amené à la programmation et j'aime les deux. Cependant, je suis un meilleur programmeur qu'un informaticien. Je ne vous accuserais jamais d'être incompétent parce que vous ne pouviez pas réinventer l'algorithme de Dijkstra en après-midi. Je m'interrogerais sur votre compétence en tant que programmeur si vous ne pouviez pas reconnaître un problème pouvant être résolu via un algorithme de graphe le plus court.

Cela dit, je pense que penser aux algorithmes et essayer de concevoir et d’en implémenter de nouveaux est (potentiellement) amusant et (presque) toujours instructif. J'essaie juste de séparer proprement mon temps de CS de mon temps de programmation. Pour les programmeurs, notre temps (surtout rémunéré) est mieux utilisé pour résoudre des problèmes pratiques plutôt que ceux d’astract. De plus, le temps passé chez CS me brise presque toujours.

Keith Layne
la source
Oh, ironie ... maintenant que je peux commenter n'importe où, dois-je supprimer la réponse qui m'a valu ce privilège? Il devrait y avoir un badge pour cela.
Keith Layne
Il y a - discipliné cependant, si votre réputation est recalculée, vous êtes redescendu à 1.
ChrisF
Oui, c’est exactement ce que je veux dire… j’irais au-delà de la discipline à ce stade, à l’OMI. Si je convertissais ma réponse en commentaire avant suppression, je pourrais tout avoir ... Je suggère un nouveau badge appelé UberDisciplined pour toute suppression entraînant le retour à un nouveau statut d'utilisateur. :)
Keith Layne
3

Vous ne remarquerez pas les mêmes choses que tout le monde. Je pense que c'est juste une réalité de la vie avec laquelle nous devons vivre. Cela dépend en grande partie de votre apprentissage passif et des modèles mentaux que vous avez développés à la suite de ceux-ci.

Je connais des programmeurs très intelligents et compétents qui ont dû apprendre le droit de DeMorgan à l'école avant de pouvoir le faire de manière cohérente. Il m'est arrivé de comprendre par moi-même l'algorithme de Dijkstra (et je dois admettre que j'en suis un peu fier), mais il m'a fallu beaucoup de temps avant même de comprendre le genre de bulles.

Plus célèbre, Einstein, qui, selon vous, serait un expert en théorie des nœuds, n'a pas pu nouer ses propres lacets avant l'âge de dix ans environ.

Il y a de bonnes chances que vous ayez réinventé sans le savoir beaucoup de choses que beaucoup d'autres n'auraient jamais découvertes si elles n'avaient pas été enseignées explicitement.

Rei Miyasaka
la source
3

Je prie de différer pour ce que la plupart des réponses disent. Bien que je ne m'attende pas à ce qu'un programmeur de n'importe quel niveau puisse se débrouiller seul avec l'algorithme de Dijkstra, je m'attendrais certainement à ce qu'il trouve n'importe quel moyen (efficace ou non) de résoudre le problème.

Par exemple, vous avez dit en guise de commentaire que vous pouviez créer vous-même une sorte de bulle. Je sais que c'est le pire des algorithmes de tri, mais vous avez trouvé un moyen de résoudre un problème, et c'est ce que je m'attends à ce que les programmeurs soient en mesure de: trouver un moyen de résoudre les problèmes.

Bien entendu, il est également utile de rechercher et de trouver des solutions proposées par d'autres personnes, mais l'extrême extrême de ce problème est un type qui ne pense pas à lui-même et dont les programmes constituent un condensé des recherches Google.

Je pense que je parais plus sévère que je ne le souhaite réellement, mais mon objectif est le suivant: je m'attendrais à ce qu'un programmeur fasse preuve de suffisamment de créativité pour proposer une solution à un problème, même si la solution est boguée ou compliquée.


Donc, pour revenir à votre cas, je ne pense pas que vous devriez avoir à proposer l'algorithme de Dijkstra, mais si vous avez la possibilité d'écrire un algorithme pour essayer plusieurs possibilités et trouver le chemin le plus court sans terminer sur une boucle infinie, alors vous avez mon approbation.

(BTW, mon approbation compte dans le même ordre d’importance qu’un coupon gratuit de lavage de voiture.)

Alpha
la source
3
Je conviens que oui, un programmeur compétent devrait pouvoir proposer le type de bulle ou son équivalent. Ce pourrait même être une utilisation productive du temps de le mettre en œuvre et de l’essayer, peut-être simplement pour mieux comprendre le problème. Mais je pense qu’il faut dire qu’aucun programmeur compétent n’allait alors continuer et l’utiliser réellement dans le code de production. C'est ce qui incite vos clients à revenir l'année prochaine et à se plaindre que, maintenant qu'ils ont plus de données à traiter, votre algorithme O (n!) Prendra deux fois l'âge de l'univers ...
Thomas Padron-McCarthy
Qui se soucie si vous pouvez inventer des algorithmes, si vous ne pouvez même pas reconnaître quand ça craint? L'autocritique est aussi importante pour un programmeur que la créativité. Je préférerais travailler avec un programmeur qui reconnaît vite que sa solution prend trop de temps ou qui risque d’être la meilleure, plutôt que de le faire avec un programmeur qui souhaite réinventer toutes les roues parce que cela nuit à son ego.
Rei Miyasaka
Je suis d'accord sur les deux points, mais je pense que nous mesurons deux choses différentes. L'un est la capacité du programmeur à résoudre des problèmes (ce que je considère essentiel). L'autre est l'autocritique (je considère cela essentiel mais pas pour la programmation: à vie) et la capacité de juger le code (hautement souhaitable). Je dirais aussi que les solutions qui durent éternellement ne sont pas vraiment des solutions, n'est-ce pas? ;)
Alpha
2

Oui, il / elle devrait.

C'est peut-être l'équivalent moral de la sorte de bulle, mais je pense qu'un bon programmeur devrait être capable de proposer au moins quelque chose qui fonctionne, aussi inefficace que cela puisse être.

Inutile de dire que si ce problème particulier se présentait, un bon programmeur examinerait au préalable s'il existe une bibliothèque pour le faire à sa place, ou quels algorithmes publiés le font et sont faciles à implémenter.

Bien sûr, de nombreuses tâches de programmation sont beaucoup moins difficiles et tout le monde n’a pas besoin de pouvoir s’attaquer à des problèmes aussi difficiles. Mais vous voudrez peut-être que votre équipe soit dotée d'un tel esprit, car vous pourriez avoir des problèmes compliqués spécifiques à un projet où vous ne pouvez pas compter sur des tonnes de recherches scientifiques antérieures.

Hans-Peter Störr
la source
1

Ne t'en fais pas

En tant que programmeur Perl, je ne veux jamais réinventer la roue. C'est le travail de CPAN. S'il existe un algorithme ou un module simple et bien supporté, nous l'utilisons. S'il n'y a pas un bon module, alors nous inventons la roue. C'est l'une des plus grandes choses à propos de Perl.

Donc, ce que je dis, c'est ceci:

  1. Je ne recommande pas de réinventer la roue mais quand vous le faites ...
  2. Essayez de ne pas le réinventer complètement et ...
  3. Ne vous inquiétez pas si vous ne pouvez pas le faire. C'est pourquoi nous avons une communauté de programmation :-).
Dynamique
la source
Il ne s'agit pas de réinventer, il s'agit de résoudre des problèmes en général. Si vous n'essayez pas d'inventer des choses par vous-même, vous ne vous améliorerez jamais.
Nils
0

La théorie des graphes et les algorithmes qui y sont appliqués paraissent simples en surface, mais en sont généralement bien éloignés. On pourrait penser que la formation de graphes non croisés (plans) est simple, par exemple à première vue. L'année dernière, j'ai beaucoup étudié ce problème (planéité via l'élimination des sous-graphes de Kuratowski). Je peux vous dire, à partir de cette expérience, que les personnes qui écrivent ces algorithmes passent généralement la durée de leurs études de doctorat, et parfois que la recherche est faite en équipe. Et en tant que chercheurs , c’est leur seul objectif de travail au cours de cette période. Il n’est pas raisonnable de penser que nous, les ingénieurs sur le terrain, pouvons nous attendre à la même chose. Comme quelqu'un d'autre l'a dit à juste titre, c'est une évidence lorsque la solution est devant vous. Cela semble toujours être le cas!

Ingénieur
la source
0

Est-ce le genre de chose qu'un bon programmeur devrait pouvoir "réinventer" en quelques heures ou suis-je irréaliste?

J'irais jusqu'à dire que si vous êtes capable d'inventer un algorithme pour un problème connu tel que Shortest Path, vous êtes un mauvais programmeur.

Cela voudrait dire que vous ignorez toute une histoire sur le problème du Shortest Path , allant d'un algorithme O (| V | ^ 4) publié en 1955 à l'algorithme O (E + V log V) publié en 1984 (qui est celui de Dijkstra). algorithme avec les arbres de Fibonacci). Vous avez presque la garantie de faire pire que les algorithmes déjà conçus. Pire encore, il y a de bonnes chances que votre algorithme présente des lacunes ou des erreurs le rendant incorrect. En outre, vous passerez sûrement beaucoup plus de temps à concevoir votre algorithme, à le mettre en œuvre et à le tester que le temps nécessaire pour réutiliser un algorithme existant.

Laissez la conception des algorithmes aux concepteurs d'algorithmes. Les programmeurs sont consommateurs de leurs résultats. Les programmeurs combinent des algorithmes et les mettent au travail sur des tâches réelles. Un policier n’a pas besoin de pouvoir réinventer la loi pour pouvoir travailler ou pour être un bon officier.

Je vous encourage même à utiliser des implémentations faites par des experts plutôt que d'implémenter vous-même les algorithmes pour un algorithme moyennement compliqué. Il est plus probable que vous ayez raison, car ils ont probablement accéléré le processus et vous font gagner beaucoup de temps. Cela est particulièrement vrai pour les algorithmes de chiffrement, car vous bénéficiez d'une demande supplémentaire en matière de sécurité, que seuls des experts peuvent généralement vous fournir.

Alex ten Brink
la source
Les algorithmes cryptographiques sont faciles à vérifier une implémentation de; Les vecteurs de test corrects connus sont à la pelle des dizaines pour tout algorithme spécifié publiquement, et il est correct ou non. (Vous pouvez obtenir des performances sous-optimales avec une implémentation personnalisée, mais si elle est correcte, vous pouvez travailler dessus.) La partie la plus difficile de la cryptographie est la génération de nombres aléatoires, la gestion correcte des clés brutes et des tables d’extension en mémoire, traitement des entrées utilisateur (salage, etc.), stockage de quelque chose pour vous permettre de déterminer si les données déchiffrées sont valides, etc.
un CVn
Je pensais plus au genre d'attaques de chronométrage, etc., des choses à peu près inconnues des programmeurs. Ce n'est pas toujours un problème, mais néanmoins un problème important. En outre, la combinaison de primitives cryptographiques ne fonctionne généralement pas comme prévu, il s'agit également d'un élément difficile de la sécurité.
Alex ten Brink
Bien que le minutage des attaques, etc. soit certainement une préoccupation valable (et pas seulement en cryptographie), je dirais que la susceptibilité d'une implémentation à cela n'a aucun impact sur son exactitude . Et il existe de très nombreuses façons d’encrasser dans la cryptographie bien plus que simplement permettre des attaques par minutage. Bruce Schneier avait l'habitude de diriger sa série Doghouse ; Je n'ai rien vu récemment, mais il y a beaucoup d'exemples de prudence. google.com/search?q=site%3Aschneier.com+%22the+doghouse%22
un CVn du