Die Wahl der richtigen Datenstruktur kann Ihr Programm effizienter machen. Hier finden Sie einen Leitfaden, der Ihnen dabei hilft, die richtige Wahl zu treffen.

Die Auswahl der besten Datenstruktur für Ihre Ziele kann angesichts der Vielzahl verfügbarer Optionen eine Herausforderung darstellen. Berücksichtigen Sie bei der Auswahl einer Datenstruktur die Daten, mit denen Sie arbeiten, die an den Daten auszuführenden Vorgänge und die Umgebung, in der Ihre Anwendung ausgeführt wird.

Verstehen Sie Ihre Daten

Es ist wichtig, die Daten zu verstehen, mit denen Sie arbeiten, bevor Sie eine Datenstruktur auswählen. Gemeinsame Datenstrukturen Zu den Programmen, die mit verschiedenen Datentypen arbeiten, gehören Arrays, verknüpfte Listen, Bäume, Diagramme und Hash-Tabellen.

Wenn Sie beispielsweise zufällig auf Elemente aus Ihren Daten zugreifen müssen, sind Arrays möglicherweise die beste Wahl. Wenn Sie einer Liste ständig Elemente hinzufügen oder daraus löschen müssen und sich auch die Listengröße ändern kann, können verknüpfte Listen besonders nützlich sein.

instagram viewer

Wenn Sie mehrere Datenebenen, beispielsweise Datensatzstrukturen, effektiv speichern und Vorgänge wie Suchen und Sortieren ausführen müssen, sind Bäume hilfreich.

Wenn Sie Interaktionen zwischen Entitäten, beispielsweise in sozialen Netzwerken, beschreiben und Operationen wie kürzeste Pfade und Konnektivität ausführen müssen, werden Diagramme bevorzugt. Hash-Tabellen sind für eine schnelle Schlüsselsuche hilfreich.

Berücksichtigen Sie die Vorgänge, die an den Daten ausgeführt werden sollen

Bei der Auswahl einer Datenstruktur müssen Sie auch die Operationen berücksichtigen, die an den Daten ausgeführt werden sollen. Unterschiedliche Datenstrukturen optimieren zahlreiche Aktionen wie Sortieren, Suchen, Einfügen und Löschen.

Verknüpfte Listen eignen sich beispielsweise besser für Aktionen wie Einfügen und Löschen, Binärbäume eignen sich jedoch am besten zum Suchen und Sortieren. Eine Hash-Tabelle kann die beste Wahl sein, wenn Ihre Anwendung gleichzeitiges Einfügen und Suchen erfordert.

Bewerten Sie die Umgebung

Wenn Sie eine Datenstruktur in Betracht ziehen, müssen Sie die Umgebung bewerten, in der die Anwendung ausgeführt wird. Die Umgebung beeinflusst, wie gut und wie schnell auf Datenstrukturen zugegriffen werden kann.

Berücksichtigen Sie bei der Beurteilung Ihres aktuellen Zustands die folgenden Faktoren:

  1. Rechenleistung: Wählen Sie Datenstrukturen für Ihre Anwendungen aus, die auf PCs mit geringer Rechenleistung gut funktionieren, während sie auf der Plattform ausgeführt werden. Beispielsweise könnten einfachere Datenstrukturen wie Arrays geeigneter sein als Bäume oder Diagramme.
  2. Parallelität: Sie sollten eine threadsichere Datenstruktur wählen, die den gleichzeitigen Zugriff ohne Datenbeschädigung verarbeiten kann; wenn Ihre Anwendung in einer gleichzeitigen Umgebung ausgeführt wird, in der mehrere Threads oder Prozesse gleichzeitig auf die Datenstruktur zugreifen. In diesem Fall sind sperrenfreie Datenstrukturen wie ConcurrentLinkedQueue Und ConcurrentHashMap ist möglicherweise besser geeignet als herkömmliche Methoden wie ArrayLi und HashMap.
  3. Netzwerk-Latenz: Wenn Ihre Anwendung eine Datenübertragung über ein Netzwerk erfordert, müssen Sie die Netzwerklatenz berücksichtigen, während Sie sich für die beste Datenstruktur entscheiden. In solchen Situationen kann die Verwendung einer Datenstruktur, die Netzwerkaufrufe einschränkt oder die Menge der Datenübertragung reduziert, zur Verbesserung der Ausführung beitragen.

