Warum verwenden wir Arrays anstelle anderer Datenstrukturen?

Während des Programmierens habe ich keine Instanz gesehen, in der ein Array besser zum Speichern von Informationen geeignet ist als eine andere Form davon. Ich hatte tatsächlich angenommen, dass die hinzugefügten "Funktionen" in Programmiersprachen dies verbessert und dadurch ersetzt hatten. Ich sehe jetzt, dass sie nicht ersetzt werden, sondern sozusagen neues Leben erhalten.

Was bringt es also, Arrays zu verwenden?

Dies ist nicht so sehr der Grund, warum wir Arrays vom Standpunkt des Computers aus verwenden, sondern vielmehr, warum wir Arrays vom Standpunkt der Programmierung aus verwenden (ein subtiler Unterschied). Was der Computer mit dem Array macht, war nicht der Punkt der Frage.

Zeit für eine Lektion in die Vergangenheit zu reisen. Obwohl wir heute in unseren ausgefallenen verwalteten Sprachen nicht viel über diese Dinge nachdenken, basieren sie auf derselben Grundlage. Schauen wir uns also an, wie der Speicher in C verwaltet wird.

Bevor ich eintauche, eine kurze Erklärung, was der Begriff " Zeiger " bedeutet. Ein Zeiger ist einfach eine Variable, die auf eine Stelle im Speicher "zeigt". Es enthält nicht den tatsächlichen Wert in diesem Speicherbereich, sondern die Speicheradresse dafür. Stellen Sie sich einen Speicherblock als Postfach vor. Der Zeiger wäre die Adresse zu diesem Postfach.

In C ist ein Array einfach ein Zeiger mit einem Versatz. Der Versatz gibt an, wie weit im Speicher gesucht werden soll. Dies bietet eine O (1) -Zugriffszeit.

  MyArray   [5]
     ^       ^
  Pointer  Offset

Alle anderen Datenstrukturen bauen entweder darauf auf oder verwenden keinen benachbarten Speicher zum Speichern, was zu einer schlechten Suchzeit für wahlfreien Zugriff führt (obwohl es andere Vorteile gibt, wenn kein sequentieller Speicher verwendet wird).

Nehmen wir zum Beispiel an, wir haben ein Array mit 6 Zahlen (6,4,2,3,1,5), im Speicher würde es so aussehen:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================

In einem Array wissen wir, dass sich jedes Element im Speicher nebeneinander befindet. Das AC-Array ( MyArrayhier aufgerufen ) ist einfach ein Zeiger auf das erste Element:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^
MyArray

Wenn wir nachschlagen wollten MyArray[4], würde intern wie folgt darauf zugegriffen:

   0     1     2     3     4 
=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
                           ^
MyArray + 4 ---------------/
(Pointer + Offset)

Da wir durch Hinzufügen des Versatzes zum Zeiger direkt auf jedes Element im Array zugreifen können, können wir jedes Element unabhängig von der Größe des Arrays in derselben Zeitspanne nachschlagen. Dies bedeutet, dass das Erhalten MyArray[1000]genauso viel Zeit in Anspruch nehmen würde wie das Erhalten MyArray[5].

Eine alternative Datenstruktur ist eine verknüpfte Liste. Dies ist eine lineare Liste von Zeigern, die jeweils auf den nächsten Knoten zeigen

========    ========    ========    ========    ========
| Data |    | Data |    | Data |    | Data |    | Data |
|      | -> |      | -> |      | -> |      | -> |      | 
|  P1  |    |  P2  |    |  P3  |    |  P4  |    |  P5  |        
========    ========    ========    ========    ========

P(X) stands for Pointer to next node.

Beachten Sie, dass ich jeden "Knoten" zu einem eigenen Block gemacht habe. Dies liegt daran, dass nicht garantiert wird, dass sie im Speicher benachbart sind (und höchstwahrscheinlich auch nicht).

Wenn ich auf P3 zugreifen möchte, kann ich nicht direkt darauf zugreifen, da ich nicht weiß, wo es sich im Speicher befindet. Ich weiß nur, wo sich die Wurzel (P1) befindet. Stattdessen muss ich bei P1 beginnen und jedem Zeiger auf den gewünschten Knoten folgen.

Dies ist eine O (N) -Nachschlagzeit (Die Nachschlagekosten steigen, wenn jedes Element hinzugefügt wird). Es ist viel teurer, zu P1000 zu gelangen, als zu P4.

Übergeordnete Datenstrukturen wie Hashtabellen, Stapel und Warteschlangen verwenden möglicherweise intern ein Array (oder mehrere Arrays), während verknüpfte Listen und Binärbäume normalerweise Knoten und Zeiger verwenden.

Sie fragen sich vielleicht, warum jemand eine Datenstruktur verwendet, die eine lineare Durchquerung erfordert, um einen Wert nachzuschlagen, anstatt nur ein Array zu verwenden, aber sie haben ihre Verwendung.

Nehmen Sie unser Array wieder. Dieses Mal möchte ich das Array-Element finden, das den Wert '5' enthält.

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^     ^     ^     ^     ^   FOUND!

