Welche Algorithmen werden in der Praxis am häufigsten verwendet?

19

Welche Algorithmen werden am häufigsten verwendet?

Bitte schreiben Sie einen Algorithmus pro Antwort und versuchen Sie, Ihre Antwort kurz zu halten (ein oder zwei Zeilen).

ds.algorithms big-list Kaveh
quelle
Kaveh, vielleicht solltest du auf Antworten warten, bevor du so viele lieferst? :)
Suresh Venkat
1
@Suresh: Tut mir Leid. :)
Kaveh
3
Am häufigsten in welchem Sinne? (Anzahl der verschiedenen Computerprogramme , die den Algorithmus? Anzahl der installierten Teile der Software implementieren , die den Algorithmus? Anzahl der Ausführungen des Algorithmus verwenden? Menge der verarbeiteten Daten durch den Algorithmus? CPU - Sekunden unter Verwendung durch den Algorithmus verwendet?) Wo? (Wissenschaft, Industrie, Heim-PCs?) Ist es jemals möglich, so etwas einzuschätzen? Können wir jemals irgendwelche Daten haben, um eine der Antworten zu stützen?
Jukka Suomela
1
Die Frage ist zu vage, wie Jukka Suomela betonte. Ohne weitere Klarstellung sind die Antworten nicht besser als das Inhaltsverzeichnis eines Lehrbuchs über Algorithmen.
Tsuyoshi Ito
1
Es gibt ein neues Buch: „Neun Algorithmen, die die Zukunft geändert: Das Geniale Ideen , die Antriebs Heutige Computer“ von John MacCormick. Siehe press.princeton.edu/titles/9528.html
Alessandro Jacopson

Antworten:

18

Ist die schnelle Fourier-Transformation das algorithmische Problem, das von realen Computersystemen am häufigsten pro Tag gelöst wird? Es muss nah sein. Also würde ich den Cooley-Tukey-FFT-Algorithmus nominieren .

Aaron Sterling
quelle
Ich mag das, FFT wird in der Informatik-Grundausbildung übersehen, aber es ist zweifellos ein Algorithmus mit enormen Auswirkungen auf unsere moderne Gesellschaft, und viele moderne Dinge um uns herum zermahlen ständig die FFT.
Jukka Suomela
14

Multiplikation.

Vielleicht ist einer der ältesten nicht-ganz-trivialen Algorithmen, und ein Problem, das häufiger als FFT gelöst.

Jukka Suomela
quelle
Die Multiplikation ist kein Algorithmus, sondern ein Problem mit vielen Teilproblemen, die durch verschiedene Algorithmen gelöst werden: Feste Ganzzahlen und Gleitkommazahlen, die von Hardware oder Software ausgeführt werden. Bignums variabler Größe (modulo oder nicht), Matrizen, ...
Gilles 'SO - hör auf, böse zu sein'
Ich bezog sich auf die Hardware-Multiplikationsschaltungen in modernen CPUs (für ganze Zahlen und Gleitkommazahlen, diese beiden sind nicht so anders am Ende). Mein Verständnis ist , dass sie neigen dazu , „nur“ sehr geschickt konstruierte Versionen des gleichen grundlegenden Ansatzes zu sein - der „lange Multiplikation“ Algorithmus, der bereits im Mittelalter bekannt war.
Jukka Suomela
Ich denke , dass Subtraktion (Vergleich) viel häufiger verwendet wird als Multiplikation, und ich kann keinen Grund sehen , warum Multiplikation zählt als Algorithmus und Addition / Subtraktion nicht. Ich weiß jedoch nicht, ob dies als Antwort geeignet ist.
Tsuyoshi Ito
Ja, Addition und Subtraktion werden noch häufiger verwendet als Multiplikation - tatsächlich reduziert der Algorithmus für lange Multiplikationen eine Multiplikation im Wesentlichen auf eine Addition. Ich weiß jedoch nicht, ob es einen einzelnen Additions- / Subtraktionsalgorithmus gibt, den wir hier vorschlagen könnten.
Jukka Suomela
@JukkaSuomela: Zweieraddition und -subtraktion wären ein guter Kandidat.
John Gietzen
13

Dijkstra und Bellman-Ford kürzesten Weg Algorithmen. Im Internet sind ab 2010 mindestens 35.000 autonome Systeme (AS) aktiv. Auf jedem AS wird entweder ein Verbindungsstatus-Routing-Protokoll (Dijkstra) oder ein Entfernungsvektor-Routing-Protokoll (Bellman-Ford) ausgeführt. Die Router innerhalb eines AS aktualisieren normalerweise ihre Tabellen regelmäßig alle paar Minuten, z. B. 10.

