Quels algorithmes sont utilisés le plus souvent en pratique?

19

Quels algorithmes sont utilisés le plus souvent?

Veuillez écrire un seul algorithme par réponse, essayez de garder votre réponse courte (une ou deux lignes).

ds.algorithms big-list Kaveh
la source
Kaveh, vous devriez peut-être attendre les réponses avant d'en fournir autant? :)
Suresh Venkat
1
@Suresh: Désolé. :)
Kaveh
3
Le plus souvent dans quel sens? (Nombre de programmes informatiques différents qui mettent en œuvre l'algorithme? Nombre de logiciels installés qui utilisent l'algorithme? Nombre d'exécutions de l'algorithme? Quantité de données traitées en utilisant l'algorithme? Secondes CPU utilisées par l'algorithme?) Où? (Universités, industrie, ordinateurs personnels?) Est-il jamais possible d'estimer quelque chose comme ça; pouvons-nous avoir des données à l'appui de l'une des réponses?
Jukka Suomela
1
La question est trop vague comme l'a souligné Jukka Suomela. Sans plus de précisions, les réponses ne seront pas meilleures que la table des matières d'un manuel sur les algorithmes.
Tsuyoshi Ito
1
Il y a un livre récent: "Neuf algorithmes qui ont changé l'avenir: les idées ingénieuses qui animent les ordinateurs d'aujourd'hui" par John MacCormick. Voir press.princeton.edu/titles/9528.html
Alessandro Jacopson

Réponses:

18

La transformation de Fourier rapide est-elle le problème algorithmique résolu la plupart du temps par des systèmes informatiques réels? Il faut que ce soit proche. Je proposerais donc l' algorithme FFT de Cooley-Tukey .

Aaron Sterling
la source
I like this, FFT est surplombé dans l' enseignement des sciences informatiques de base, mais il est certainement un algorithme avec un impact énorme dans notre société moderne, et beaucoup de choses modernes qui nous entourent sont crissement FFT tout le temps.
Jukka Suomela
14

Multiplication.

Peut-être l'un des plus anciens algorithmes pas tout à fait triviaux, et un problème qui est résolu plus souvent que la FFT.

Jukka Suomela
la source
La multiplication n'est pas un algorithme, c'est un problème avec de nombreux sous-problèmes résolus par différents algorithmes: entier de taille fixe et virgule flottante, exécuté par du matériel ou un logiciel; bignums de taille variable (modulo ou non), matrices, ...
Gilles 'SO- arrête d'être diabolique'
Je faisais référence aux circuits de multiplication matérielle dans les processeurs modernes (pour les nombres entiers et à virgule flottante; ces deux ne sont pas si différents à la fin). Je crois comprendre qu'ils ont tendance à être "juste" des versions très intelligemment conçues de la même approche de base - l'algorithme de "multiplication longue", qui était déjà connu au Moyen Âge.
Jukka Suomela
Je pense que la soustraction (comparaison) est utilisée beaucoup plus souvent que la multiplication, et je ne vois aucune raison pour laquelle la multiplication compte comme un algorithme et l'addition / soustraction non. Cependant, je ne sais pas si cela peut être considéré comme une réponse.
Tsuyoshi Ito du
Oui, l'addition et la soustraction sont utilisées encore plus souvent que la multiplication - en effet, l'algorithme de multiplication longue réduit essentiellement une multiplication à une addition. Cependant, je ne sais pas s'il existe un seul algorithme d'addition / soustraction que nous pourrions proposer ici?
Jukka Suomela
@JukkaSuomela: L'addition et la soustraction de complément à deux seraient un bon candidat.
John Gietzen
13

Algorithmes de chemin le plus court de Dijkstra et Bellman-Ford . Il y a au moins 35 000 systèmes autonomes (AS) actifs sur Internet en 2010. Chaque AS exécute soit un protocole de routage à état de liaison (Dijkstra), soit un protocole de routage à vecteur de distance (Bellman-Ford). Les routeurs d'un AS mettent généralement à jour leurs tables périodiquement toutes les quelques minutes, par exemple 10.

