Lors du concours Google Code Jam (2013) en cours , il y avait un problème qui nécessitait plus de 200 lignes de code pour les personnes C ++ et Java, par rapport aux personnes de Python qui ont résolu le même problème en utilisant seulement 40 lignes de code.

Python n'est pas directement comparable à C ++ et Java, mais la différence de verbosité que je pensais pourrait peut-être avoir une influence sur l'efficacité de l'algorithme.

Quelle est l'importance de connaître le bon algorithme par rapport au choix de la langue? Un programme Python parfaitement implémenté pourrait-il être implémenté en C ++ ou en Java de manière plus efficace (en utilisant le même algorithme) et cela at-il une relation avec la verbosité naturelle de certains langages de programmation?

De toute évidence, si vous envisagez cette question dans le contexte de Google Code Jam, la réflexion algorithmique est clairement plus importante pour résoudre des problèmes algorithmiques.

Cependant, dans la vie quotidienne, environ un million d'autres facteurs doivent également être pris en compte, ce qui rend la question beaucoup moins noire que blanche.

Juste un contre-exemple: si vous avez besoin de 200 lignes supplémentaires en Java, mais que tout le monde dans votre entreprise connaît Java, ce n’est pas grave. Si vous pouviez l'écrire en 5 lignes de Python ou de toute autre langue, mais que vous seriez le seul dans l'entreprise à connaître cette langue, c'est une grosse affaire. Une telle affaire, en fait, que vous ne serez même pas autorisé à le faire et que vous devrez plutôt l'écrire en Java.

Du point de vue des artisans, nous essayons toujours d'approcher avec le bon outil pour le travail, mais le mot juste ici est si difficile que l'on peut facilement se tromper.

Au contraire, j'ai trouvé que la pensée algorithmique dans les entreprises était presque absente. Seules quelques personnes choisies le possèdent, alors que le citoyen moyen a souvent déjà du mal à estimer les complexités à l'exécution des boucles, recherches, etc.

En termes de compétitions algorithmiques, cependant, mon expérience personnelle de la compétition pendant plusieurs années m’indique clairement que vous devez vous en tenir à une seule langue. La vitesse est un facteur important et vous ne pouvez tout simplement pas vous permettre de perdre du temps sur vos outils, alors que vous devriez le consacrer à la résolution des problèmes dans les délais impartis. Considérez également qu'écrire 200 lignes de code Java sans réfléchir est toujours beaucoup plus rapide que de créer manuellement 50 lignes de code python compliqué nécessitant beaucoup de réflexion, tout en résolvant plus ou moins le même problème.

Enfin, assurez-vous de bien comprendre les principales différences entre le code de concurrence algorithmique et le code de production de la société. J'ai vu des codeurs algorithmiques fantastiques, qui écrivaient un code horrible que je n'accepterais jamais dans un produit.

Je dirais que, même en dehors des compétitions, la pensée algorithmique est plus importante que de connaître chaque astuce pour une langue spécifique.

Bien sûr, vous souhaitez connaître au mieux la langue avec laquelle vous travaillez, mais les langues vont et viennent, tandis que la capacité de penser de manière abstraite en termes d’algorithmes est une compétence hautement transférable.

Exemple: si je me souviens bien, il y a quelque temps un article sur les programmeurs dans lequel quelqu'un se plaignait de l'échec de FizzBuzz dans une interview et en imputait son manque de connaissance sur l'opérateur modulo de Java. Cette conclusion est fausse: le manque de connaissances sur le fonctionnement de modulo l'a rendu incapable de penser le problème de manière algorithmique et de le résoudre, même en l'absence d'un opérateur modulo dédié. Pour aller plus loin: Java a une classe Tree - et si, à l'avenir, vous devez travailler avec un langage qui n'implémente pas cette classe? Encore une fois, la capacité de réfléchir au problème l'emporte sur les détails spécifiques à la langue.

J'admets que les exemples sont simplistes, mais ils aident à faire passer le message.

La langue compte.

La DARPA et l'US Navy ont mené une expérience de tir au canon il y a près de 20 ans. Le vainqueur en fuite du cheval noir était Haskell. Ada et C ++ étaient tous deux représentés; Java n'était pas.