In dieser Situation weiß ich nicht, welchen Offset ich dem Zeiger hinzufügen soll, um ihn zu finden. Daher muss ich bei 0 beginnen und mich nach oben arbeiten, bis ich ihn finde. Dies bedeutet, dass ich 6 Überprüfungen durchführen muss.

Aus diesem Grund wird die Suche nach einem Wert in einem Array als O (N) betrachtet. Die Suchkosten steigen, wenn das Array größer wird.

Erinnern Sie sich oben, wo ich sagte, dass die Verwendung einer nicht sequentiellen Datenstruktur manchmal Vorteile haben kann? Die Suche nach Daten ist einer dieser Vorteile und eines der besten Beispiele ist der Binärbaum.

Ein Binärbaum ist eine Datenstruktur ähnlich einer verknüpften Liste. Anstatt jedoch mit einem einzelnen Knoten zu verknüpfen, kann jeder Knoten mit zwei untergeordneten Knoten verknüpft werden.

         ==========
         |  Root  |         
         ==========
        /          \ 
  =========       =========
  | Child |       | Child |
  =========       =========
                  /       \
            =========    =========
            | Child |    | Child |
            =========    =========

 Assume that each connector is really a Pointer

Wenn Daten in einen Binärbaum eingefügt werden, werden anhand mehrerer Regeln entschieden, wo der neue Knoten platziert werden soll. Das Grundkonzept lautet: Wenn der neue Wert größer als der der Eltern ist, wird er links eingefügt. Wenn er niedriger ist, wird er rechts eingefügt.

Dies bedeutet, dass die Werte in einem Binärbaum folgendermaßen aussehen könnten:

         ==========
         |   100  |         
         ==========
        /          \ 
  =========       =========
  |  200  |       |   50  |
  =========       =========
                  /       \
            =========    =========
            |   75  |    |   25  |
            =========    =========

Bei der Suche in einem Binärbaum nach dem Wert 75 müssen aufgrund dieser Struktur nur 3 Knoten (O (log N)) besucht werden:

• Ist 75 weniger als 100? Schauen Sie sich den rechten Knoten an
• Ist 75 größer als 50? Schauen Sie sich den linken Knoten an
• Da ist die 75!

Obwohl unser Baum 5 Knoten enthält, mussten wir uns die verbleibenden zwei nicht ansehen, da wir wussten, dass sie (und ihre Kinder) möglicherweise nicht den Wert enthalten konnten, den wir suchten. Dies gibt uns eine Suchzeit, die im schlimmsten Fall bedeutet, dass wir jeden Knoten besuchen müssen, aber im besten Fall müssen wir nur einen kleinen Teil der Knoten besuchen.

Hier werden Arrays geschlagen, sie bieten trotz O (1) -Zugriffszeit eine lineare O (N) -Suchzeit.

Dies ist eine unglaublich umfassende Übersicht über Datenstrukturen im Speicher, die viele Details überspringt, aber hoffentlich die Stärke und Schwäche eines Arrays im Vergleich zu anderen Datenstrukturen veranschaulicht.

Für O (1) Direktzugriff, der nicht zu schlagen ist.

Nicht alle Programme machen dasselbe oder laufen auf derselben Hardware.

Dies ist normalerweise die Antwort, warum verschiedene Sprachfunktionen existieren. Arrays sind ein zentrales Konzept der Informatik. Das Ersetzen von Arrays durch Listen / Matrizen / Vektoren / unabhängig von der erweiterten Datenstruktur würde die Leistung erheblich beeinträchtigen und in einer Reihe von Systemen geradezu undurchführbar sein. Es gibt eine beliebige Anzahl von Fällen, in denen die Verwendung eines dieser "erweiterten" Datenerfassungsobjekte aufgrund des betreffenden Programms verwendet werden sollte.

In der Business-Programmierung (was die meisten von uns tun) können wir auf Hardware abzielen, die relativ leistungsfähig ist. Die Verwendung einer Liste in C # oder eines Vektors in Java ist in diesen Situationen die richtige Wahl, da der Entwickler mit diesen Strukturen die Ziele schneller erreichen kann, wodurch diese Art von Software besser genutzt werden kann.

Beim Schreiben von eingebetteter Software oder eines Betriebssystems ist ein Array häufig die bessere Wahl. Ein Array bietet zwar weniger Funktionen, benötigt jedoch weniger RAM und der Compiler kann den Code effizienter für die Suche in Arrays optimieren.

Ich bin sicher, dass ich einige der Vorteile für diese Fälle weglasse, aber ich hoffe, dass Sie den Punkt verstehen.

Eine Möglichkeit, die Vorteile von Arrays zu betrachten, besteht darin, festzustellen, wo die O (1) -Zugriffsfähigkeit von Arrays erforderlich ist und daher aktiviert wird:

1. In Nachschlagetabellen Ihrer Anwendung (ein statisches Array für den Zugriff auf bestimmte kategoriale Antworten)

2. Memoisierung (bereits berechnete komplexe Funktionsergebnisse, damit Sie den Funktionswert nicht erneut berechnen, z. B. log x)

3. Hochgeschwindigkeits-Computer-Vision-Anwendungen, die eine Bildverarbeitung erfordern ( https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing )