Votre algorithme préféré et la leçon qu'il vous a apprise [fermé]

StackOverflow https://stackoverflow.com/questions/26301

  •  09-06-2019
  •  | 
  •  

Question

Quel algorithme vous a le plus appris sur la programmation ou sur une fonctionnalité spécifique du langage ?

Nous avons tous vécu ces moments où, tout d'un coup, nous savons, sachez simplement, que nous avons appris une leçon importante pour l'avenir basée sur la compréhension finale d'un algorithme écrit par un programmeur situé à quelques échelons de l'échelle de l'évolution.Quelles idées et quel code vous ont apporté la touche magique ?

Était-ce utile?

La solution

"Itérer est humain, récurer est divin" - cité en 1989 à l'université.

P.S.Publié par Woodgnome en attendant l'invitation à rejoindre

Autres conseils

Algorithmes généraux :

  • Le tri rapide (et son analyse de complexité moyenne) montre que la randomisation de votre entrée peut être une bonne chose ! ;
  • arbres équilibrés (Arbres AVL par exemple), une manière intéressante d'équilibrer les coûts de recherche/insertion ;
  • Dijkstra et Ford-Fulkerson des algorithmes sur des graphes (j'aime le fait que le second ait de nombreuses applications) ;
  • la famille d'algorithmes de compression LZ* (LZW par exemple), la compression des données me paraissait un peu magique jusqu'à ce que je la découvre (il y a longtemps :) );
  • le FFT, omniprésent (réutilisé dans tant d’autres algorithmes) ;
  • le simplexe algorithme, omniprésent également.

Liés aux chiffres :

  • Algorithme d'Euclide pour calculer le pgcd de deux entiers :l'un des premiers algorithmes, simple et élégant, puissant, comporte de nombreuses généralisations ;
  • multiplication rapide d'entiers (Cooley Tukey Par exemple);
  • Itérations de Newton pour inverser/trouver une racine, un méta-algorithme très puissant.

Concernant la théorie des nombres :

  • AGA-algorithmes liés (exemples) :conduit à des algorithmes très simples et élégants pour calculer pi (et bien plus encore !), bien que la théorie soit assez profonde (Gauss en a introduit des fonctions elliptiques et des formes modulaires, on peut donc dire qu'elle a donné naissance à la géométrie algébrique...) ;
  • le tamis à champ numérique (pour la factorisation entière): très compliqué, mais un résultat théorique assez sympa (cela vaut aussi pour le AK algorithme, qui a prouvé que PRIMES est dans P).

J'ai aussi aimé étudier l'informatique quantique (Court et Deutsch-Josza algorithmes par exemple) :cela vous apprend à sortir des sentiers battus.

Comme vous pouvez le voir, je suis un peu partisan des algorithmes orientés mathématiques :)

Algorithme des chemins les plus courts de Floyd-Warshall pour toutes les paires

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Voici pourquoi c'est cool :Lorsque vous découvrez pour la première fois le problème du chemin le plus court dans votre cours de théorie des graphes, vous commencez probablement par l'algorithme de Dijkstra qui résout célibataire-source le chemin le plus court.C'est assez compliqué au début, mais ensuite on s'en remet et on l'a bien compris.

Puis le professeur dit : « Maintenant, nous voulons résoudre le même problème, mais pour TOUS sources".Vous vous dites : « Oh mon Dieu, cela va être un problème beaucoup plus difficile ! Ça va être au moins N fois plus compliqué que l'algorithme de Dijkstra !!!".

Ensuite, le professeur vous donne Floyd-Warshall.Et votre esprit explose.Ensuite, vous commencez à pleurer devant la simplicité de l’algorithme.C'est juste une boucle triplement imbriquée.Il utilise uniquement un simple tableau pour sa structure de données.

La partie la plus révélatrice pour moi est la réalisation suivante :disons que vous avez une solution au problème A.Ensuite, vous avez un plus grand "superproblème" B qui contient le problème A.La solution au problème B peut en fait être plus simple que la solution au problème A.

Tri rapide.Cela m'a montré que la récursivité peut être puissante et utile.

Celui-ci peut paraître anodin mais ce fut une révélation pour moi à l’époque.J'étais dans mon tout premier cours de programmation (VB6) et le Prof venait de nous parler des nombres aléatoires et il m'a donné les instructions suivantes :"Créez une machine de loterie virtuelle.Imaginez une boule de verre remplie de 100 balles de ping-pong marquées de 0 à 99.Choisissez-les au hasard et affichez leur numéro jusqu'à ce qu'ils soient tous sélectionnés, sans doublon.