Gemeinsame Datenstrukturen und ihre Anwendungsfälle

Hier finden Sie eine Zusammenfassung einiger beliebter Datenstrukturen und ihrer Verwendung.

  1. Arrays: Dies ist eine einfache und effiziente Datenstruktur, die eine Reihe fester Größe von Elementen desselben Datentyps enthalten kann. Damit sie ordnungsgemäß funktionieren, benötigen sie über einen Index einen schnellen und direkten Zugriff auf bestimmte Objekte.
  2. Verknüpfte Listen: Verknüpfte Listen bestehen aus Knoten, die ein Element und einen Verweis auf den nächsten Knoten und/oder vorherigen Knoten enthalten. Aufgrund ihrer effizienten Abläufe eignen sich verknüpfte Listen am besten für Situationen, in denen häufig Elemente eingefügt oder gelöscht werden müssen. Allerdings ist der Zugriff auf einzelne Elemente über den Index in verknüpften Listen im Vergleich zu Arrays langsamer.
  3. Warteschlangen und Stapel: Stapel folgen der Last-In-First-Out (LIFO)-Regel, bei der der zuletzt eingefügte Artikel der erste entnommene Artikel ist. Warteschlangen unterliegen dem First-In-First-Out-Prinzip (FIFO). wobei das erste hinzugefügte Element auch das erste gelöschte Element ist.
  4. Hash-Tabellen: Hash-Tabellen sind eine Form von Datenstrukturen, die Schlüssel-Wert-Paare enthalten. Die beste Lösung ist die Verwendung von Hash-Tabellen, wenn die Anzahl der Komponenten unvorhersehbar ist und Sie einen schnellen Zugriff auf die Werte per Schlüssel benötigen.
  5. Bäume: Bäume sind hierarchische Datenstrukturen, die eine Gruppe von Elementen in einer Hierarchie speichern können. Die besten Einsatzmöglichkeiten für binäre Suchbäume befinden sich in hierarchischen Datenstrukturen, in denen die Beziehungen zwischen den Datenelementen eine baumartige Struktur darstellen können.

Auswahl der richtigen Datenstruktur

Berücksichtigen Sie vor der Auswahl einer Datenstruktur die Daten, Verpflichtungen und Umgebung Ihrer Anwendung. Berücksichtigen Sie bei Ihrer Wahl die folgenden Elemente:

  1. Zeitkomplexität: Die Leistung Ihrer Anwendung kann durch die zeitliche Komplexität Ihrer Datenstruktur erheblich beeinträchtigt werden. Wenn Ihre Anwendung häufige Such- oder Abrufvorgänge erfordert, verwenden Sie eine Datenstruktur mit geringerer Zeitkomplexität, wie z. B. eine Hash-Tabelle.
  2. Weltraumkomplexität: Die räumliche Komplexität der Datenstruktur ist ein weiterer wichtiger Gesichtspunkt. Wenn Ihre Anwendung speicherintensiv ist, wählen Sie eine Datenstruktur mit weniger Platzkomplexität, z. B. ein Array. Wenn der Platz keine Rolle spielt, können Sie eine Datenstruktur mit größerer Platzkomplexität verwenden, beispielsweise einen Baum.
  3. Lesen vs. Schreiboperationen: Wenn Ihre Anwendung viele Schreibvorgänge verwendet, wählen Sie eine Datenstruktur mit einer schnelleren Einfügeleistung, z. B. eine Hash-Tabelle. Wenn Ihre Anwendung viele Lesevorgänge erfordert, wählen Sie eine Datenstruktur mit einer schnelleren Suchgeschwindigkeit, beispielsweise einen binären Suchbaum.
  4. Art der Daten: Die Daten, mit denen Sie arbeiten, können sich auch auf die von Ihnen gewählte Datenstruktur auswirken. Beispielsweise können Sie eine baumbasierte Datenstruktur verwenden, wenn Ihre Daten hierarchisch sind. Wenn Sie über einfache Daten verfügen, auf die zufällig zugegriffen werden muss, kann die Wahl einer Array-basierten Datenstruktur die beste Option sein.
  5. Verfügbare Bibliotheken: Berücksichtigen Sie die Bibliotheken, die für die Datenstruktur, die Sie in Betracht ziehen, leicht zugänglich sind. Die Ausführung und Wartung könnte einfacher sein, wenn Ihre Programmiersprache über integrierte Bibliotheken für eine bestimmte Datenstruktur verfügt.