Ainsi, le nombre d'exécutions de Dijkstra & Bellman-Ford par jour s'élève à au moins 5 millions. Et cela vient uniquement des routeurs.

Nous n'avons pas compté les calculs de chemin les plus courts à partir de Google Maps et les goûts qui devraient facilement représenter 10 fois plus. Un demi-milliard d'exécutions par jour n'est pas exagéré.

Hung Q. Ngo
la source
Un demi-milliard d'exécutions par jour peut sembler beaucoup, mais gardons à l'esprit que nous avons, par exemple, des milliards de téléphones portables sur cette planète. Que font ces choses tout le temps? Ou que font-ils lors de chaque appel téléphonique? Je ne sais pas, mais je suppose qu'ils font au moins beaucoup plus de FFT que les chemins les plus courts.
Jukka Suomela
8

Tri rapide

Kaveh
la source
14
Soit dit en passant, est-ce vraiment le cas que le tri rapide est l'algorithme de tri le plus utilisé dans le monde réel? J'ai jeté un coup d'œil à l'implémentation d'une fonction de "tri" à usage général dans certains langages de programmation couramment utilisés. Perl: semble être passé récemment de quicksort à mergesort. Python: utilise Timsort (hybride de tri par fusion / insertion). Java: anciennement mergesort, de nos jours Timsort. Les bases de données ont tendance à utiliser le tri externe. Le tri rapide est-il déjà une espèce en voie de disparition?
Jukka Suomela
Je pense que c'est un très bon point. Ce serait bien si quelqu'un pouvait modifier la réponse.
Juan Bermejo Vega
@Juan, bien que le point mentionné par Jukka soit correct, je ne vois aucune raison de modifier la réponse.
Kaveh
7

Je pense que l'algorithme le plus utilisé est Parity Check (ou peut-être CRC ou une sorte de code correcteur d'erreurs), car ils apparaissent dans chaque accès RAM.

Diego de Estrada
la source
Également utilisé au moins une fois pour chaque paquet envoyé sur n'importe quel réseau IP
Brochure Claus
5

Algorithme Simplex - n'est-ce pas encore compétitif avec les meilleures méthodes de point intérieur? Si c'est le cas, il doit être beaucoup utilisé.

Mugizi Rwebangira
la source
4

k

Plus généralement, vous devriez regarder les lauréats du prix Kanellakis pour des idées qui ont un poids théorique et pratique.

Suresh Venkat
la source
merci pour le lien, ça a l'air très intéressant. Une motivation partielle pour la question était de trouver un joli nom algorithmique accrocheur pour le site. :)
Kaveh
4

Correspondance d'expressions régulières par conversion en automates finis - je crois que grep fonctionne dans ce sens.

Neeldhara
la source
3

Il est difficile de penser à des algorithmes plus largement utilisés que ceux des implémentations modernes de TCP : évitement de la congestion , retransmission rapide . Bien que cela dépende de la façon dont on détermine ce qui répond aux critères d'un algorithme ...

Lev Reyzin
la source
Mais pouvez-vous vraiment utiliser les algorithmes TCP plus souvent que la FFT (qui figure déjà sur cette liste)? Si mon ordinateur envoie un seul paquet IP (TCP ou non), ne déclenche-t-il généralement pas tout un tas de calculs FFT? Habituellement, les paquets sont transmis à un moment donné en utilisant des technologies telles que le WLAN, l'ADSL et le GSM, et je pense que la plupart d'entre eux utilisent des modulations qui dépendent fortement de la FFT.
Jukka Suomela
Je pense que tu as raison.
Lev Reyzin
3

Élimination gaussienne Ceci est toujours utilisé dans la pratique, n'est-ce pas? Sinon, remplacez-le par ce qui est le plus souvent utilisé pour résoudre les systèmes linéaires ...

Mugizi Rwebangira
la source
2

SHA-1 (et les fonctions de hachage en général). Probablement mieux que la plupart des autres algorithmes en termes de nombre d'exécutions.

Hung Q. Ngo
la source
2

Des algorithmes liés à l'arbre B + sont utilisés pour les éléments de base de données

