Warum wird in einem Array O (1) gesucht?

Question

Ich glaube, dass in einigen anderen Sprachen als Ruby eine Array-Suche O (1) ist, weil Sie wissen, wo die Daten beginnen, und multiplizieren Sie den Index mit der Größe der Daten, die das Array hält, und greifen Sie dann auf diesen Speicherort .

Allerdings kann ein Array in Ruby Objekte aus verschiedenen Klassen haben, also wie schafft es ein Nachschlagen von O (1) Komplexität?

Answer 1

Was @Neil Slater sagte, mit ein wenig mehr Details ...

Grundsätzlich gibt es zwei plausible Ansätze eine Reihe von heterogenen Objekten unterschiedlicher Größe zu speichern:

1. Shop die Objekte als einzeln - oder doppelt - linked list, wobei dem Speicherplatz für jedes einzelne Objekt ein oder mehrere Zeiger auf die vorhergehenden und/oder folgenden Objekte vorangestellt sind. Diese Struktur hat den Vorteil, dass es sehr einfach ist, neue Objekte an beliebigen Stellen einzufügen, ohne sich um den Rest des Arrays zu bewegen. Der Nachteil ist jedoch, dass das Nachschlagen eines Objekts an seiner Position generell O(N) ist, da man von einem beginnen muss Ende der Liste und durchspringe sie Knoten für Knoten, bis du bei der n-ten ankommst.

2. Speichern Sie eine Tabelle oder ein Array von Zeigern konstanter Größe auf die einzelnen Objekte. Da diese Nachschlagetabelle Objekte konstanter Größe in einem zusammenhängenden geordneten Layout enthält, suchen Sie nach den Adressen einzelner Objekte O(1); Die Tabelle ist nur ein C-artiges Array, in dem die Suche nur ein paar wenige Maschinenanweisungen benötigt, sogar auf RISC-CPU-Architekturen.

(Die Allocation-Strategien der einzelnen Objekte für die Speicherung sind auch interessant und komplex, aber nicht unmittelbar relevant für Ihre Frage.)

dynamische Sprachen wie Perl/Python/Ruby-ziemlich alle entscheiden sich für # 2 für ihre allgemeine Liste/Array-Typen. Mit anderen Worten, sie machen die Suche effizienter als das Einfügen von Objekten an zufälligen Orten in der Liste, was für viele Anwendungen die bessere Wahl ist.

Ich bin nicht vertraut mit den Implementierungsdetails für Ruby, aber sie sind wahrscheinlich sehr ähnlich denen von Pythons list Art, deren Leistung und Design in wunderbaren Details bei effbot.org erklärt wird.

Answer 2

Ihre Implementierung enthält wahrscheinlich ein Array von Speicheradressen, die auf die tatsächlichen Objekte zeigen. Daher kann es immer noch nachschlagen, ohne das Array zu durchlaufen.