Die Implementierung einer matrix, die effizienter ist, mit einem Array von Arrays (2D) oder ein 1D-array?

Bei der Implementierung einer Matrix-Konstrukt mit arrays, was wäre effizienter?
Mit einem 1D-array, oder ein array von arrays (2D)?

Ich würde denken, eine 2D-effizienter ist, als Sie bereits die X-und Y-Koordinaten eines Elements, wobei in einem 1D-Implementierung Sie müssen berechnen den index.

Edit: umgesetzt wird es mit Hilfe von Java

InformationsquelleAutor barfoon | 2009-04-09
  1. 12

    "Effizient" ist nicht eine catch-all-Begriff.

    Eines array-von-arrays-Lösung ist effizienter in Bezug auf die Lagerung, wo das array kann geringer Dichte (D. H., Sie können null-Zeiger zur Darstellung einer matrix-Zeile alles Nullen). Dies wäre (in C):

    int *x[9];

    wo jeder "int *" zugeordnet werden würde separat.

    Einem 2D-array (das ist nicht unbedingt ein array von arrays) werden in der Regel schneller (effizienter in Bezug auf Geschwindigkeit), da funktioniert das memory locations mit der Mathematik, die zimmerreserviereung, ohne das de-Referenz-Speicherplätze. Ich spreche von dem Konstrukt:

    int x[9][9];

    Einem 1D-array der form:

    int x[81];

    ist unwahrscheinlich, dass alle schneller sind als entsprechende 2D-version, da Sie noch zu tun, die Berechnungen an einem gewissen Punkt finden der richtigen Zelle (manuell im code anstatt der compiler es tun).

    Nach Bearbeiten, in dem sich die Java Hinzugefügt wurde als eine Anforderung:

    Ich glaube, dass Java 2D-arrays sind arrays von arrays Sorte (die benötigen zwei Speicher-Zugriffen im Gegensatz zu der einen Bedarf für ein 1D-array), so dass die 1D-array mit manueller index Berechnung kann auch schneller sein. Also, statt der Deklaration und Verwendung:

    int x[width][height];
x[a][b] = 2;

    können Sie mehr Geschwindigkeit mit:

    int x[width*height];
x[a*height+b] = 2;

    Sie müssen nur darauf achten, dass Sie nicht bekommen, die Formel gemischt wird, bis überall (d.h., nicht-swap 4 und 7 versehentlich).

    Diese Geschwindigkeit Unterschied wird, wie ich denke, Java ist codiert, unter der Decke, so dass ich könnte falsch sein (aber ich bezweifle es :-). Mein Rat ist, wie immer, zur Optimierung Fragen, Messen, nicht schätzen!

    • +1 für "effiziente nicht eine catch-all-phrase" denken Sie Daran, dass .NETTO-Optimierungen für jagged-arrays, die nicht arbeiten für mehrdimensionale zum Beispiel.
    • In Java-1D-array ist wahrscheinlich schneller, da das 2D-Array erfordert mindestens zwei Speicherkarten liest (keine Berechnung, obwohl).
    • Ich würde vorsichtig sein, Annahmen zu machen. Zum Beispiel, wenn Sie das Durchlaufen einer Zeile des 2D-Arrays, Java vielleicht optimieren aus der index-lookups wheares mag es nicht, wenn Sie die Durchführung einer Berechnung in den index mit einem 1D-array).
    InformationsquelleAutor paxdiablo
  2. 3

    Ich werde zu brechen Reihen mit den Antworten zu Datum und schlage vor, den folgenden Grund, dass ein 1D-array ist sehr wahrscheinlich schneller.

    Einem 2D-array beinhaltet 2 Speicherzugriffe. A[x][y] zum Beispiel muss zuerst Eine lookup - [x], und führen Sie dann eine weitere Suche aus, dass array[y].

    1D-Umsetzung traditionell wäre Ein[x + (Breite *y)]. Bei der Breite wird in Registern (oder ein literal), das bedeutet 2 Mathe-ops und 1-lookup statt 2-lookups. Lookups sind Größenordnungen langsamer als Mathe-ops, also wenn die Breite ist im register selbst ein kleiner Prozent der Zeit, oder ist ein literal, es wird schneller sein.

    Natürlich die standard-Vorsichtsmaßnahmen anwenden. Immer profile, und vermeiden vorzeitige Optimierungen.

    • Umsetzung eines 2D-Arrays hängt von der Sprache, ist es nicht unbedingt ein array von arrays. x[9][9] kann x[81] unter den decken, das wird NICHT anders sein, als Sie das deklarieren von x[81]. Der Unterschied ist nur, ob der code oder der compiler nicht die Mathematik zu finden, die die Zelle.
    • Eigentlich dachte, ich würde besser überprüfen. Unter gcc, "int x[9][9];x[5][4] = 7;" kompiliert unten auf "movl $7,-148(%ebp)", eine Feste Position im stack-frame. So ist es zumindest nicht tun, zwei memory-Referenzen. Wieder, es hängt von der Sprache und compiler.
    • Vereinbart, es ist höchst Sprache/compiler-abhängig. Ich nehme Sie aber, dass diese Matrizen wäre dynamisch zugewiesen, so dass Ihr test ist nicht was ich mir vorstelle, was der OP im Sinn hatte.
    InformationsquelleAutor patros
  3. 2

    Ich glaube nicht, dass diese Frage beantwortet werden kann , ohne tatsächlich zu schreiben, Beispiel-code und die Prüfung der Ergebnisse. Zum Beispiel diese Frage fanden die folgenden Ergebnisse.

    sum(double[], int): 2738 ms (100%)