Die Anzahl der Hinrichtungen von Dijkstra & Bellman-Ford pro Tag beträgt also mindestens 5 Millionen. Und das ist nur von den Routern.

Wir haben nicht kürzesten Weg Berechnungen von Google Maps und die Gleichen gezählt, die 10-mal so viele leicht bilanzieren soll. Eine halbe Milliarde Hinrichtungen pro Tag ist nicht weit hergeholt.

Hung Q. Ngo
quelle
Eine halbe Milliarde Hinrichtungen pro Tag mögen sich nach viel anhören, aber denken wir daran, dass wir zum Beispiel Milliarden von Mobiltelefonen auf diesem Planeten haben. Was machen diese Dinger die ganze Zeit? Oder was machen sie bei jedem Telefonat? Ich weiß es nicht, aber ich vermute, dass sie zumindest viel mehr FFT machen als die kürzesten Wege.
Jukka Suomela
8

Schnelle Sorte

Kaveh
quelle
14
Ist es übrigens wirklich so, dass Quicksort der in der realen Welt am häufigsten verwendete Sortieralgorithmus ist? Ich habe mir kurz die Implementierung einer allgemeinen "Sortier" -Funktion in einigen häufig verwendeten Programmiersprachen angesehen. Perl: scheint in letzter Zeit von Quicksort zu Mergesort gewechselt zu sein. Python: verwendet Timsort (Mergesort / Insertion Sort Hybrid). Java: war früher Mergesort, heute Timsort. Datenbanken verwenden in der Regel eine externe Sortierung. Ist Quicksort bereits eine gefährdete Art?
Jukka Suomela
Ich denke, das ist ein sehr guter Punkt. Es wäre toll, wenn jemand die Antwort bearbeiten könnte.
Juan Bermejo Vega
@Juan, obwohl der von Jukka erwähnte Punkt korrekt ist, sehe ich keinen Grund, die Antwort zu bearbeiten.
Kaveh
7

Ich denke, der am häufigsten verwendete Algorithmus ist Parity Check (oder vielleicht CRC oder eine Art fehlerkorrigierender Code), weil sie in jedem RAM-Zugriff erscheinen.

Diego de Estrada
quelle
Wird auch mindestens einmal für jedes Paket verwendet, das über ein IP-basiertes Netzwerk gesendet wird
Claus Broch,
5

Simplex-Algorithmus - ist dies nicht immer noch konkurrenzfähig mit den besten Innenpunktmethoden? Wenn ja, muss es viel benutzt werden.

Mugizi Rwebangira
quelle
4

k bedeutet. .

Im Allgemeinen sollten Sie sich die Kanellakis-Preisträger ansehen, um Ideen mit theoretischem und praktischem Gewicht zu erhalten.

Suresh Venkat
quelle
danke für den link, es sieht sehr interessant aus. Teilweise motiviert für die Frage war es, einen schönen eingängigen algorithmischen Namen für die Site zu finden. :)
Kaveh
4

Anpassung regulärer Ausdrücke durch Konvertierung in endliche Automaten - ich glaube, grep funktioniert in diesem Sinne.

Neeldhara
quelle
3

Tiefensuche (DFS)

Kaveh
quelle
3

Es ist schwer, sich weiter verbreitete Algorithmen als jene in modernen Implementierungen von TCP vorzustellen : dh Vermeidung von Überlastungen , schnelle Neuübertragung . Das hängt jedoch davon ab, wie man bestimmt, was die Kriterien für einen Algorithmus erfüllt ...

Lev Reyzin
quelle
Aber können Sie TCP-Algorithmen wirklich öfter verwenden als FFT (was bereits auf dieser Liste steht)? Wenn mein Computer ein einzelnes IP-Paket sendet (TCP oder nicht), löst er dann normalerweise eine ganze Reihe von FFT-Berechnungen aus? Normalerweise werden die Pakete irgendwann mithilfe von Technologien wie WLAN, ADSL und GSM übertragen, und ich denke, die meisten von ihnen verwenden Modulationen, die stark von FFT abhängen.
Jukka Suomela
Ich denke, du hast recht.
Lev Reyzin
3

Gaußsche Eliminierung Wird in der Praxis immer noch verwendet, oder? Wenn nicht durch das ersetzen, was am häufigsten zur Lösung linearer Systeme verwendet wird ...

Mugizi Rwebangira
quelle
2

SHA-1 (und Hash-Funktionen im Allgemeinen). Wahrscheinlich schlagen die meisten anderen Algorithmen in Bezug auf die Anzahl der Ausführungen.

Hung Q. Ngo
quelle
2

