Je passais en revue mes notes et suis tombé sur l'application de différents algorithmes de tri.
Alors que je tentais de comprendre l’implémentation de QuickSort et MergeSort, je me suis rendu compte que, bien que je fasse de la programmation pour gagner ma vie et que je me considère décent dans ce que je fais, je n’ai ni la mémoire photographique ni le courage de mettre en œuvre ces algorithmes sans s'appuyant sur mes notes. Tout ce dont je me souvenais, c’est que certains de ces algorithmes sont stables et d’autres pas. Certains prennent le temps de compléter O (nlog (n)) ou O (n ^ 2). Certains utilisent plus de mémoire que d'autres ...
J'aurais l'impression de ne pas mériter ce genre de travail si ce n'était pas le cas, car mon poste n'exige pas que j'utilise un algorithme de tri autre que ceux que l'on trouve dans les API standard. Je veux dire, combien d’entre vous occupent un poste en programmation où il est essentiel de pouvoir se souvenir de ce genre de choses ou de les inventer par vous-même?
la source
Réponses:
Demandons à Albert et voyons ce qu'il a à dire à ce sujet:
Amen, frère Albert, Amen.
Une fois que vous avez fait une bonne analyse des algorithmes essentiels dans une discipline donnée (sorte, recherche, peu importe), vous pouvez alors oublier les détails de la mise en oeuvre jusqu'à ce que vous ayez réellement besoin de l'algo. Dans ce cas, vous allez le rechercher bibliothèque préexistante Il y a 25 ans, j'ai construit un système de recherche majeur utilisant des arbres B *, mais aujourd'hui, il me faudrait RTFM pour bien les utiliser.
la source
O(n log n)
, mais si vous avez beaucoup de données manquantes dans la mémoire cache ou (que Dieu nous en préserve), vous frappez le disque, cen log n
ne sera qu'un bon souvenir.Ce n'est pas vraiment une question de mémorisation. Il s’agit de comprendre en profondeur des classes générales d’algorithmes tels que diviser pour régner. Si vous comprenez vraiment diviser pour régner, vous n'avez pas besoin de mémoriser le tri rapide. Vous pouvez le dériver sur place au besoin. En outre, le véritable avantage n'est même pas de pouvoir récupérer rapidement un tri rapide, mais bien de savoir quand un nouveau problème peut être résolu par une solution de division.
Tous les travaux de programmation ne sont pas identiques. Certains emplois nécessitent une connaissance approfondie des algorithmes, certains ont besoin de personnes qui comprennent la théorie des types, et d'autres simplement de personnes capables de récupérer des données dans un formulaire Web et de les transférer dans une base de données. Certains emplois ont même besoin de toutes ces compétences à la fois. Quel genre de travail voulez-vous travailler?
la source
Je pense que le seul moment où vous devez vous rappeler de tout cela est lorsque vous postulez pour un emploi, lorsque vous devez trouver des réponses sur-le-champ et ne pas disposer de ressources extérieures.
Des collègues ont réécrit QuickSort et ainsi de suite, mais je leur répète de revenir à l’utilisation des fonctions de tri intégrées au langage. Je sais que, selon le type de projet sur lequel nous travaillons, nous devons garder en mémoire d’autres algorithmes, car ils ne sont généralement pas inclus dans les bibliothèques standard, mais le tri n’est pas celui qui est utilisé car il est généralement intégré au langage.
Cependant, lorsque nous devons nous souvenir de ces algorithmes, nous nous tournons généralement vers Google ou un livre, qui ne recherche généralement pas une implémentation spécifique, mais plutôt celle qui convient le mieux à notre problème.
la source
Se rappeler quel algorithme est utile dans quels scénarios serait largement suffisant pour vous aider pendant votre travail. En fait, la plupart des tâches de programmation ne nécessitent pas de mémorisation d'approche, mais s'intéressent plutôt à votre façon de reconnaître le modèle algorithmique face au problème .
En fait, il existe une abondance d'informations dans la plupart des blogs / articles de programmation sur des sujets relatifs aux algorithmes. Ainsi, la mémorisation d'une mise en œuvre exacte n'a pas d'importance. L'information la plus précieuse serait de se faire une idée de base sur le type d'algorithme disponible et sur le problème spécifique qu'il est capable de résoudre . Rechercher une mise en œuvre exacte une fois que vous savez ce que vous recherchez est assez rapide.
En résumé, il est toujours préférable de savoir ce que vous recherchez et où sont les références - qui vous guideront vers la source.
la source
La mise en œuvre exacte n'est pas très importante. Mais le principe de mergesort / quicksort - la récursivité, le partitionnement, etc., est très basique et doit être compris par tous les programmeurs. Une fois que vous avez compris, ces algorithmes sont très simples à décrire en mots.
Ce n'est pas vraiment un problème de savoir si vous pouvez le rechercher ou si vous pouvez le rechercher sur Google, mais bien si le programmeur comprend ces techniques de résolution de problèmes et est capable de l'appliquer à d'autres situations.
la source
Je suis de deux avis sur ce sujet. Je connais beaucoup de programmeurs qui ne savent pas ce qu'est un algorithme de tri, mais font assez bien leur travail. Je crois aussi à la compréhension des principes afin de vraiment comprendre le domaine.
Il est difficile pour moi d’avoir une réponse impartiale à ce sujet car je programme depuis si longtemps que j’ai probablement oublié plus d’algorithmes que je connais actuellement - mais je connais toujours ceux de tri mentionnés dans cette question. Je pense que les leaders d'opinion d'Agile (par exemple, Ron Jeffries et Alistair Cockburn) ont de bonnes idées proches de cette idée (par exemple, Shu-Ha-Ri).
En résumé, voici la réponse difficile: utilisez l'API (le NIH est un signe d'immaturité du développeur), mais comprenez toujours les principes sous-jacents. J'espère que ça aide.
la source
Trier et rechercher sont incroyablement importants, que vous soyez un fan de Donald Knuth ou que vous souhaitiez être le prochain Larry Page. En fonction de votre activité et du niveau de concurrence que vous pouvez maîtriser parmi vos candidats, je vous recommanderais d'inclure certains des concepts suivants dans l'entretien.
Tri
Recherche
Certains pourraient dire que requérir le code pour ces algorithmes est excessif sauf si le travail est sur une île déserte sans connexion Internet. Une autre considération est que, si vous disposez de 30 minutes et que vous souhaitez poser des questions à propos de quelque chose d'autre, la mise en œuvre de ce type pourrait prendre beaucoup de temps pour de nombreux candidats.
la source