Speichern von Matrizen in Maps günstiger als in Arrays?

[Milo]

Hallo,

ich rechne mit Matrizen, die sehr groß sind. Ich habe dabei das Problem, das ich schnell mal an die Grenzen des Speichers stoße. Derzeit halte ich alle Matrizen in 2D-double-Arrays. Ich weiß von einigen Matrizen, dass sie viele Nullen bzw. reine Diagonalmatrizen sind. Nun habe ich mir überlegt, dass ich ja nicht notwendigerweise die Nullelemente auch speichern muß - sparse-Matrix.

Wenn ich nun alle Matrizen in Maps ablegen würde, könnte man die Spalte und Zeile über den Schlüssel auslesen:

LinkedHashMap A = new LinkedHashMap();
A.put("1,3") = 1.2345;

Was mich nun interessiert, ist dies wirklich günstiger gerade auch weil ich hier den Schlüssel als String ablege? Welche Alternativen habe ich ggf. noch?


Gruß Micha

 

[Gelöschtes Mitglied 5909]

eine hashmap hat intern ein sehr grßes array und braucht von hausaus relativ viel speicher

aber was machst du bitte dass du den speicher mit 2d arrays sprengst?

aber wenn du das wirklich brauchst erhöh den Speicher
über den VM parameter

-Xmx128m
(128 MB)

 

[didjitalist]

Ich würd mir drei Implementierungen einer Matrixklasse vorhalten:
1. diagonal
2. "normal"
3. sparse
Diagonale NxN Matrizen lassen sich sehr simpel durch ein eindimensionales Array der Länge N repräsentieren. Für normale entweder ein- oder zwei-dimensionale Arrays. Für sparse würd ich auf lineare Suche setzen. Das macht Zugriffe zwar u.U. langsam, aber wenn die Matrix wirklich sehr dünn besiedelt ist, wird es kaum ins Gewicht fallen. Und zur Not kann man sich auch noch nen guten Suchalgorithmus reinstricken. Pattern ist ungefähr so:

public class SparseMatrix
{
   private int[] indices;
   private double[] values;

  public void set( int x, int y, double value )
  {
     int index = getIndex( x, y );
     setValue( index, value );
  }

  public double get( int x, int y )
  {
     int index = findIndex( x, y );
     return getValue( index );
  }
}

 

[Milo]

Hallo,

@raiL, die Berechnung ist recht groß (bzw. die Matrizen sind es) und ich brauche im Moment -Xmx1600 (also 1.6GB), damit er rechnet. Ich weiß auch, dass das Problem bei den Matrizen liegt und wollte daher hier zunächst anfangen Speicher zu sparen.

@didjitalist, als bzw. in was speichere ich dann den Wert bei sparse-Matrizen? Dein Beispielcode gibt das irgendwie nicht her.

Bei Maps kann ich auch den Speicher vorgeben, wenn ich das richtig sehe. Die Dimensionen der Matrix kenne ich ja vorher. Es müsste als kein zusätzlicher Speicher bereitgestellt werden (default afaik 75%).

Gruß Micha

 

[didjitalist]

Um in eine NxN Matrix in einem eindimensionalem Array zu speichern, kann man den sich den offset wie folgt berechnen: offset( x, y ) := y * N + x
Die Grundidee ist jetzt, sich zwei Listen vorzuhalten. Eine Liste beinhaltet die offset-Werte, die andere die Werte der Matrix. Wird ein Wert eingefügt, so wird sein offset berechnet und dessen Index in der Liste der offsets bestimmt. Der Wert wird in die Wert-Liste an eben diesem Index eingefügt, sofern er ungleich 0 ist. Somit belegt die Matrix nur ungefähr soviel Speicher, wie auch Positionen besetzt sind. Allerdings zu dem Nachteil langsamerer Schreib- und Lesezugriffe.

 

[Milo]

Hi,

in was speichere ich die Werte? In 3 Arrays row, col, value oder an was dachstest Du?