À peu près au même moment, Pratt & Whitney a mené une étude d'exploration de données sur des projets de contrôleur de moteur à réaction, en examinant des données de fiches de présence et de suivi des bogues. Ils ont découvert qu'Ada donnait le double de la productivité du programmeur et un quart de la densité de défauts de tout autre langage utilisé.

Atari avait l'habitude d'utiliser FORTH pour développer des jeux vidéo et le fait qu'ils l'utilisent était considéré comme extrêmement exclusif.

Les commentaires de Paul Graham sur l'utilisation de LISP sont bien connus. Les commentaires d' Erann Gat sur LISP au JPL sont également convaincants, mais pas aussi connus.

Le logiciel d'avionique du Boeing 777 est à peu près tout Ada. Leur expérience était très bonne, même si un sous-traitant important a dû recommencer à mi-chemin.

La langue compte.

Quelques points:

• Les premières positions ont tendance à être C ++ / C / Java, quel que soit le nombre de lignes de code utilisées pour faire la différence entre ce langage et un autre langage. C'est peut-être plus lié au fait que les meilleurs codeurs ont tendance à choisir ces langues plutôt que d'autres, probablement à cause de leur vitesse brute.
  Malheureusement, vous ne pouvez pas facilement voir le langage de programmation sur Google Code Jam, mais j'ai téléchargé quelques-uns des meilleurs et, pour autant que je m'en souvienne, il s'agit principalement de C / C ++. TopCoder (un site d'hébergement de concours de programmation en ligne populaire) a généralement des résultats similaires.

• Comme ils sont assez bas, je suis sûr que vous ne battrez pas facilement le C / C ++ en termes de temps d'exécution brut (et que celui de Java n'est pas trop loin derrière). D'après mon expérience, les langages à typage dynamique ont tendance à être beaucoup plus lents que les langages à typage statique. La solution optimale peut même ne pas être assez rapide dans certaines langues, mais cela ne devrait pas être une règle générale.

• Le bon algorithme est vital. Si vous saviez comment résoudre tous les problèmes (de manière très détaillée) dès le départ et que vous êtes un bon codeur rapide, vous gagnerez très probablement, quelle que soit la langue dans laquelle vous codez (à condition de choisir la solution optimale dans cette langue). est assez rapide).

• Le nombre de lignes droites n'est pas si grave. Une fois que vous aurez acquis suffisamment d'expérience en programmation, vous saurez que vous pouvez passer 10 minutes à programmer 10 lignes ou 200 lignes, tout dépend de la complexité des lignes. En outre, si vous avez codé des codes similaires des centaines de fois, vous pourrez le faire assez rapidement. Mentionnez également toutes les macros que les principaux codeurs C / C ++ utilisent souvent pour optimiser leur temps de codage.

• Frank avance un bon point - (en dehors des compétitions de programmation), vous ne pouvez pas coder en Python pour votre entreprise si leur base de code est en C ou quoi que ce soit, vous devez vous conformer à leur langage.

• Il est relativement facile de basculer entre les langues, il n'est pas facile de construire des années de connaissances en pensée algorithmique. Je suis prêt à parier que presque tous les excellents programmeurs peuvent passer à une autre langue (vaguement similaire) en une semaine environ. Peut-être ne sera-t-il pas assez bon pour gagner des compétitions de programmation dans cette langue (lui donner encore 2 semaines), mais il aura les bases bas.

La même logique peut-elle être mieux implémentée en C ++? Bien sûr que si, vous entendez mieux, plus rapide et plus efficace en termes de mémoire. Le problème est que la quantité d'effort requise pour le faire est considérablement plus élevée. De plus, théoriquement, vous pourriez toujours aller au niveau inférieur et l'implémenter en C pur ou même en ASM, ce qui prendrait encore plus de temps, mais vous pourriez avoir un code encore plus optimisé.

Bien sûr, dans le cas de compétitions comme Code Jam ou TopCoder, ce n’est pas un gros problème, car il n’ya que 40 lignes contre 200 lignes. Par contre, dans ce type de concurrence, l’important est la complexité spatio-temporelle de l’algorithme. Alors que dans l' application de la vie réelle, YMMV, dans ces types de compétitions O (n) algorithme écrit dans le plus lent des langues sera toujours battre O (n²) écrit dans le plus rapide des langues. Surtout qu'il y aura plusieurs tests qui sont le pire des cas.

