Quelles sont les raisons pour apprendre différents algorithmes / structures de données servant le même objectif?

92

Je me pose des questions sur cette question depuis que je suis étudiant de premier cycle. C'est une question générale mais je développerai avec des exemples ci-dessous.

J'ai vu beaucoup d'algorithmes - par exemple, pour des problèmes de flux maximum, je connais environ 3 algorithmes qui peuvent résoudre le problème: Ford-Fulkerson, Edmonds-Karp & Dinic, avec Dinic ayant la meilleure complexité.

Pour les structures de données - par exemple, les tas -, il existe des tas binaires, des tas binomiaux et des tas de Fibonacci, le tas de Fibonacci présentant la meilleure complexité globale.

Ce qui me laisse perplexe: existe-t-il des raisons pour lesquelles nous devons toutes les connaître? Pourquoi ne pas simplement apprendre et se familiariser avec la meilleure complexité?

Je sais que c'est le meilleur si nous les connaissons tous. Je veux juste savoir s'il existe des raisons "plus valables", comme certains problèmes / algorithmes ne peuvent être résolus qu'en utilisant A mais pas B , etc.

Shole
la source
17
Comme je le dis toujours: ceux-ci (généralement) ne sont pas "meilleurs". Une fois que vous définissez explicitement ce que vous entendez par «meilleur», la réponse devient évidente.
Raphaël
2
C'est une bonne question, mais elle évoque ce que je considérerais comme un trou dans votre éducation que vous pourriez envisager de corriger. C’est une expérience pratique. Si vous n’aviez pas écrit ces algorithmes au cours de votre formation, vous pourriez envisager de les écrire maintenant. Je suppose que la réponse à cette question serait rapidement devenue évidente si vous tentiez de trouver des utilisations pour ces algorithmes.
Sam
@Sam D'après mon expérience, ce que je pensais, c'est que dans les conférences, ou dans certains manuels, ils sont informatifs, introduisent de nombreux algorithmes, analyses, etc. genre d’algorithmes de A à Z, et quelques problèmes de devoirs, mais pour moi ils peuvent tous être résolus par A seulement, ou par Z seulement, etc., d’où la question posée.
Shole
5
Si vous insistez pour laisser de côté les intérêts académiques, la meilleure raison pratique d’apprendre des algorithmes non optimaux est de les reconnaître et de les optimiser en les remaniant au maximum. Vous ne pouvez pas transformer un arc en arme en arme si vous ne savez pas à quoi servent un arc et une flèche.
candied_orange
1
Nous avons en fait proposé un site StackExchange spécialement conçu pour répondre aux questions d’éducation CS telles que celle-ci. Venez nous soutenir ici: area51.stackexchange.com/proposals/92460/…
vk2015

Réponses:

121

Il y a un manuel qui doit être écrit à un moment donné, avec le titre de travail Structures de données, algorithmes et compromis . Presque tous les algorithmes ou structures de données que vous êtes susceptible d'apprendre au premier cycle possèdent certaines fonctionnalités qui le rendent meilleur pour certaines applications que pour d'autres.

Prenons l'exemple du tri puisque tout le monde connaît les algorithmes de tri standard.

Tout d'abord, la complexité n'est pas le seul souci. En pratique, les facteurs constants sont importants, raison pour laquelle (par exemple) le tri rapide a tendance à être utilisé davantage que le tri en tas, même si le tri rapide a une terrible complexité dans le pire des cas.

O(nlogn)

Dans d'autres cas, les idées d'un algorithme ou d'une structure de données peuvent être applicables à un problème spécifique. Le tri à bulles semble toujours plus lent que le type à insertion sur du matériel réel, mais l’idée de réaliser une passe à bulles est parfois exactement ce dont vous avez besoin.

Prenons, par exemple, une sorte de visualisation 3D ou de jeu vidéo sur une carte vidéo moderne, dans laquelle vous souhaitez dessiner des objets dans l’ordre le plus proche de l’appareil photo, pour des raisons de performances, mais si vous ne recevez pas la commande exacte, le matériel s'en chargera. Si vous vous déplacez dans l'environnement 3D, l'ordre relatif des objets ne changera pas beaucoup d'une image à l'autre. Par conséquent, le passage d'une bulle à chaque image peut constituer un compromis raisonnable. (Le moteur Source de Valve le fait pour les effets de particules.)