B + tree-bezogene Algorithmen werden für die Datenbankinhalte verwendet

Prabu
quelle
2

Scheduling-Algorithmen. Sie werden von jedem Benutzergerät und Server weltweit verwendet. Es wird eine Reihe von Variationen verwendet. Ich habe viele Referenzen für "Mehrebenen-Feedback-Warteschlange" gefunden.

Chazisop
quelle
1

Diese Antwort wird "am häufigsten" in Bezug auf die tatsächlichen CPU-Zyklen interpretiert.

Als ich in den 70er Jahren Computer lernte, habe ich gelesen, dass die überwiegende Mehrheit der Computerzyklen (read: mainframe) dem Sortieren gewidmet war. Geschäftsanwendungen erfordern eine umfassende Sortierung für Analyse und Berichterstellung. Ich kann mir nicht vorstellen, dass sich das sehr geändert hat, aber natürlich muss der Aufstieg anderer Apps - E-Mail, Textverarbeitung usw. - die Mischung verändert haben. Diese Sortierungen sind normalerweise stabile Sortierungen (keine Quicksort-Sortierungen), da zum Erstellen von Subsortierungen nach Feldfolgen sortiert werden muss.

Streng genommen ist der am häufigsten verwendete Algorithmus ohne Zweifel, was auch immer vom Windows-Systemwartevorgang ausgeführt wird, wenn nichts anderes läuft ;-).

whuber
quelle
1

Sprase-Matrix-Vektor multiplizieren

... ist das rechnerische Arbeitstier hinter der Lösung nahezu aller linearen Systeme. Infolgedessen wird es ausgeführt, wann immer

  • Wissenschaftler / Ingenieure lösen Differentialgleichungen
  • Statistiker finden neue Korrelationen (PCA)
  • Google führt einen PageRank aus
  • Ihr Telefon sagt Ihren Standort anhand von GPS, Beschleunigungsmessern und Mobilfunkstandorten voraus
  • Ihr Auto passt Ihre Federung in Bewegung an
  • etc....

Die meisten FLOPs eines Supercomputers oder Clusters befinden sich in einem spärlichen mat-vec.

MRocklin
quelle
1

Newtons Methode. Es wird für die Berechnung von Quadratwurzeln und für die Berechnung von Divisionen verwendet. Es kann zur linearen Programmierung verwendet werden. Im Allgemeinen ist es das Arbeitspferd der (konvexen) Optimierung. Es kann verwendet werden, um Differentialgleichungen in der Physik zu lösen, indem die Aktion / Energie minimiert wird.

Jules
quelle
1

Hashing und rot-schwarze Bäume.

Sie sind bereits in STL (hash_map, map) implementiert, und jeder Programmierer weiß, dass ein solcher Container unglaublich praktisch ist, wenn Sie Informationen speichern möchten, die von einem beliebigen Datentyp indiziert wurden.

zotachidil
quelle
0

Dynamische Programmierung .

Ich denke, dass DP "häufiger" verwendet wird als andere Algorithmen, die bisher in der Umfrage genannt wurden. Ich schließe "öfter" in dem Sinne, wie oft ein nicht-triviales Algorithmuskonzept vom Programmierer im wirklichen Leben implementiert wurde, anstatt wie oft eine bestimmte Implementierung eines Algorithmus aufgerufen wurde.

DP ist vielseitig und hat viele Gesichter. Manchmal habe ich es etwas unbewusst benutzt und später festgestellt, dass ich DP mache.

Natürlich gibt es Dinge, die noch häufiger vorkommen als Dynamic Program, aber es handelt sich meistens um Datenstrukturen (Array, verknüpfte Liste, Hash).

Hardy Leung
quelle
7
Dies unterscheidet sich ein wenig von den anderen Vorschlägen, da es sich um ein Algorithmus-Design-Paradigma handelt (ähnlich wie gierig oder primär-dual) und nicht nur um einen einzelnen Algorithmus.
Jukka Suomela
0

String Matching, wird ständig in der Anwendungssoftware und auf Datenbankebene verwendet.

Im genauen Fall gibt es mehrere ziemlich komplizierte Algorithmen (KMP, Boyer-Moore), von denen einige eine sublineare erwartete Laufzeit erreichen. Sie sind auch aus CS-Sicht interessant zu studieren.

Noch interessanter ist wahrscheinlich die ungefähre Zeichenfolgenübereinstimmung, d. H. Die Ausrichtung. Sie wissen, „autocorrecting“ Funktionen? Auch die Suche in verrauschten String-Daten (z. B. DNA) erfolgt mithilfe von Alignments.

Raphael
quelle