Mais en dehors des compétitions, si nous parlons de gros projets dans la vie réelle, il ne s'agit plus de 40 lignes contre 200 lignes. Dans les grands projets, l’énorme base de code commence à poser problème. A quel point vous arrivez à:

C ++ vs Python?

Pure Python est lent. C'est pourquoi l'interpréteur Python standard (CPython) est écrit en C. Pratiquement tous avec des fonctions intégrées écrites en tant que C hautement optimisé. Il peut également être facilement utilisé avec des bibliothèques C (via ctypes ou en tant que modules cpython natifs ) et avec des bibliothèques C ++. via Boost :: Python . De cette façon, vous pouvez écrire votre logique de haut niveau en Python, un langage flexible qui permet un prototypage et une adaptation rapides (ce qui signifie que vous pouvez passer plus de temps à peaufiner et à améliorer votre algorithme). OTOH, vous pouvez écrire vos fonctions de bibliothèque de niveau inférieur dans le module C ou C ++. SciPy, qui est une bibliothèque Python, est un bon exemple de cette approche. Cependant, sous le capot, il utilise des bibliothèques numériques hautement optimisées telles que ATLAS, LAPACK, Intels MKL ou ACML d'AMD.

À mon avis, ce que les gens considèrent couramment comme un "langage de programmation" sont en réalité trois choses distinctes:

1. Type de langue et syntaxe
2. Langue IDE
3. Bibliothèques disponibles pour une langue

Par exemple, lorsque quelqu'un parle de C # dans une discussion, vous pensez peut-être qu'il parle de syntaxe de langage (1), mais il est certain à 95% que la discussion impliquera .Net framework (3). Si vous ne concevez pas une nouvelle langue, il est difficile et généralement inutile d’isoler (1) et d’ignorer (2) et (3). En effet, l'IDE et la bibliothèque standard sont des "facteurs de confort", des choses qui affectent directement l'expérience d'utilisation d'un outil donné.

Ces dernières années, j'ai moi aussi participé à Google Code Jam. La première fois que j’ai opté pour C ++ parce qu’il supporte bien la lecture de l’entrée. Par exemple, la lecture de trois entiers à partir d’une entrée standard en C ++ ressemble à ceci:

int n, h, w;
cin >> n >> h >> w;

En C #, la même chose ressemblerait à ceci:

int n, h, w;
string[] tokens = Console.ReadLine().Split(' ');
n = int.Parse(tokens[0]);
h = int.Parse(tokens[1]);
w = int.Parse(tokens[2]);

C'est beaucoup plus de frais généraux mentaux pour une fonctionnalité simple. Les choses deviennent encore plus compliquées en C # avec une entrée multiligne. Peut-être que je n'ai tout simplement pas trouvé une meilleure solution à l'époque. En tout cas, je n’ai pas réussi à passer le premier tour parce que j’avais un bug que je ne pouvais pas corriger avant la fin du tour. Ironiquement, la méthode de lecture des entrées a obscurci le bogue. Le problème était simple, l'entrée contenait un nombre trop grand pour un entier de 32 bits. En C # int.Parse(string)lève une exception, mais en C ++, le flux d'entrée du fichier définit un certain indicateur d'erreur et échoue sans que le développeur non averti ne soit pas au courant d'un problème.

Les deux exemples montrent comment la bibliothèque a été utilisée plutôt que la syntaxe du langage. La première montre la verbosité et l’autre la fiabilité. De nombreuses bibliothèques sont portées dans plusieurs langues et certaines langues peuvent utiliser des bibliothèques qui ne sont pas spécialement conçues pour elles (voir la réponse de @ vartec sur Python avec les bibliothèques C).