Gruß Micha

 

[Gast]

Du kannst es so speichern, dass du nur zwei eindimensionale arrays hast. Und zwar musst du dein zweidimensionales Array in einem eindimensionalen Array spaltenweise speichern. Dann kürzt du es in dem du alle Nullen rauslöschst, musst aber im zweiten Array die Indezes der Einträge speichern, die keine Nullen haben

 

[Milo]

Hi,

aha, ich verstehe. Deine Formel

offset( x, y ) := y * N + x

ist aber nur für quadratische Matrizen gültig. Gehts allg.?

offset( x, y ) := y * N*M + x

Die Berechnungen sind im Übrigen nicht zeitkritisch, sodass es auf ein paar Stunden nicht ankommt ;-)

Gruß Micha

 

[Milo]

Hi,

ich denke, ich habs:

i*N+i*M+j

Gruß
Micha

 

[Milo]

Hi,

ich noch mal ;-)

Da ich ja am Anfang nicht weiß, wo überall Nullen stehen, müsste ich die Werte ja doch in einer Liste speichern, oder?

Micha

 

[Marco13]

Hi,

aha, ich verstehe. Deine Formel

offset( x, y ) := y * N + x

ist aber nur für quadratische Matrizen gültig. Gehts allg.?

Das müßte auch für nicht-quadratische gelten.

offset( x, y ) := y * N*M + x

DAS ist aber eher Unfug.


Falls ich nicht was übersehen habe....

 

[Milo]

Hi,

die Formel habe ich ja schon korrigiert. Die andere gilt nur bei quadratischen Matrizen

N = 2
M = 4

1*N+1 = 3
1*N+2 = 4
1*N+3 = 5
1*N+4 = 6

2*N+1 = 5 ***
2*N+2 = 6 ***
2*N+3 = 7
2*N+4 = 8

daher:

       private int getKey(int rowIndex, int colIndex) {
               if (this.row < this.col)
                  return rowIndex*Math.max(this.row,this.col)+colIndex
               return rowIndex*Math.min(this.row,this.col)+colIndex
       }

DIe Multiplikation dürfte auch gehen, erzeugt aber große Zahlen.

Was mich im Moment jedoch interessiert ist:

Da ich ja am Anfang nicht weiß, wo überall Nullen stehen, müsste ich die Werte ja doch in einer Liste speichern, oder?

Gruß Micha

 

[Marco13]

Falls du mit "korrigiert" das hier meinst:
i*N+i*M+j
das ist auch unfug.

Und die Sache mit der MxN-Matrix ... auf die Idee, mal M statt N zu verwenden, bist du nicht gekommen? :wink: (Abgesehen davon, dass man bei 0 zu zählen anfängt....)

Man müßte jetzt noch unterscheiden, ob man "row-major" oder "column-major" speichern will, aber

rows = 4
cols = 2

0 1 
2 3
4 5 
6 7

index = r * cols + c

bzw.

rows = 4
cols = 2

0 4 
1 5
2 6 
3 7

index = c * rows + r

Die zitierte Frage ... ja. Dünn besetzte Matrizen und Diagonalmatrizen treten in den verschiedensten Bereichen SEHR häufig auf, und da geht es dann teilweise eben auch um welche, die Größen von 10Million x 10Million haben und locker etliche GB Speicher brauchen. Deswegen haben sich da schon SEHR viele SEHR schlaue Leute Gedanken drüber gemacht - ein Eisteigspunkt wäre also z.B. http://en.wikipedia.org/wiki/Sparse_matrix_representation , dort findet man allgemeine Informationen, welche Möglichkeiten es da gibt. Wenn es etwas vorgefertigtes sein soll, findet man vielleicht http://ressim.berlios.de/ oder so, aber verwendet hab' ich das noch nicht.

 

[Milo]

Hallo,

auf die Idee, mal M statt N zu verwenden, bist du nicht gekommen?