Il existe persistance, concurrence, localisation du cache, évolutivité sur un cluster / nuage et une foule d'autres raisons possibles pour lesquelles une structure de données ou un algorithme peut être plus approprié qu'un autre, même avec la même complexité de calcul pour les opérations qui vous intéressent.

Cela dit, cela ne signifie pas que vous devez mémoriser un tas d’algorithmes et de structures de données au cas où. La majeure partie de la bataille consiste à réaliser qu’il ya un compromis à exploiter en premier lieu, et à savoir où chercher si vous pensez qu’il pourrait y avoir quelque chose d’approprié.

Pseudonyme
la source
7
Grande réponse avec d'excellents exemples! Je ne savais même pas que l'utilisation d'une bulle passait dans le monde réel ...
shole
1
@shole Je n'ai pas beaucoup d'expérience dans le secteur des jeux, mais tout ce qui précède est important à des degrés divers. (Évidemment, le type d'algorithmes, de structures de données et de mathématiques dont vous avez besoin pour les jeux est probablement différent de celui requis pour les bases de données, la bioinformatique ou ce que vous avez.) Si j'étais vous, j'irais ici et je commencerais à regarder: handmadehero. org en outre , il peut être utile de tapi sur gamedev.stackexchange.com
Pseudonym
1
L’efficacité du cache est un facteur important qui fait l’objet de nombreuses recherches ("mur de mémoire" sur Google).
Raphaël
6
Attention, Quicksort est en moyenne beaucoup plus rapide que Heapsort, mais Heapsort est plus cohérent (la variance du temps d'exécution est moindre, et le pire des cas est bien meilleur). Et le fait que Heapsort saute dans le tableau par rapport aux balayages linéaires à gauche et à droite de Quicksort fait une énorme différence une fois que le cache / la pagination entrent en jeu.
vonbrand
1
@shole Quel type de développement de jeu vous intéresse? Il y a au moins deux sous-champs très différents, les graphiques 3D et le gameplay (qui inclut l'IA). Je ne connais que les graphiques, mais je peux dire que les structures de données et les mathématiques sont extrêmement importantes dans les graphiques, ainsi que dans une moindre mesure les algorithmes. Si vous utilisez un moteur, la plupart de ces éléments seront bien sûr pris en charge, mais vous devez tout de même comprendre les mathématiques de base de la géométrie 3D.
Gardenhead
51

Outre le fait qu'il existe une myriade de mesures de coûts (durée d'exécution, utilisation de la mémoire, erreurs de cache, erreurs de prédiction de branche, complexité d'implémentation, possibilité de vérification ...) sur des myriades de modèles de machines (TM, RAM, PRAM, ...) Dans l’éventualité où les considérations d’amortissement sont à prendre en compte, il existe souvent des différences fonctionnelles allant au-delà de la portée de la spécification de base du manuel.

Quelques exemples:

  • Mergesort est stable, contrairement à Quicksort.
  • Les arbres de recherche binaires vous donnent l'itération dans l'ordre, pas les hashtables.
  • Bellman-Ford peut faire face aux poids négatifs, Dijkstra ne le peut pas.

Il y a aussi des considérations didactiques à faire:

  • Est-il facile de comprendre une solution plus complexe avant des solutions plus simples? (Arbres AVL (et leur analyse) sans BST; Dinic sans Ford-Fulkerson; ...)
  • Voyez-vous les mêmes principes et modèles lorsque vous êtes exposé à une seule solution par problème par rapport à de nombreuses solutions?
  • L'exposition à une seule solution par problème offre-t-elle une formation suffisante (vers la maîtrise)?
  • Devez-vous connaître l’ampleur des solutions trouvées (afin de vous empêcher de réinventer la roue encore et encore¹)?
  • Comprenez-vous d'autres solutions que l'on trouve dans la nature (par exemple, dans une bibliothèque de programmation en situation réelle), lorsque vous ne découvrirez qu'une solution par problème?

  1. C'est quelque chose que nous voyons beaucoup de types de programmeurs qui ne disposent pas d'une riche boîte à outils CS.
Raphaël
la source
4
+1 pour inclure des raisonnements didactiques! En relation avec plusieurs des raisonnements (en particulier les deuxième et troisième), voir comment les algorithmes et les structures de données sont développés et optimisés enseigne des techniques de développement et d’optimisation et une compréhension des compromis (apprendre non seulement "quoi" mais aussi "comment" et "pourquoi" ).
Paul A. Clayton
2
Une autre considération est que l' analyse des différentes alternatives offre des exemples d'outils utiles pour analyser de nouveaux algorithmes pour des paramètres peut-être inhabituels.
vonbrand
1
Bon point, @vonbrand. L'analyse de la complexité amortie a été inventée pour comprendre le comportement des arbres évasés, mais ces derniers sont rarement utilisés dans la pratique. Bien, pas les arbres évasés tels que publiés, en tout cas. Le noyau Windows NT utilise de manière célèbre des arborescences splay pour implémenter des mappes de mémoire virtuelle, mais il ne réorganise pas chaque recherche.
Pseudonyme le
1
@vonbrand Oui. Je comprendrais cependant que quelqu'un qui s'intéresse principalement à la dimension boîte à outils d'une classe d'algorithmes se moque de cette raison.
Raphaël
7

Dans le monde réel , il est probable que vous travailliez sur un logiciel conçu par une équipe composée d'autres personnes. Certains de ces logiciels auront été écrits avant votre naissance!

Afin de comprendre les algorithmes / structures de données utilisés, il est très utile de connaître un grand nombre d’algorithmes / structures de données, y compris des options qui ne sont plus considérées comme «à la pointe de la technologie».

Vous devrez également travailler sur des algorithmes non standard et utilisés uniquement dans l'application sur laquelle vous travaillez. Lorsque vous devrez améliorer ces algorithmes, vous constaterez que votre cerveau est rempli de méthodes utiles pour améliorer les algorithmes, tout en étudiant comment d'autres personnes ont amélioré les algorithmes.

C'est ce qui distingue quelqu'un qui a étudié l'informatique de quelqu'un qui vient d'apprendre à programmer. Dans la plupart des emplois dans lesquels j'ai travaillé, il m'est déjà arrivé d'étudier l'informatique, mais je pouvais résoudre un problème qu'un programmeur «savant apprendre du livre» ne pourrait pas, mais 95% du temps où j'ai découvert que l'initiation à l'informatique ne me donnait aucun avantage. sur d'autres programmeurs expérimentés .

Ian Ringrose
la source
À moins que 95% des problèmes que vous tentez de résoudre soient liés à l'apprentissage automatique. Je ne vois pas comment un programmeur normal peut même avoir la bonne occasion de s’attaquer aux problèmes rencontrés par de vrais problèmes de ML.
Pinocchio
3
Objectif: trouver un emploi avec un meilleur taux que 5%.
Raphaël
N'oubliez pas qu'étudier la CS était un excellent moyen de rassembler des connaissances sur les algorithmes et les structures de données. Le codage est la meilleure occupation - pour les codeurs.
Greybeard
5

Beaucoup de gens ont à juste titre mentionné qu'il n'y avait souvent pas le meilleur algorithme - cela dépend de la situation.

Il est également possible qu'un jour, vous rencontriez une situation inconnue. Plus vous connaissez d'algorithmes, plus vous avez de chances d'en connaître un qui constitue presque une solution que vous pouvez utiliser comme base.

Bloke Down Le Pub
la source
5
Cette réponse ne fait que répéter les points des plus anciens.
Raphaël
1

Beaucoup de bonnes réponses, juste quelque chose qui me manque, même si la réponse de Raphaël le dit un peu.

La facilité de mise en œuvre doit également être prise en compte.
Ce n'est généralement pas un problème avec les algorithmes de tri, car la plupart des plateformes / langages en ont déjà un implémenté (et souvent mieux que ce que vous pourriez faire), mais des algorithmes plus inhabituels pourraient ne pas être disponibles.
Selon votre problème, vous n'aurez peut-être pas besoin du meilleur algorithme absolu si le délai de mise en œuvre est de 1 jour contre 2 semaines.

Leherenn
la source