Tous les autres ont écrit leur programme comme ceci :Choisissez une balle, mettez son numéro dans une « liste déjà sélectionnée », puis choisissez une autre balle.Vérifiez si elle est déjà sélectionnée, si c'est le cas, choisissez une autre balle, sinon mettez son numéro sur la "liste déjà sélectionnée" etc....

Bien sûr, à la fin, ils faisaient des centaines de comparaisons pour trouver les quelques balles qui n'avaient pas encore été récupérées.C'était comme jeter les boules dans le bocal après les avoir sélectionnées.Ma révélation a été de jeter les balles après avoir choisi.

Je sais que cela semble incroyablement évident, mais c'est à ce moment-là que le « commutateur de programmation » s'est inversé dans ma tête.C’est à ce moment-là que la programmation est passée de l’apprentissage d’une langue étrangère étrange à la résolution d’un casse-tête amusant.Et une fois que j’ai établi ce lien mental entre la programmation et le plaisir, plus rien ne m’a arrêté.

Le codage Huffman serait le mien, j'avais initialement créé ma propre version stupide en minimisant le nombre de bits pour coder le texte de 8 à moins, mais je n'avais pas pensé au nombre variable de bits en fonction de la fréquence.Ensuite, j'ai découvert le codage de Huffman décrit dans un article d'un magazine et cela a ouvert de nombreuses nouvelles possibilités.

Algorithme de dessin au trait de Bresenham m'a intéressé au rendu graphique en temps réel.Cela peut être utilisé pour restituer des polygones remplis, comme des triangles, pour des choses comme le rendu de modèles 3D.

Analyse de descente récursive - Je me souviens avoir été très impressionné par la façon dont un code aussi simple pouvait réaliser quelque chose d'aussi apparemment complexe.

Tri rapide en Haskell :

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Même si je ne savais pas écrire Haskell à l'époque, j'ai compris ce code et avec lui la récursivité et l'algorithme de tri rapide.Il a juste fait un clic et c'était là...

L'algorithme itératif de Fibonacci, car pour moi il a mis en évidence le fait que le code le plus élégant (dans ce cas, la version récursive) n'est pas forcément le plus efficace.

Pour élaborer - L'approche "fib(10) = fib(9) + fib(8)" signifie que fib(9) sera évalué comme fib(8) + fib(7).Ainsi, l'évaluation de fib(8) (et donc fib7, fib6) sera toutes évaluée deux fois.

La méthode itérative (curr = prev1 + prev2 dans une boucle for) ne s'arbore pas de cette façon et ne prend pas autant de mémoire puisqu'il ne s'agit que de 3 variables transitoires, au lieu de n images dans la pile de récursion.

J'ai tendance à m'efforcer d'obtenir un code simple et élégant lorsque je programme, mais c'est l'algorithme qui m'a aidé à réaliser que ce n'est pas la fin de l'écriture de bons logiciels et qu'en fin de compte, les utilisateurs finaux ne le font pas. Je ne me soucie pas de l'apparence de votre code.

Pour une raison quelconque, j'aime le Transformation schwartzienne

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

Où foo($) représente une expression gourmande en calcul qui prend $ (chaque élément de la liste tour à tour) et produit la valeur correspondante qui doit être comparée en elle-même.

Minimax m'a appris que les programmes d'échecs ne sont pas intelligents, ils peuvent simplement penser à plus d'avancées que vous.

Je ne sais pas si cela peut être considéré comme un algorithme ou simplement comme un hack classique.Dans les deux cas, cela m’a aidé à commencer à sortir des sentiers battus.

Échangez 2 entiers sans utiliser de variable intermédiaire (en C++)

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

Tri rapide:Jusqu'à mon arrivée à l'université, je ne m'étais jamais demandé si la force brute Bubble Sort était le moyen de tri le plus efficace.Cela semblait intuitivement évident.Mais être exposé à des solutions non évidentes comme Quicksort m'a appris à regarder au-delà des solutions évidentes pour voir si quelque chose de mieux était disponible.

Pour moi, c'est l'algorithme de tri par tas faible car il montre (1) à quel point une structure de données judicieusement choisie (et les algorithmes qui y travaillent) peut influencer les performances et (2) que des choses fascinantes peuvent être découvertes même dans des applications anciennes et bien connues. des choses.(le tri en tas faible est la meilleure variante de tous les types de tas, qui a été éprouvé huit ans plus tard.)

C'est lent :)

J'ai beaucoup appris sur le C et les ordinateurs en général en comprenant Appareil Duffs et Échanges XOR

MODIFIER:

@Jason Z, c'est mon échange XOR :) cool n'est-ce pas.

Pour une raison quelconque, Bubble Sort m'a toujours marqué.Pas parce que c'est élégant ou bon, simplement parce qu'il avait un nom loufoque, je suppose.