Wie Du meinem letzten posting entnehmen konntest, bin ich auf eine zufriedenstellende Lösung gekommen, ja.
(Das Min/Max kann man sich klemmen, da dies die Bedingung ja bereits prüft). Wobei der Index eigentlich das kleinere Problem ist, denn Ausgangspunkt meiner Frage und des Threads war: In was speichere ich die Matrizen. Also wie realisiere ich die Datenhaltung selbst. Für die paar Matrizenoperationen, die ich benötige, wollte ich keine extere Bibliothek verwenden, die das Program unnötig aufbläht. Ich benötige lediglich Addieren/Subtrahieren, Multiplizieren, Transponieren und Invertieren. Da ich die für normale Arrays schon habe, wäre eine übertragung also auch recht einfach möglich, wenn das Grundproblem - die Datenhaltung - geklärt wäre.

Frag ich mal andersherum: In Maps ist die Speicherung eher ungünstig. Ist sie in Listen ähnlich schlecht? Die Arrays permanent zu vergrößern, indem man ein neues (größeres) anlegt und das alte zerstört, wenn ein weiteres Nicht-Null-Element hinzukommt, halte ich auch für zweckfremd. Hier wäre ich für Anregungen dankbar!

Schöne Grüße
Micha

 

[Marco13]

Bei dem min/max-Zeug musst du aufpassen, dass das ganze wirklich eindeutig bleibt.

Die Operationen sind an sich einfach. Bis auf Invertieren. Das ist schon Hardcore, und ... insbesondere ist die Inverse einer dünn besetzten 1000x1000-Matrix i.a. NICHT dünn besetzt, d.h. das wird schon aufwändig.

In jeden Fall sollte man sich eine abstrakte Klasse/Interface für die Matrix machen, dann kannst du nachträglich die Implementierung ändern, ohne dass sich am übrigen Code was ändert.

Mögliche Implementierungen findest du dann zum Beispiel hier: http://www.netlib.org/linalg/html_templates/node90.html

Das mit den Arrays ist aber nicht so abwegig. Wenn man schon weiß, wie viele Elemente nicht 0.0 sind, sowieso (das weißt du ja aber nicht), aber auch sonst. Wenn man eine Möglichkeit braucht, "beliebige viele" Float-Elemente zu speichern, dann gibt es verschiedene Möglichkeiten. Eine wäre eine List<Float> (d.h. LinedList<Float> oder ArrayList<Float>) aber die ist für numerische Anwendungen ungünstig, weil das Autoboxing/Autounboxing (d.h. die Umwandlung zwischen "float" und "Float") sehr ineffizient ist.

Für deinen Fall könnte es sinnvoll sein, dir eine "IntArrayList" und eine "FloatArrayList" zu bauen. Also Klassen, die zwar intern einen int- oder float-Array verwenden, aber diese Arrays automatisch vergrößern, wenn das notwendig ist. Ggf. kannst du dir die Implementierung von ArrayList ansehen, und die entsprechend anpassen.

 

[Milo]

Hi Marco,

ich werde heute Abend, wenn ich zu hause bin, mal meinen bis jetzt entstandenen Code posten. Dann kannst Du ja einen Blick drauf werfen und mal entsprechend rezensieren ;-)

Im Moment habe ich es über zwei ArrayListen realsiert - eine für den Schlüssel und eine für die Werte, so wie didjitalist das vorschlug.

Zwei Methoden getValueAt/setValueAt existieren und machen das ganze soweit unabhängig von der Datenhaltung - ein Interface ware hier sicher noch ein Tick geschickter. Solange ich auch innerhalb der Klasse auf diese Hol- und Zuweisungsmethoden zurückgreife, sollte man am Rest was ändern können. Ich denke, soweit entspreche ich Deinem Hinweis schon.
Die nicht Null-Elemente kenne ich nicht vorher bzw. nicht bei allen Matrizen, daher wird es da schwierig, schon vorher auf die Größe zu kommen.