Das folgende Python-Beispiel zeigt, wie Sie die beste Datenstruktur für einen bestimmten Anwendungsfall auswählen.

Stellen Sie sich den Fall vor, dass Sie eine Dateisystemanwendung entwickeln, die Dateien in einer Hierarchie speichern und abrufen muss. Sie müssen eine Datenstruktur auswählen, die diese hierarchische Struktur effizient darstellen und Vorgänge wie Suchen, Einfügen und Löschen schnell ausführen kann.

Es könnte eine gute Idee sein, eine baumbasierte Datenstruktur wie eine binäre Suche oder einen B-Baum zu verwenden. Wenn die Anzahl der Einträge in jedem Verzeichnis relativ gering ist und der Baum nicht sehr tief ist, würde der binäre Suchbaum gut funktionieren. Für eine größere Anzahl von Dateien und tiefere Verzeichnisstrukturen wäre ein B-Baum besser geeignet.

Unten finden Sie ein Beispiel für einen binären Suchbaum in Python.

KlasseKnoten:
def__drin__(Selbst, Wert):

self.value = Wert
self.left_child = Keiner
self.right_child = Keiner

KlasseBinarySearchTree:

def__drin__(selbst):
self.root = Keiner
defEinfügung(Selbst, Wert):

Wenn self.root IstKeiner:
self.root = Knoten (Wert)

anders:
self._insert (Wert, self.root)
def_Einfügung(self, value, current_node):

Wenn Wert < current_node.value:
Wenn current_node.left_child IstKeiner:
current_node.left_child = Knoten (Wert)

anders:
self._insert (Wert, current_node.left_child)
elif value > current_node.value:
Wenn current_node.right_child IstKeiner:
current_node.right_child = Knoten (Wert)
anders:
self._insert (Wert, current_node.right_child)

anders:
drucken(„Wert existiert bereits im Baum.“)
defsuchen(Selbst, Wert):
Wenn self.root IstnichtKeiner:
zurückkehren self._search (Wert, self.root)

anders:
zurückkehrenFALSCH
def_suchen(self, value, current_node):

Wenn value == current_node.value:
zurückkehrenWAHR

elif Wert < aktueller_Knotenwert Und current_node.left_child IstnichtKeiner:
zurückkehren self._search (Wert, current_node.left_child)

elif value > current_node.value Und current_node.right_child IstnichtKeiner:
zurückkehren self._search (Wert, current_node.right_child)

anders:
zurückkehrenFALSCH

In dieser Implementierung erstellen Sie zwei Klassen: a BinarySearchTree Klasse, die Einfügungs- und Suchvorgänge verwaltet, und a Knoten Klasse, die einen Knoten im binären Suchbaum symbolisiert.

Während die Einfügemethode je nach Wert einen neuen Knoten an der entsprechenden Stelle im Baum einfügt, sucht die Suchmethode nach einem Knoten mit einem angegebenen Wert. Die zeitliche Komplexität beider Operationen in einem ausgeglichenen Baum beträgt O(log n).

Wählen Sie die optimale Datenstruktur

Die Geschwindigkeit und Anpassungsfähigkeit Ihrer Anwendung kann durch die von Ihnen gewählte Datenstruktur erheblich verbessert werden. Die Berücksichtigung Ihrer Daten, Ihrer Abläufe und Ihrer Umgebung kann Ihnen bei der Auswahl der besten Datenstruktur helfen.

Überlegungen wie zeitliche Komplexität, räumliche Komplexität, Lese- und Schreibvorgänge, Parallelität, Datentyp und Bibliothekszugänglichkeit sind wichtig.

Indem Sie das Gewicht jeder Komponente bewerten, sollten Sie die Datenstruktur auswählen, die den Anforderungen Ihrer Anwendung entspricht.