Pour conclure, connaître le bon algorithme peut aider. Dans les compétitions de codage, c'est crucial, en particulier lorsque des ressources telles que le temps d'exécution et la mémoire sont volontairement limitées. Dans le développement d'applications, c'est bienvenu mais généralement pas crucial. La maintenabilité y est plus importante. Pour ce faire, il est possible d’appliquer des modèles de conception corrects, d’avoir une bonne architecture, un code lisible et une documentation pertinente. Toutes ces méthodes dépendent fortement des bibliothèques internes et tierces. Je trouve donc plus important de savoir quel type de roues sont déjà inventées et comment elles s’adaptent, puis comment fabriquer les miennes.

Si vous souhaitez participer à des compétitions de programmation chronométrées, vous devez apprendre le langage le plus expressif autorisé dans la compétition. Perl serait probablement le mieux, suivi de Ruby ou Python. Vous aurez toujours besoin d’une bonne facilité avec les algorithmes, mais au moins vous ne vous perdrez pas à écrire quelque chose comme:

Integer prev = b.get(k)
if (prev == null) prev = 0
Integer v = a.get(k);
if (v == null) v = 0;
b.put(prev + v);

au lieu de

b[k] += a[k]

Ne vous inquiétez pas pour apprendre plusieurs bibliothèques. Ils sont tous très similaires et la documentation est en ligne. La maîtrise de langages plus expressifs fera de vous un meilleur programmeur (éventuellement frustré) dans des langages moins expressifs. Le contraire n'est pas vrai.

NB

La différence entre 200 lignes de code et 40 lignes de code est énorme et elle est encore plus grande lorsqu'il s'agit de la différence entre un programme de 200 000 lignes et un programme de 40 000 lignes. Ensuite, il y a une différence entre une équipe de cinq personnes plus un manager et une équipe de un ou deux.

Tout algorithme peut être implémenté dans n’importe quel langage de programmation. Après tout, ce n'est pas la syntaxe qui compte. Mais utiliser un langage de haut niveau comme Python a ses propres avantages. Moins de travail et moins de codage. Donc, pour implémenter un algorithme en Python, vous aurez besoin de moins de lignes que ce qui est nécessaire dans un langage de bas niveau comme C.

Python a la plupart des structures de données intégrées dans sa bibliothèque. Mais en C, nous devons partir de zéro et utiliser une structure pour tout construire. Il existe certes des différences entre le langage de haut niveau et le langage de bas niveau, mais le langage ne devrait pas vous empêcher de mettre en œuvre un algorithme.

Bien que l'extrapolation de l'exemple "40 CdV contre 200 CdL", en disant "bon, seulement un cinquième de la CdT totale est évidemment plus rapide à écrire, donc ça doit être mieux" peut sembler tentante, je pense vraiment qu'il y a peu de vérité à ce sujet.

Optimiser le moins possible la LoC n’est presque jamais une bonne idée à mon avis. Oui, chaque LoC écrite est un potentiel de bugs, et vous n’avez jamais à déboguer ce que vous n’avez jamais écrit, etc. Le but est d'optimiser la lisibilité et le découplage. Peu importe si vous résolvez un problème en utilisant une regex grosse de 20 lignes, par opposition à l'écriture d'un module de 1k LoC. La regex sera un mur opaque, extrêmement sujet aux bugs, difficile à comprendre, cauchemardesque à modifier sans changer son comportement de manière irréprochable, etc.

Se débarrasser du standard et de la verbosité qui n’ajoutent aucune valeur est très utile, mais en revanche, en utilisant quelque chose comme Java ou C #, la connaissance des modèles de conception et des outils comme resharper vous permet une telle flexibilité dans la refactorisation du code. , nettoyer au fil du temps, décomposer des choses, etc., ce serait tout simplement beaucoup plus difficile si vous l'aviez écrit comme un script python ou une application ruby ​​beaucoup plus petit.

Une comparaison très révélatrice: je préférerais avoir 100 000 CdC de code C # découplé, couvert de tests, rempli de choses "excessives" comme un modèle de stratégie, des usines, etc., plutôt qu'une application 20k python qui "fait bien les choses". 5 fois plus de code ou pas, l'architecture gagne chaque jour.

Je suis tout à fait d’accord pour dire que certaines sortes de travail sont plus faciles et plus pratiques dans certaines langues, mais je crois plus dans le choix de votre langue en fonction des outils dont vous avez besoin et des exigences (et qui pourraient l’être dans un proche avenir).