Wenn ich Dich richtig verstanden habe, dann ist eine solche Lösung:

int A[] = {2,3,5,7,11 };
int B[] = new int[A.length+1];
System.arraycopy(A,0,B,0,A.length);

eine akzeptable Lösung für jedes neue Element?


Gruß Micha

 

[Marco13]

Jein. Das geht ist aber ineffizient. Wenn man 8 Elemente nacheinander einfügt, muss man

1. 1 Einfügen
2. 1 Einfügen, 1 Kopieren
3. 1 Einfügen, 2 Kopieren
4. 1 Einfügen, 3 Kopieren
5. 1 Einfügen, 4 Kopieren
6. 1 Einfügen, 5 Kopieren
7. 1 Einfügen, 6 Kopieren
8. 1 Einfügen, 7 Kopieren

D.h. das Einfügen von n Elementen hat Laufzeit O(n^2).

In solchen Fällen ist es besser, den Array immer um einen konstanten Faktor zu vergrößern. Man könnte z.B. jedes mal, wenn der Array zu klein wird, die größe des Arrays verdoppeln. Dann hätte man bei 6 Elementen

1. 1 Einfügen, Arraygröße 1
2. 1 Einfügen, 1 Kopieren, Arraygröße 2
3. 1 Einfügen, 2 Kopieren, Arraygröße 4
4. 1 Einfügen
5. 1 Einfügen, 4 Kopieren, Arraygröße 8
6. 1 Einfügen
7. 1 Einfügen
8. 1 Einfügen

Dort hat das Einfügen von n Elementen dann Laufzeit O(n)
Bei der ArrayList wird das übrigens auch so gemacht.

 

[Milo]

Hallo,

okay. Ich habe mal ein wenig gegoogelt. Man findet ja einige Ideengeber für die Implementierung von Listen.

Meine Matrixklasse habe ich nun so aufgebaut

import java.lang.IndexOutOfBoundsException;
import java.util.Locale;


public class SparseMatrix extends Matrix {

     private final int row,
                       col;
       
     private IntArrayList    indices  = new IntArrayList();
     private DoubleArrayList elements = new DoubleArrayList();
     public SparseMatrix (int row, int col)  {
          super(row, col);
          this.row = super.getRowCount();
          this.col = super.getColumnCount();
     }
       
     private int getKey(int rowIndex, int colIndex) {
          return rowIndex*this.col+colIndex;
     }
       
       
     private int getIndexOf(int key) {
          for (int i=0; i<this.indices.size(); i++)
               if (this.indices.get(i) == key)
                    return i;
          return -1;
     }
       
     @Override
     public void setValueAt(int rowIndex, int colIndex, double value) throws IndexOutOfBoundsException {
          if (rowIndex < 0 || colIndex < 0)
               throw new IndexOutOfBoundsException(this.getClass() +
               " Index muessen groesser Null sein! " +
               ((rowIndex < 0)?rowIndex:colIndex));
          else if (rowIndex >= this.row || colIndex >= this.col)
               throw new IndexOutOfBoundsException(this.getClass() +
               " Index ueberschreitet Matrixdimentsion! " +
               ((rowIndex >= this.row)?rowIndex:colIndex));
          if (value == 0.0)
               return;
                 
          int key = this.getKey(rowIndex, colIndex);
          int index = this.indices.indexOf( key );

          if (index < 0) {
               this.elements.add( value );
               this.indices.add( key );
          }
          else
               this.elements.add( index, value );

     }
       
     @Override
     public double getValueAt(int rowIndex, int colIndex) throws IndexOutOfBoundsException {
          if (rowIndex < 0 || colIndex < 0)
               throw new IndexOutOfBoundsException(this.getClass() +
               " Index muessen groesser Null sein! " +
               ((rowIndex < 0)?rowIndex:colIndex));
          else if (rowIndex >= this.row || colIndex >= this.col)
               throw new IndexOutOfBoundsException(this.getClass() +
               " Index ueberschreitet Matrixdimentsion! " +
               ((rowIndex >= this.row)?rowIndex:colIndex));

          int key = this.getKey(rowIndex, colIndex);
          int index = this.indices.indexOf( key );
             
          if (index < 0)
               return 0.0;
                 
          return this.elements.get(index);
     }

// weitere Operationen
}

