Warum dauert der Zugriff auf ein Element in einem Array konstant?

Nehmen wir an, ich habe ein Array als:

int a[]={4,5,7,10,2,3,6}

wenn ich auf ein Element zugreife, wie z a[3], was passiert eigentlich hinter den Kulissen? Warum sagen viele Algorithmenbücher (wie das Cormen-Buch …), dass es eine konstante Zeit dauert?

(Ich bin nur ein Noob in Low-Level-Programmierung, also würde ich gerne mehr von euch lernen)

Das Array ist effektiv durch eine Speicherstelle (einen Zeiger) bekannt. Zugriff a[3] kann in konstanter Zeit gefunden werden, da es nur location_of_a+3*sizeof(int) ist.

In C sieht man das direkt. Denken Sie daran, a[3] ist das gleiche wie *(a+3) – was in Bezug auf das, was es tut, etwas klarer ist (Dereferenzieren des Zeigers “3 Elemente” über).

Ein Array von 10 Integer-Variablen mit den Indizes 0 bis 9 kann als 10 Wörter an den Speicheradressen 2000, 2004, 2008, … 2036 gespeichert werden, sodass das Element mit dem Index i die Adresse 2000 + 4 × i hat. Dieser Prozess erfordert eine Multiplikation und eine Addition. Da diese beiden Operationen eine konstante Zeit in Anspruch nehmen, können wir sagen, dass der Zugriff in konstanter Zeit durchgeführt werden kann

Nur um vollständig zu sein: “Auf welche Struktur wird in linearer Zeit zugegriffen?” EIN Verknüpfte Liste Der Zugriff auf die Struktur erfolgt in linearer Zeit. Um das zu bekommen n Element, durch das Sie reisen müssen n-1 vorherige Elemente. Sie wissen, wie bei einem Tonbandgerät oder einer VHS-Kassette, wo Sie lange warten mussten, um zum Ende des Bandes / der VHS zu gelangen 🙂

Ein Array ähnelt eher einer Festplatte: Jeder Punkt ist in “konstanter” Zeit erreichbar 🙂

Aus diesem Grund heißt der Arbeitsspeicher eines Computers RAM: Random Access Memory. Sie können zu jedem Ort gehen, wenn Sie dessen Adresse kennen, ohne den gesamten Speicher vor diesem Ort zu durchlaufen.

Einige Leute sagten mir, dass der HD-Zugriff nicht wirklich in konstanter Zeit erfolgt (wobei ich mit Zugriff meine “Zeit, um den Kopf zu positionieren und einen Sektor der HD zu lesen”). Ich muss sagen, dass ich mir dessen nicht sicher bin. Ich habe herum gegoogelt und ich habe niemanden gefunden, der darüber spricht. Ich weiß, dass die Zeit nicht linear ist, weil immer noch zufällig darauf zugegriffen wird. Wenn Sie am Ende der Meinung sind, dass Ihnen der HD-Zugriff nicht konstant genug ist (aber was ist dann konstant? der Zugriff auf den Arbeitsspeicher? unter Berücksichtigung von Cache-, Prefetching-, Data Locality- und Compiler-Optimierungen?), können Sie den Satz gerne in Betracht ziehen wie Ein Array ähnelt eher einem USB-Stick: Jeder Punkt ist in “konstanter” Zeit zugänglich 🙂

Weil Arrays sequentiell im Speicher gespeichert werden. Also eigentlich, wenn Sie auf Array zugreifen[3] Sie sagen dem Computer: “Holen Sie sich die Speicheradresse des Anfangs des Arrays, fügen Sie dann 3 hinzu und greifen Sie dann auf diese Stelle zu.” Da das Hinzufügen konstant viel Zeit in Anspruch nimmt, gilt dies auch für den Array-Zugriff!

“Konstante Zeit” bedeutet eigentlich “Zeit, die nicht von der ‘Problemgröße’ abhängt”. Für das „Problem“ „etwas aus einem Behälter herausholen“ ist die „Problemgröße“ die Größe des Behälters.

Der Zugriff auf ein Array-Element dauert grundsätzlich gleich lange (dies ist eine Vereinfachung), unabhängig von der Containergröße, da ein fester Satz von Schritten verwendet wird, um das Element abzurufen: seine Position im Speicher (dies ist auch eine Vereinfachung) wird berechnet, und dann wird der Wert an dieser Stelle im Speicher abgerufen.

Eine verkettete Liste beispielsweise kann dies nicht, weil jeder Link den Ort des nächsten angibt. Um ein Element zu finden, müssen Sie alle vorherigen durcharbeiten; Im Durchschnitt arbeiten Sie durch die Hälfte des Containers, daher spielt die Größe des Containers natürlich eine Rolle.

Array ist eine Sammlung ähnlicher Datentypen. Alle Elemente benötigen also die gleiche Menge an Speicher. Wenn Sie also die Basisadresse des Arrays und den darin enthaltenen Datentyp kennen, können Sie das Element Array leicht erhalten[i] in konstanter Zeit unter Verwendung der unten angegebenen Formel:

int takes 4 bytes in a 32 bit system.
int array[10];
base address=4000;
location of 7th element:4000+7*4.
array[7]=array[4000+7*4];

Daher ist es deutlich sichtbar, dass Sie das Element in konstanter Zeit erhalten können, wenn Sie die Basisadresse und den Datentyp kennen, den es enthält. Bitte besuche Dies Link, um mehr über die Array-Datenstruktur zu erfahren.

Ein Array ist sequentiell, was bedeutet, dass die Adresse des nächsten Elements im Array neben der des aktuellen steht. Wenn Sie also das 5. Element eines Arrays erhalten möchten, berechnen Sie die Adresse des 5. Elements, indem Sie die Basisadresse des Arrays mit 5 summieren. Diese direkte Adresse wird nun direkt verwendet, um das Element an dieser Adresse zu erhalten.

Sie können jetzt dieselbe Frage hier weiter stellen: “Woher kennt der Computer die berechnete Adresse bzw. greift sie direkt darauf zu?” Dies ist die Natur und das Prinzip des Computerspeichers (RAM). Wenn Sie weiter daran interessiert sind, wie RAM auf jede Adresse in konstanter Zeit zugreift, können Sie es in jedem Computerorganisationstext finden oder einfach googeln.