je n'ai pas de préféré -- il y en a tellement de belles parmi lesquelles choisir -- mais celle que j'ai toujours trouvée intrigante est la Formule Bailey – Borwein – Plouffe (BBP), qui vous permet de calculer un chiffre arbitraire de pi sans connaître les chiffres précédents.

RSA m'a fait découvrir le monde de l'arithmétique modulaire, qui peut être utilisée pour résoudre un surprenant nombre de intéressant problèmes!

Ne m'a pas appris grand chose, mais le Algorithme Johnson-Trotter ne manque jamais de m'épater.

Diagrammes de décision binaire, bien que formellement il ne s'agisse pas d'un algorithme mais d'une structure de données, conduit à des solutions élégantes et minimales pour divers types de problèmes de logique (booléenne).Ils ont été inventés et développés pour minimiser le nombre de portes dans la conception des puces et peuvent être considérés comme l'un des fondements de la révolution du silicium.Les algorithmes résultants sont étonnamment simples.

Ce qu'ils m'ont appris :

  • une représentation compacte de n'importe lequel le problème est important ;petit est beau
  • un petit ensemble de contraintes/réductions appliquées de manière récursive peut être utilisé pour y parvenir
  • pour les problèmes de symétries, la transformation vers une forme canonique devrait être la première étape à considérer
  • tous les morceaux de littérature ne sont pas lus.Knuth a découvert les BDD plusieurs années après leur invention/introduction.(et j'ai passé presque un an à les enquêter)

Pour moi, le simple échange chez Kelly & Pohl's Un livre sur C faire la démonstration de l'appel par référence m'a fait flipper quand je l'ai vu pour la première fois.J'ai regardé cela et les pointeurs se sont mis en place.Textuellement...

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

Le Algorithme des tours de Hanoï est l'un des plus beaux algorithmes.Il montre comment utiliser la récursivité pour résoudre un problème d'une manière beaucoup plus élégante que la méthode itérative.

Alternativement, l'algorithme de récursivité pour les séries de Fibonacci et le calcul des puissances d'un nombre démontrent la situation inverse de l'algorithme récursif utilisé dans un souci de récursivité au lieu de fournir une bonne valeur.

L'algorithme itératif de Fibonacci, car pour moi il a mis en évidence le fait que le code le plus élégant (dans ce cas, la version récursive) n'est pas forcément le plus efficace.

La méthode itérative (curr = prev1 + prev2 dans une boucle for) ne s'arbore pas de cette façon et ne prend pas autant de mémoire puisqu'il ne s'agit que de 3 variables transitoires, au lieu de n images dans la pile de récursion.

Vous savez que Fibonacci a une solution sous forme fermée qui permet de calculer directement le résultat en un nombre fixe d'étapes, n'est-ce pas ?À savoir (phin - (1 - phi)n) / sqrt(5).Cela me semble toujours quelque peu remarquable que cela donne un nombre entier, mais c'est le cas.

phi est le nombre d'or, bien sûr ;(1 + carré (5)) / 2.

Un algorithme qui génère une liste de nombres premiers en comparant chaque nombre à la liste de nombres premiers actuelle, en l'ajoutant s'il n'est pas trouvé et en renvoyant la liste de nombres premiers à la fin.Stupéfiant à plusieurs égards, la moindre n'étant pas l'idée d'utiliser le résultat partiellement terminé comme critère de recherche principal.

Stocker deux pointeurs dans un seul mot pour une liste doublement chaînée m'a appris la leçon selon laquelle vous pouvez effectivement faire de très mauvaises choses en C (avec laquelle un GC conservateur aura beaucoup de problèmes).

Le plus fier que j'ai été d'une solution a été d'écrire quelque chose de très similaire au package DisplayTag.Cela m'a beaucoup appris sur la conception, la maintenabilité et la réutilisation du code.Je l'ai écrit bien avant DisplayTag, et il a été inscrit dans un accord NDA, je n'ai donc pas pu l'ouvrir en source, mais je peux toujours en parler avec enthousiasme lors des entretiens d'embauche.

Cartographier/Réduire.Deux concepts simples qui s'assemblent pour faciliter la parallélisation d'un grand nombre de tâches informatiques.

Oh...et ce n'est que la base de l'indexation massivement parallèle :

http://labs.google.com/papers/mapreduce.html

Pas mon préféré, mais le Algorithme de Miller Rabin car tester primality m'a montré qu'avoir raison presque tout le temps est suffisant presque tout le temps.(c'est à dire.Ne vous méfiez pas d'un algorithme probabiliste simplement parce qu'il a une probabilité de se tromper.)

@Krishna Kumar

La solution bit à bit est encore plus amusante que la solution récursive.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top