Welche Algorithmen / Datenstrukturen soll ich „erkennen“ und namentlich kennen? [geschlossen]

69

Ich würde mich gerne als einen ziemlich erfahrenen Programmierer bezeichnen. Ich programmiere jetzt seit über 5 Jahren. Mein Schwachpunkt ist jedoch die Terminologie. Da ich Autodidakt bin, kenne ich einige der formaleren Aspekte der Informatik nicht, obwohl ich programmieren kann. Was sind also praktische Algorithmen / Datenstrukturen, die ich anhand des Namens erkennen und kennen könnte?

Hinweis: Ich bitte nicht um eine Buchempfehlung zur Implementierung von Algorithmen. Die Implementierung ist mir egal, ich möchte nur erkennen können, wann ein Algorithmus / eine Datenstruktur eine gute Lösung für ein Problem darstellt. Ich bitte mehr um eine Liste von Algorithmen / Datenstrukturen, die ich "erkennen" sollte. Zum Beispiel kenne ich die Lösung für ein Problem wie dieses:

Sie verwalten eine Reihe von Schließfächern mit der Bezeichnung 0-999. Die Leute kommen zu Ihnen, um das Schließfach zu mieten, und kommen dann zurück, um den Schließfachschlüssel zurückzugeben. Wie würden Sie eine Software entwickeln, um zu wissen, welche Schließfächer frei und welche in Gebrauch sind?

Die Lösung wäre eine Warteschlange oder ein Stapel.

Was ich suche, sind Dinge wie "In welcher Situation sollte ein B-Tree verwendet werden? Welcher Suchalgorithmus sollte hier verwendet werden?" Algorithmen funktionieren.

Ich habe versucht, in der Wikipedia-Liste der Datenstrukturen und Algorithmen nachzuschlagen, aber ich denke, das ist ein bisschen übertrieben. Also suche ich mehr nach den wesentlichen Dingen, die ich erkennen sollte?

Earlz
quelle
10
Abstimmung als "nicht konstruktiv" zu schließen. Jede Antwort ist völlig subjektiv - es besteht kein Konsens darüber, was man wissen sollte.
Oded
2
Welcher Teil dieses Schließfachproblems erfordert eine Eingabe- / Ausgabebestellung? [Tipp!]
Telastyn
5
@Oded Es gibt absolut eine Liste, über die sich die meisten Leute einig sein werden, welche Datenstrukturen und Algorithmen ein versierter Programmierer kennen sollte.
David Cowden
6
@Oded Kein Konsens? Was ist mit dem Lehrplan eines Einführungskurses in Algorithmen und Datenstrukturen in der Informatik? Sehr gut standardisiert und von Fachleuten begutachtet . Ein guter Ausgangspunkt.
MarkJ
3
Alternative Lösung; Nehmen Sie an, dass Sie tageweise aufladen und eine maximale Gebühr haben. Bringen Sie ein Papieretikett am Schlüssel an, wenn Sie das Schließfach lassen und die julianische Tageszahl darauf schreiben. Wenn der Schlüssel zurückgegeben wird, sehen Sie sich den Tag an, um die fällige Miete zu berechnen. Fehlende oder unleserliche Tags ziehen die maximale Gebühr an. Die unbenutzten Schlüssel werden in einer Tasche aufbewahrt (da Sie keinen bestimmten Schlüssel aus den freien Schlüsseln auswählen müssen, wenn Sie ein Schließfach lassen). Gesamtgröße der Datenstruktur: Null Bits. Alle Teile des Algorithmus sind O (1).
James Youngman

Antworten:

78

Eine objektive Antwort:

Während meine anfängliche Antwort auf diese Frage auf meiner empirischen Erfahrung als angehender CS-Student und meiner projizierten Meinung über die Art von Menschen beruhte, mit denen ich im CS-Bereich zusammenarbeiten wollte. Es gibt tatsächlich eine objektive (in Bezug auf die subjektiven Meinungen der ACM SIGCSE und IEEE Computing Society) Antwort. Alle 10 Jahre arbeiten das ACM und die IEEE- Gremien an einer gemeinsamen Veröffentlichung zusammen, in der Vorschläge für ein Informatik-Curriculum für Grundstudenten auf der Grundlage von Fachkenntnissen über den Stand der Computerbranche aufgeführt sind. Weitere Informationen finden Sie unter cs2013.org . Das Komitee veröffentlicht einen Abschlussbericht, in dem die Lehrplanempfehlungen aufgeführt sind .

