Wo finde ich Informationen zu Datenstrukturen, die in gängiger Software verwendet werden?

6

Im Rahmen eines Kurses, den ich über Datenstrukturen unterrichte, möchte ich, dass die Schüler die Verwendung von Datenstrukturen in gängigen Software / Diensten erforschen und präsentieren. Grundlegendes Googeln zeigt mir jedoch, dass diese Informationen nicht so leicht verfügbar sind.

Kann mich jemand auf die richtigen Ressourcen hinweisen, die ich als Ausgangspunkt für ihre Forschung mit den Studenten teilen kann?

BEARBEITEN

Nach den eingegangenen Antworten zu urteilen, ist die ursprüngliche Frage nicht klar genug, daher füge ich weitere Details hinzu.

Ich suche nach Ressourcen des Typs, der beispielsweise angibt, dass service-x die Datenstruktur-a verwendet, um die Funktionalität-y aufgrund der Eigenschaft-b auszuführen . Dies ist der Idealfall. Andere Ressourcen, die ähnliche Informationen bereitstellen, sind ebenfalls willkommen.

wsaleem
quelle
1
Bei so vielen Open Source-Softwareprogrammen, die auf GitHub gehostet werden, können Sie versuchen, auf GitHub nach häufig verwendeten Datenstrukturen zu suchen. Dort finden Sie unglaublich viele Treffer.
Andrew Au
Eine solche Suche liefert nur direkte Implementierungen der Datenstruktur, zB hier . Ich suche nach Fällen, in denen die Datenstruktur Teil einer größeren Software ist. Vielleicht können Sie eine hilfreichere Art der Suche vorschlagen.
Wsaleem
Wählen Sie Ihr bevorzugtes Datenstruktur- und Algorithmusbuch. Jede der beschriebenen Strukturen wird ziemlich häufig verwendet. Und ebenso exotischere Strukturen (die Literatur ist üppig), die in Fällen verwendet werden, in denen die Leistung ihrer bescheidenen Brüder zu kurz kommt.
vonbrand
1
Wählen Sie eine Open-Source-Bibliothek aus - es gibt viele. Ich denke, die Schüler können viel lernen, indem sie den Quellcode und die Dokumentation durchforsten.
Raphael
2
@SamM Vielleicht keine "beliebte Software", aber Fibonacci-Haufen werden sehr häufig in der Genom- und Transkriptom-Assemblierung für die Sequenzierung der zweiten Generation verwendet. De-novo-Assembler wie Velvet und SOAPdenovo verwenden den Dijkstra-Algorithmus für kürzeste Wege, um potenzielle Lesefehler zu erkennen.
Pseudonym

Antworten:

10

Aus dem Kopf:

Jedes moderne Betriebssystem verwendet ausgeglichene binäre Suchbäume, um die virtuelle Speicherzuordnung eines Prozesses zu implementieren. Windows verwendet Spreizbäume, Linux und OS X verwenden rot-schwarze Bäume und Solaris verwendet AVL-Bäume. Sie tun dies, weil das Betriebssystem die virtuelle Speicherzuordnung in der Reihenfolge (nach virtueller Adresse) speichern muss, um ein schnelles Einfügen und Entfernen zu ermöglichen und nach nicht verwendeten Bereichen zu suchen, in denen Speicherplatz zugewiesen werden kann.

Viele moderne 3D-Spiele (z. B. alles, was eine neuere Version von Unreal Engine verwendet) verwenden Oktrees, um zu bestimmen, welche Objekte für die Kamera sichtbar sind. Sie tun dies, weil es sehr effizient ist zu berechnen, welche Knoten sich mit dem Sichtstumpf einer Kamera überlappen.

Viele (wenn nicht die meisten) Router verwenden Radix-Bäume, um Routing-Tabellen zu implementieren. Sie tun dies, weil häufig das Präfix einer Netzwerkadresse (dh die höchstwertigen Bits) wichtig ist, nicht der gesamte Schlüssel. Darüber hinaus benötigt die Suche Zeit, die nur von der Größe der Adresse abhängt, nicht von der Anzahl der Routing-Tabelleneinträge, was die Vorhersage des Timings erleichtert.

Hash-Tabellen werden natürlich überall verwendet. Antivirensoftware verwendet es, um in seiner Datenbank nach bekannter Malware zu suchen, Textverarbeitungsprogramme verwenden es, um Rechtschreibprüfungen usw. durchzuführen.

Diagrammdatenstrukturen werden von Tabellenkalkulationen verwendet, um die Auswertung zu implementieren. Stellen Sie sich jede belegte Zelle als Knoten vor und zeichnen Sie einen Bogen zwischen den Zellen, wenn der Wert der einen direkt vom Wert der anderen abhängt. Wenn sich ein Eintrag in einer Zelle ändert, wird das Diagramm durchlaufen, um zu bestimmen, welche Zellen basierend auf dieser Änderung aktualisiert werden müssen.

Pseudonym
quelle