Prabu
la source
2

Algorithmes de planification. Ils sont utilisés par tous les appareils et serveurs utilisateurs du monde entier. Un certain nombre de variantes sont utilisées, j'ai trouvé beaucoup de références pour la "file d'attente de rétroaction à plusieurs niveaux"

chazisop
la source
1

Cette réponse interprète "le plus souvent" en termes de cycles CPU réels.

Lorsque j'apprenais l'informatique dans les années 70, je me souviens avoir lu que la grande majorité des cycles informatiques (lire: mainframe) étaient consacrés au tri. Les applications métier nécessitent un tri étendu pour l'analyse et le reporting. Je n'imagine pas que cela a beaucoup changé, mais bien sûr, la montée en puissance d'autres applications - e-mail, traitement de texte, etc. - a dû modifier le mélange. Ces tris sont généralement des tris stables (pas Quicksort) en raison de la nécessité de trier les successions de champs pour créer des sous-tris.

À strictement parler, cependant, l'algorithme le plus souvent utilisé est, sans aucun doute, tout ce qui est exécuté par le processus d'attente du système Windows lorsque rien d'autre ne se passe ;-).

Whuber
la source
1

Sprase Matrix Vector Multiply

... est le cheval de bataille informatique derrière la solution de presque tous les systèmes linéaires. En conséquence, il est exécuté chaque fois

  • Des scientifiques / ingénieurs résolvent des équations différentielles
  • Les statisticiens trouvent de nouvelles corrélations (ACP)
  • Google exécute un pagerank
  • Votre téléphone prédit votre position à partir du GPS, des accéléromètres et des emplacements des tours cellulaires
  • Votre voiture ajuste votre suspension en mouvement
  • etc....

La plupart des FLOP sur n'importe quel supercalculateur ou cluster sont dépensés à l'intérieur d'un mat-vec clairsemé.

MRocklin
la source
1

La méthode de Newton. Il est utilisé pour calculer les racines carrées, pour calculer la division. Il peut être utilisé pour effectuer une programmation linéaire. Plus généralement, c'est le cheval de bataille de l'optimisation (convexe). Il peut être utilisé pour résoudre des équations différentielles en physique en minimisant l'action / l'énergie.

Jules
la source
1

Hachage et arbres rouge-noir.

Ils sont déjà implémentés en STL (hash_map, map), et chaque programmeur sait qu'un tel conteneur est incroyablement pratique lorsque vous souhaitez stocker des informations indexées par un type de données arbitraire.

zotachidil
la source
0

Programmation dynamique .

Je pense que DP est utilisé "plus souvent" que les autres algorithmes cités dans l'enquête jusqu'à présent. Je déduis «plus souvent» dans le sens de la fréquence à laquelle un concept d'algorithme non trivial a été implémenté par le programmeur dans la vie réelle, plutôt que combien de fois une implémentation particulière d'un algorithme a été invoquée.

DP est polyvalent et a de nombreux visages. Parfois, je l'ai utilisé un peu inconsciemment, puis j'ai réalisé plus tard que je faisais du DP.

Bien sûr, il y a des choses qui sont encore plus courantes que Dynamic Program, mais ce sont principalement des structures de données (tableau, liste chaînée, hachage).

Hardy Leung
la source
7
C'est un peu différent des autres suggestions car c'est un paradigme de conception d'algorithme (similaire à gourmand ou primal-dual) et pas seulement un algorithme unique.
Jukka Suomela
0

String Matching, utilisé tout le temps dans les logiciels d'application et au niveau de la base de données.

Dans le cas exact, il existe plusieurs algorithmes assez impliqués (KMP, Boyer-Moore) dont certains atteignent un temps d'exécution sublinéaire attendu. Ils sont également intéressants à étudier d'un point de vue CS.

La correspondance approximative des chaînes, c'est-à-dire les alignements, est probablement encore plus intéressante. Vous connaissez les fonctionnalités de "correction automatique"? En outre, les recherches dans les données de chaîne bruyantes (par exemple, l'ADN) sont effectuées à l'aide d'alignements.

Raphael
la source