Warum ist 2D-Array besser als Objekte, um x-y-Koordinaten für bessere Leistung und weniger Speicher zu speichern?

Question

Angenommen, ich möchte n Punkte mit ganzzahligen (x, y) Koordinaten speichern. Ich kann ein 2-d (2Xn) -Array verwenden oder eine Liste/Sammlung/oder ein Array von n Objekten verwenden, wobei jedes Objekt 2 ganzzahlige Felder zum Speichern der Koordinaten hat. Soweit ich weiß ist die 2d-Array-Option schneller und verbraucht weniger Speicher, aber ich weiß nicht warum? Detaillierte Erklärung oder Links mit Details sind willkommen.

Answer 1

Dies ist eine sehr weit gefasste Frage, und irgendwie hat es viele Teile dazu. Zunächst einmal, das ist relativ zu der Sprache, in der Sie arbeiten. Lassen Sie uns Java als Beispiel nehmen.

Wenn Sie ein Objekt erstellen, erbt es von der Hauptobjektklasse. Wenn das Objekt erstellt wird, stammt der Overhead von der Tatsache, dass die benutzerdefinierte Klasse von Object erbt. Der Compiler muss bestimmte Methodenaufrufe im Speicher virtualisieren, so dass das Programm beim Aufruf .equals() oder .toString() weiß, welches Programm aufgerufen werden soll (dh die Klassen .equals() oder Object.equals()). Dies wird mit einer Nachschlagetabelle erreicht und zur Laufzeit mit Zeigern ermittelt.

Dies wird als Virtualisierung bezeichnet. Jetzt, in Java, ist ein Array tatsächlich ein Objekt, so dass Sie wirklich nicht viel von einem Array von Arrays bekommen. In der Tat könnten Sie besser Ihre eigene Klasse verwenden, da Sie die damit verbundenen Metadaten begrenzen können. Arrays in Java speichern Informationen über ihre Länge.

Viele der Sammlungen haben jedoch Overhead mit ihnen verbunden. ArrayList zum Beispiel wird die Größe selbst und speichert Metadaten über sich im Speicher, die Sie möglicherweise nicht benötigen. LinkedList hat Verweise auf andere Knoten, was einen Overhead zu seinen tatsächlichen Daten darstellt.

Nun, was ich sagte ist nur wahr über Java. In anderen OO-Sprachen verhalten sich Objekte auf der Innenseite anders, und einige können mehr/weniger effizient sein.

In einer Sprache wie C++, wenn Sie ein Array zuweisen, erhalten Sie wirklich nur eine Menge Speicher und es liegt an Ihnen, was Sie damit tun wollen. In diesem Sinne könnte es besser sein. C++ hat einen ähnlichen Overhead mit seinen Objekten, wenn Sie überschreiben (Schlüsselwort virtual), da es diese virtuellen Lookups im Speicher erstellt.

Answer 2

Alles hängt davon ab, wie effizient Sie den Speicherplatz nutzen und welche Zugriffsanforderungen Sie haben. Den Speicher beiseite zu legen, um ein 10.000 x 10.000 Array zu halten, um nur 10 Punkte zu speichern, wäre eine scheußliche Verschwendung von Speicher. Auf der anderen Seite ist das Speichern von Speicher durch Speichern der Punkte in einer verknüpften Liste auch sinnlos, wenn Sie so viel Zeit damit verbringen, die Liste zu durchlaufen, um den Punkt zu finden, den Sie tatsächlich in den 10.000.000 gespeicherten benötigen.

Einige der Nachteile von beidem können überwunden werden. Sparse Arrays, Vorsortieren der Liste nach einer Regel so "benötigt" Punkte nach oben, etc. ...

Answer 3

In den meisten Sprachen, Mit einem multidimensionalen Array sagen AxB, haben Sie nur ein Stück Speicher groß genug, um Halten Sie A * B Objekte, und wenn Sie ein Element (m, n) nachschlagen, müssen Sie nur das Element an der Stelle m * A + b finden. Wenn Sie eine Liste von Objekten haben, ist jeder Liste ein Overhead zugeordnet, und die Suche ist komplexer als eine einfache Adressberechnung.

Wenn die Größe Ihrer Matrix konstant ist, ist ein 2D-Array die schnellste Option. Wenn es wachsen und schrumpfen muss, haben Sie wahrscheinlich keine andere Möglichkeit als den zweiten Ansatz zu verwenden.