Trotzdem finde ich meine Liste immer noch ziemlich gut.

Ursprüngliche Antwort unten.


Was muss ich wissen?

Minimum

Ich denke, ein erfahrener Programmierer sollte mindestens Grundkenntnisse in Informatik haben. Sicher, Sie können bei vielen Jobs mit nur einem kleinen Teil der Informatik effektiv sein, da CS auf einer soliden Community basiert und der Fokus der meisten professionellen Positionen eingeschränkt ist. Außerdem werden sich viele Menschen nach dem Bachelor-Studium weiter spezialisieren. Ich denke jedoch auch nicht, dass dies eine Ausrede ist, um nicht mit grundlegenden CS-Kenntnissen vertraut zu sein.

Um die Titelfrage zu beantworten, sollte ein CS-Student (die Grundlage für einen erfahrenen Programmierer) nach seinem Abschluss Folgendes wissen:

Datenstrukturen

  • Maschinendaten-Darstellung
    • Einsen, Zweierkomplement und verwandte Arithmetik
    • Wörter, Zeiger, Gleitkomma
    • Bit-Zugriff, Verschiebung und Manipulation
  • Verknüpfte Listen
  • Hash-Tabellen (Karten oder Wörterbücher)
  • Arrays
  • Bäume
  • Stapel
  • Warteschlangen
  • Diagramme
  • Datenbanken

Algorithmen

  • Sortierung:
    • Bubble Sort (um zu wissen, warum es schlecht ist)
    • Sortieren durch Einfügen
    • Zusammenführen, sortieren
    • Schnelle Sorte
    • Radix-Stil sortiert, Zählsortierung und Eimersortierung
    • Heap Sort
    • Bogo und Quantum Sort (=
  • Suche:
    • Lineare Suche
    • Binäre Suche
    • Tiefe erste Suche
    • Breite erste Suche
  • String-Manipulation
  • Wiederholung
  • Baum-Durchquerung
  • Liste Traversal
  • Hashing-Funktionen
  • Konkrete Implementierung einer Hash-Tabelle, eines Baums, einer Liste, eines Stapels, einer Warteschlange, eines Arrays und einer Menge oder einer Sammlung
  • Scheduling-Algorithmen
  • Dateisystem-Traversal und -Manipulation (auf der Inode- oder äquivalenten Ebene).

Designmuster

  • Modularisierung
  • Fabrik
  • Baumeister
  • Singleton
  • Adapter
  • Dekorateur
  • Fliegengewicht
  • Beobachter
  • Iterator
  • Zustandsmaschine]
  • Model View Controller
  • Threading und parallele Programmiermuster

Paradigmen

  • Imperativ
  • Objektorientierter
  • Funktional
  • Deklarativ
  • Statische und dynamische Programmierung
  • Datenmarkierung

Komplexitätstheorie

  • Komplexitätsräume
  • Berechenbarkeit
  • Regelmäßige, kontextfreie und universelle Turing-Maschine für vollständige Sprachen
  • Reguläre Ausdrücke
  • Zählen und grundlegende Kombinatorik

Darüber hinaus

Um später in Ihrer Frage zu erfahren, worüber Sie Fragen haben, sollten Sie in der Lage sein, das entsprechende Muster, den Algorithmus und die Datenstruktur für ein bestimmtes Szenario zu identifizieren, sofern Sie mit dem oben Gesagten vertraut sind. Sie sollten jedoch erkennen, dass es oft keine beste Lösung gibt. Manchmal kann es erforderlich sein, das kleinere von zwei Übeln auszuwählen oder einfach zwischen zwei gleichermaßen realisierbaren Lösungen zu wählen. Aus diesem Grund benötigen Sie das allgemeine Wissen, um Ihre Wahl gegen Ihre Kollegen zu verteidigen.

