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.
Antworten:
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.
quelle