sum(double[,]):     5019 ms (183%)
sum(double[][]):    2540 ms ( 93%)

    Jagged-arrays, die am schnellsten, gefolgt von einer 1-dimensionalen arrays, gefolgt von mehrdimensionalen arrays. Jagged-arrays, die am schnellsten ist wahrscheinlich nicht das, was vorhergesagt hätten. Diese Ergebnisse sind wahrscheinlich unbrauchbar für Java seit Java hat verschiedene Optimierungen (und keine mehrdimensionalen arrays in Java).

    Würde ich sehr vorsichtig sein, Annahmen zu machen. Zum Beispiel, wenn Sie das Durchlaufen einer Zeile des 2D-Arrays, Java vielleicht optimieren aus der index-lookups oder out-of-bounds checking wheares es möglicherweise nicht in der Lage, wenn Sie ein 1D-array mit inline-index-Berechnungen.

    Schlage ich vor, schreiben ein einfaches Programm zum testen der Geschwindigkeiten auf die gewünschte Plattform.

    InformationsquelleAutor Laplie Anderson
  4. 1

    Je nach Sprache gibt es keinen Unterschied. Die eigentliche Frage ist, wie die 2D-matrix zugeordnet ist. Ist es zu einem einzigen zusammenhängenden Raum X*Y bytes, oder ist es zugeordnet, wenn Y unabhängige arrays von X-Größe. Letzteres erfolgt in der Regel beim erstellen von sparse-Matrizen.

    • es wird in java implementiert
    InformationsquelleAutor MadCoder
  5. 0

    Dem kommerziellen finite-element-Paket, das ich während meiner Karriere als Maschinenbau-Ingenieur mit einem 1D-array als Grundlage für seine lineare algebra Berechnungen. Finite-element-Methoden führen zu matricies, die sind groß, Dünn, und gebändert. Die Speicherung all diejenigen, die null Elemente außerhalb der band, machte keinen Sinn.

    Die einzige Zeit, die Sie sehen 2D-arrays verwendet, ist für die kleinen, schulischen Problemen oder solche, die sich nicht mit (z.B., boundary-Elemente-Methoden).

    InformationsquelleAutor duffymo
  6. 0

    Im Allgemeinen Fall die effizienteste Implementierung für jeden Algorithmus ist die eine, die am wenigsten code. Dies ist aus vielen Gründen:

    • Weniger code -> weniger Zeit, es zu schreiben,
    • Weniger code bedeutet weniger bugs (da bugs pro KLOC ist ziemlich konstant für eine gegebene Programmierer), die sind leichter zu finden (da Sie sich nicht verstecken, auch in wenigen Zeilen code)
    • Wenn dein Algorithmus ist nicht fit für die Aufgabe, es ist leichter zu ersetzen, wenn es 10 Zeilen anstelle von 100
    • Eine kompakte Umsetzung in der Regel führt zu sauberen Schnittstelle, die das macht der code, der verwendet die Bibliothek sauber (also der Effekt multipliziert). Dies kann auch dazu führen, eine komplexere Bibliothek Umsetzung, wenn das macht der client-code mehr effizient (d.h. Sie konzentrieren sich die Bemühungen in einer einzigen Ort, um alles, was sonst einfacher).

    Es hängt auch viel davon ab die Zugriffsmuster. Haben Sie immer zu Fuß die gesamte matrix? Ist es spärlich? Bevorzugen Sie zu verarbeiten, Zeilen oder Spalten?

    Im Extremfall (matrix mit Milliarden von Zeilen und Spalten mit nur 10 Zellen genutzt), ein HashMap effizienter sein kann, als jede array-Implementierung. Für andere Probleme kann es effizienter sein, die Mischung der Ansätze, die je nach Fragestellung (zum Beispiel ein HashMap von arrays von mini-Matrizen, wenn die Zellen "Klumpen" in einer gigantischen leeren Raum).

    Wenn Ihr Probleme, fragt zum suchen einer Zeile/Spalte und dann zu verarbeiten, die Werte, könnte es effizienter sein, ein 2D-Ansatz, so ist der erste Zugriff auf ein array zurückgibt, die Sie dann verarbeiten, ohne sich über die Grenzen, ein-off-Fehler, etc.

    InformationsquelleAutor Aaron Digulla
Schreibe einen Kommentar