Hier einige Tipps für Algorithmen und Datenstrukturen:

  • Die binäre Suche kann (und sollte) nur für sortierte Daten verwendet werden.
  • Radix-Style-Sortierungen sind fantastisch, aber nur, wenn Sie endliche Klassen von Dingen haben, die sortiert werden.
  • Bäume sind für fast alles gut, ebenso wie Hash-Tabellen. Die Funktionalität einer Hash-Tabelle kann extrapoliert und verwendet werden, um viele Probleme auf Kosten der Effizienz zu lösen.
  • Mit Arrays können die meisten Datenstrukturen auf höherer Ebene gesichert werden. Manchmal ist eine "Datenstruktur" nicht mehr als eine clevere Mathematik für den Zugriff auf Positionen in einem Array.
  • Die Wahl der Sprache kann der Unterschied zwischen dem Herausziehen der Haare oder dem Durchsegeln eines Problems sein.
  • Die ASCII-Tabelle und ein 128-Elemente-Array bilden eine implizite Hash-Tabelle (=
  • Reguläre Ausdrücke können viele Probleme lösen, aber nicht zum Parsen von HTML verwendet werden .
  • Manchmal ist die Datenstruktur genauso wichtig wie der Algorithmus.

Einige der oben genannten Punkte scheinen keine Hirngespinste zu sein, andere scheinen vage zu sein. Wenn Sie wollen, dass ich näher darauf eingehen kann, kann ich. Ich hoffe jedoch, dass Sie bei einer konkreteren Frage wie "Entwerfen einer Funktion, die die Anzahl der Vorkommen jedes Zeichens in einer Zeichenfolge zählt" den Tipp zur ASCII-Tabelle und zu 128 Elementarrays lesen, die einen sauberen impliziten Hash bilden Tabellen für die Antwort.

Basierend auf diesen Ideen werde ich eine Antwort auf das in Ihrer Frage umrissene Schließfachproblem vorschlagen.


Beantworten Sie das in Ihrer Frage aufgeworfene Problem.

Dies ist möglicherweise nicht die beste Antwort auf Ihre Frage, aber ich denke, es ist eine interessante Frage, die nichts zu Komplexes erfordert. Und es wird sicherlich die zeitliche Komplexität der Verwendung einer Warteschlange oder eines Stapels übertreffen, die eine lineare Zeit benötigt, um zu bestimmen, ob ein Schließfach frei ist oder nicht.

Sie haben 0-999 Schließfächer. Da Sie nun eine feste Anzahl von Schließfächern haben, können Sie sich leicht eine Hash-Funktion ohne Kollisionen im Bereich von 0 bis 999 vorstellen. Diese Funktion ist einfach h (x) = x mod 1000. Konstruieren Sie nun [konzeptionell] eine Hash-Tabelle mit ganzzahligen Schlüsseln und dem Inhalt eines 1000-Elemente-Zeichen-Arrays als Ihre Werte. Wenn ein Kunde das Schließfach 78 für die Verwendung reservieren möchte, geben Sie einfach 78 in die Hash-Funktion ein (Rückgabe von 78) und fügen Sie diese Zahl zum Basiszeiger des Arrays hinzu. Dabei wird ein wahrer Wert an der Stelle gespeichert, auf die der Versatzwert zeigt . Wenn Sie überprüfen möchten, ob 78 verwendet wird, lesen Sie einfach den an diesem Ort gespeicherten Wert und vergleichen Sie ihn mit true.

Diese Lösung arbeitet für die Suche und Speicherung in konstanter Zeit, im Gegensatz zu einer Speicherung und Suche in Protokoll (n) für den Fall einer Prioritätswarteschlange, die durch einen Binärbaum gesichert ist. Die Beschreibung ist absichtlich ausführlich, damit Sie sehen können, wie die höheren Konzepte zu einem effizienten Algorithmus zusammengefasst werden.

Nun fragen Sie sich vielleicht, was wäre besser, wenn ich alle verfügbaren Schließfächer kennen müsste? Wenn in der Prioritätswarteschlange k verfügbare Schließfächer vorhanden sind, dauert das Iterieren über alle von ihnen k Schritte. Abhängig von Ihrer Prioritätswarteschlangenimplementierung müssen Sie möglicherweise Ihre Prioritätswarteschlange neu erstellen, wenn Sie sich alles ansehen. Dies würde k * log (k): (k <1000) Schritte erfordern. In der Array-Lösung müssen Sie nur ein 1000-Elemente-Array iterieren und prüfen, welche geöffnet sind. Sie können der Implementierung auch eine verfügbare oder verwendete Liste hinzufügen, um nur die Uhrzeit einzuchecken.

David Cowden
quelle
1
Gute Antwort! Ich möchte auch hinzufügen, dass Sie wirklich sicher sein sollten, die vordefinierten Funktionen / Datenstrukturen der von Ihnen verwendeten Sprache zu verwenden, beispielsweise Algorithmus- und STL-Datenstrukturen in C ++ oder die Java-API für Java.
Marktani
1
Ausgezeichnet! Insbesondere "Reguläre Ausdrücke können viele Probleme lösen, aber nicht zum Parsen von HTML verwendet werden."
FrustratedWithFormsDesigner
2
Die Antwort war gut, bis das "Problem" auftauchte. Es gibt überhaupt keinen Grund, eine Prioritätswarteschlange oder eine Hash-Tabelle zu verwenden. Ein einfacher Stapel reicht aus. Fügen Sie Iteration hinzu, um die vollständige Liste der kostenlosen Schließfächer abzurufen.
Matthieu M.
1
Sollten wir relationale Datenbank + SQL, Kenntnisse über B + -Baum, Compilertheorie, Kenntnisse über Hardwareorganisation, Kenntnisse über Betriebssystemtheorie und Kenntnisse über TCP / IP-Netzwerke hinzufügen?
Dan_l
1
Ich bin skeptisch gegenüber Design Patterns. Viele sind in einigen Arten von Sprachen nützlich, während sie in anderen nutzlos und / oder unnötig sind. Möglicherweise möchten Sie auch Heuristiken unter Algorithmen und die Trie- und Überspringlisten-Datenstrukturen hinzufügen. Herkömmliche Algorithmen / Datenstrukturen erreichen eine Grenze für den synchronen Zugriff, können jedoch von anderen nicht herkömmlichen Ansätzen unter Verwendung mehrerer Threads und gleichzeitiger Zugriffe übertroffen werden. Heuristiken können die Anzahl der erforderlichen Suchvorgänge drastisch verringern, während Strukturen wie eine Überspringliste das Schreiben der Datenstruktur ohne globale Sperre ermöglichen.
Evan Plaice
6

Das Algorithm Design Manual von Steven S. Skiena scheint die Quelle zu sein, nach der Sie suchen. Der zweite Teil ist eine klassifizierte Liste von Problemen mit einer Überprüfung der zugehörigen Algorithmen. Es gibt eine Webversion .

Ein Programmierer
quelle
3
Ein großartiges Buch, aber Sie müssen nicht alles beherrschen, um wirklich ein Programmierer zu sein. Ich habe es erst kürzlich gekauft und bin seit 1979 für das Programm bezahlt worden. (Und ja, ich habe es gekauft, weil ich glaubte, etwas daraus lernen zu können.)
Kate Gregory
@KateGregory Ich habe das Buch gekauft und konnte es nicht richtig verstehen, weil ich nur hochqualifizierte Sprachen wie Ruby und Javascript kenne (keine Binärbäume, verknüpfte Listen usw.) ... Ich habe es schließlich aufgegeben, es zu lesen.
Bigpotato
4

Es gibt kein "sollte". A. Machen Sie sich mit den grundlegenden Komplexitätsklassen (linear, logarithmisch usw.) vertraut. B. Stellen Sie fest, dass Sie mit einem einfachen Array so gut wie alles tun können, wie mit einer ausgefallenen Datenstruktur wie einem B-Baum. Der Trick bei der Auswahl der geeigneten Struktur / des geeigneten Algorithmus besteht darin, die Leistung, die erwartete Eingabegröße und die Komplexität der Implementierung in Einklang zu bringen.

Dann gibt es abstrakte, aber immens nützliche Dinge (obwohl die Nützlichkeit nicht sofort offensichtlich ist): Zustandsmaschinen, Graphentheorie, Konvexitätstheorie (lineare Programmierung usw.).

zvrba
quelle
1
Unterschätzen Sie nicht, wie wichtig es ist, zu wissen, wann man was verwendet. Weil diese Probleme, die Sie mithilfe eines einfachen Arrays gelöst haben, zurückkommen und Sie beißen, wenn Sie im Begriff sind, diesen großen Client einzuspielen und herauszufinden, dass Ihre jahrelang einwandfreie Anwendung zu einem Crawl verlangsamt wird, nur weil Sie stattdessen einen Bubblesort verwendet haben eine Quicksorte.
Pieter B
3

Das MIT veröffentlicht kostenlose Vorlesungsunterlagen, Videos, Aufgaben und Prüfungsunterlagen zur Einführung in Algorithmen . In den Vorlesungstiteln sind die behandelten Algorithmen / Datenstrukturen aufgeführt.

Dies ist ein von Experten überprüfter Konsens darüber, was Sie wissen sollten. Es ist wahrscheinlich auch eine großartige Lernressource.

MarkJ
quelle