Ich hoffe das sieht nicht zu konfus aus ;-)

Ich dachte nun, ich könnte eine all. Matrix Klasse erzeugen für vollbesetzte Matrizen und eine für dünnbesetzte. Letztere sollte von der anderen erben.

Kann ich erreichen, dass ich nicht alle Methoden doppelt erstellen muß?

Beispiel addieren einer Zahl:

public Matrix sum (double d) {
          Matrix R = new Matrix(this.row, this.col);
          for (int rowIndex=0; rowIndex<this.row; rowIndex++)
               for (int colIndex=0; colIndex<this.col; colIndex++)
                    R.setValueAt(rowIndex, colIndex, this.getValueAt(rowIndex, colIndex) + d);
          return R;
     }

Die selbe Methode würde auch für Objekte der Klasse SparseMatrix gelten. Da SparseMatrix von Martix erbt, steht dieser auch die Methode sum zur Verfügung aber der Rückgabetyp ist eine (vollbesetzte) Matrix; das ist ja eher unschön. Kann ich dies nur um gehen, indem ich selbige Methode auch explizit in SparseMatrix erzeuge?

public SparseMatrix sum (double d) {
          SparseMatrix R = new SparseMatrix(this.row, this.col);
          for (int rowIndex=0; rowIndex<this.row; rowIndex++)
               for (int colIndex=0; colIndex<this.col; colIndex++)
                    R.setValueAt(rowIndex, colIndex, this.getValueAt(rowIndex, colIndex) + d);
          return R;
     }

Schöne Grüße Micha

 

[Marco13]

Hm :? dort wird bei jedem Zugriff auf irgendein Element "indices.indexof" aufgerufen - das ist ziemlich teuer. Das müßte sich doch irgendwie vermeiden lassen? ???:L
Wie auch immer.

Das Problem mit den Rückgabetypen usw. kann man zum Biespiel(!) lösen, indem man in der Matrix-Klasse eine abstrakte protected-Methode "createMatrix" o.ä. anbietet. Die ist in abgeleiteten Klassen so implementiert, dass immer der passende Typ zurückgegeben wird. (Ggf. gibt's auch andere Lösungen, aber das ist recht einfach und naheliegend)

 

[Milo]

Hallo Marco,

Hm :? dort wird bei jedem Zugriff auf irgendein Element "indices.indexof" aufgerufen - das ist ziemlich teuer. Das müßte sich doch irgendwie vermeiden lassen? ???

Ich bin für Ideen offen. Arrays lassen sich besser mit binarySearch durchsuchen, jedoch gilt dies eben nur für sortierte Arrays, was ich ja nicht habe. Eine bessere Suchstrategie wäre vermutlich nötig, um den Index des Schlüssels zu bekommen.

Das war übrigens auch der Grund, warum ich Maps nutzen wollte. Dort hätte man den Index und den Schlüssel gleich setzen können zB durch eine Kommazahl in der Art

map.put(2.4, 3.14);

, wobei der Wert in Zeile 2 und Spalte 4 steht. Mit containsKey() könnte man prüfen, ob es den Inde gibt und mit get() ihn ggf. holen.
Ist dies nun besser auch im Sinne von Speicherschonender?

Das Problem mit den Rückgabetypen usw. kann man zum Biespiel(!) lösen, indem man in der Matrix-Klasse eine abstrakte protected-Methode "createMatrix" o.ä. anbietet.

Das habe ich nicht ganz verstanden aber ggf. durch probieren doch richtig umgesetzt. Meinets Du so?

abstract class Matrix {

  private final int row, col;
  public Matrix(int row, int col) {
    this.row = row;
    this.col = col;
  }
  abstract protected Matrix createMatrix(int row, int col);

  abstract double getValueAt(int rowIndex, int colIndex);
  abstract void setValueAt(int rowIndex, int colIndex, double value);

  public Matrix sum (double d) {
      Matrix R = createMatrix(this.row, this.col);
          for (int rowIndex=0; rowIndex<this.row; rowIndex++)
               for (int colIndex=0; colIndex<this.col; colIndex++)
                    R.setValueAt(rowIndex, colIndex, this.getValueAt(rowIndex, colIndex) + d);
          return R;


  }
}

public class SparseMatrix extends Matrix {

  public SparseMatrix(int row, int col) {
    super(row, col);
  }
  
  public double getValueAt(int rowIndex, int colIndex) {
   // ToDo
    return 0.0;
  }
  
  public void setValueAt(int rowIndex, int colIndex, double value) {
    // ToDo
  }

  public SparseMatrix createMatrix(int row, int col) {
    return new SparseMatrix(row, col);
  }


}

Ist es das, was Dir vorschwebte?

Schöne Grüße Micha

 

[Marco13]

Ideen hab' ich keine direkten - ich habe jetzt nicht nachvollzogen, welches Speicherungsschema du verwendest, aber es gibt sicher auch Schemata, bei denen man nicht bei jedem Zugriff in einem Array suchen muss.

Eine Möglichkeit wäre auch die Map. (Die habe ich ja nie grundsätzlich in Frage gestellt). Als Key dann eine double-Zahl zu verwenden wäre aber nicht so gut, da kann man sich Probleme mit Rundungsfehlern einhandeln. Man könnte entweder mehrere ineinander verschachtelte (d.h. "mehrdimensionale") Maps verwenden, oder sich eine Klasse "IntTuple2" machen, die 2 Indizes enthält, oder (was evtl. effizienter wäre) man verwendet einen "long" als Key und berechnet den aus den beiden indizes über
long key = ((long)a << 32L) | (long)b;
oder, oder, oder... es gibt imer viele Möglichkeiten.

Zu dem createMatrix: Genau so meinte ich das. Jetzt kann man sowas machen wie

Matrix a = new SparseMatrix(...);
Matrix b = a.sum(5);

Die Matrix b ist jetzt eine SparseMatrix.

Das ist insbesondere praktisch, weil es ja jetzt in Zukunft noch mehr Klassen geben könnte:
class SparseMatrixWithArrays extends Matrix
class SparseMatrixWithMap extends Matrix
class SparseMatrixWithCRS extends Matrix
class SparseMatrixWithRCRS extends Matrix
class SparseMatrixWithJDS extends Matrix
....

Die sollte man ALLE IMMER nur als "Matrix" kennen. Wenn man dann ein Programm hat

Matrix a = new SparseMatrixWithArrays();
Matrix b = a.add(5);
Matrix c = a.add(b);
Matrix d = c.invert();
Matrix e = d.add(a);

kann man das Laufen lassen und sehen, wie effizient es ist. Und dann kann man einfach die erste Zeile ändern in

Matrix a = new SparseMatrixWithMap();

und der restliche Code bleibt unverändert und man kann sehen, ob es mit dieser anderen SparseMatrix-Implementierung effizienter ist.

 

[Milo]

Hi,

zunächst Dank für Deine Erklärung! Den Schlüssel könnte man auch als long oder int ablegen, so wir er auch im Moment berechnet wird - klar. Die Fließkommazahl war nur eine Idee. Die Zerlegung wäre ja auch einfach mit casten und modularen Operationen.
Gut, dann versuch ich doch mit einer MAP. ;-)

Gruß Micha

 

[Milo]

Hi,

ich denke, mit der HashMap ist das Problem für mich elegant gelöst. Danke für Deine Erklärungen!

Gruß Micha