4. effiziente Abbildung symmetrische Matrix auf array

effiziente Abbildung symmetrische Matrix auf array

  • V

    Hi,
    Folgendes Problem:
    Ich habe numerierte ([1,n]) objekte, die zueinander (nicht zu sich selbst) in einer symmetrieschen Beziehung stehen.

    Das ganze ergibt dann eine Dreiecksmatrix ohne Diagonale

    n = 5:
  -> objekt j
  1 2 3 4 5   
1 # _ _ _ _  |  objekt i
2 # # _ _ _  v
3 # # # _ _
4 # # # # _
5 # # # # # 

# - nicht benötigtes Feld
_ - benötigtes Feld

    Das heißt der benötigte Speicherplatz ist
    n*(n-1)/2
    habn also ein Array
    T data[n*(n-1)/2]; // für n=5: 10

    mein Problen ist nun das mapping von i,j -> nach einem Arrayindex möglichst effektiv zu gestallten.

    den Versatz, der von der normalen Formel ( i*n+j ) abgeogen werden muss ist
    Die Summe Σx von x=1 bis i

    Ich hab schon ne weile überlegt, aber ich komme auf keine effiziente methode.
    möglichst also ohne Schleifen, und Divisionen

    0
  • B

    (i,j) wird abgebildet auf den Index $$\sum_{\mu=1}^{i-1} \mu + j - 1$$, also $$\frac{1}{2}i(i-1)+j-1$$. Da ist zwar eine Division drin, aber nur eine durch 2, die durch ein Bitshift implementiert werden kann.

    0
  • V

    Danke!

    so ganz scheint das nicht zu funktionieren.
    die formel sollte für folgende daten:
    i = [1,1,1,1,2,2,2,3,3,4];
    j = [2,3,4,5,3,4,5,4,5,5];
    eine von 0 aufsteigende sequenz ergeben. Raus kommt:
    1 2 3 4 3 4 5 6 7 10

    komme jetzt auf folgendes:

    f(i,j,n)=(i−1)(n−1)−i(i−1)2+j−2f(i,j,n) = (i-1)(n-1) - \frac{i(i-1)}{2} + j-2

    ist aber doch recht umständlich

    Edit:formel

    0
  • B

    vlad_tepesch schrieb:

    so ganz scheint das nicht zu funktionieren.

    Ups, ich habe nicht genau gelesen. Ich bin davon ausgegangen, dass wir eine untere Dreiecksmatrix mit Diagonale haben, hab also _ und # vertauscht.

    0
  • ?

    Nehmen wir an, wir haben folgende symmetrische Matrix:

    const int N = 5;
int Matrix[N][N] =
  {
	{0, 3, 2, 4, 5},
	{3, 0, 7, 1, 3},
	{2, 7, 0, 8, 9},
	{4, 1, 8, 0, 2},
	{5, 3, 9, 2, 0}
  };
// Speicherbedarf ist (N*N) (N=5; 32Bit OS int = 4 Byte; 100 Byte)

    Wie man sehen kann, sind die Werte oberhalb der Matrixdiagonalen gleich der Werte unterhalb. In diesem speziellen Fall ist Matrix(i,j) = Matrix(j,i) und wenn i=j, dann Matrix(i,j) = 0.
    Um Speicherplatz zu sparen lohnt es sich, die Matrix in ein 1D Array umzuwandeln. Wir speichern alle Werte oberhalb der Diagonalen inklusive der Diagonalen:

    1. Vereinfachung

    const int SIZE = N*(N+1)/2;
int Array[SIZE];
int index = 0;

for (int i=0; i<N; ++i)
{
  for (int j=i; j<N; ++j)
  {
[code]    Array[index] = Matrix[i][j];[/code]
    ++index;
  }
}
Array[0 3 2 4 5 0 7 1 3 0 8 9 0 2 0]
// Speicherbedarf ist (N*N-N)/2+N (N=5; 32Bit OS int = 4 Byte; 60 Byte)

    Da wir wissen, dass wenn i=j, der Matrixwert = 0 ist (alle Werte der Matrixdiagonalen sind 0), können wir das Array noch weiter vereinfachen:

    2. Vereinfachung

    const int SIZE = N*(N-1)/2;
int Array[SIZE];
int index = 0;

for (int i=0; i<N; ++i)
{
  for (int j=i+1; j<N; ++j)
  {
[code]    Array[index] = Matrix[i][j];[/code]
    ++index;
  }
}
Array[3 2 4 5 7 1 3 8 9 2]
// Speicherbedarf ist (N*N-N)/2 (N=5; 32Bit OS int = 4 Byte; 40 Byte)

    Bei der 2. Vereinfachung sparen wir also 60% des Speicherplatzes.
    Um nun wieder an die Werte der Matrix zu kommen, muss der Index des Arrays für die i und j Stelle der Matrix berechnet werden. Hierzu benutzt wir die Funktion:
    **
    1. Vereinfachung**

    int i = 2;
int j = 3;
int index = Trag_eq(i, j, N);
cout << Array[index] << endl; // Array[10] = 8

    **
    2. Vereinfachung**

    int i = 2;
int j = 3;

//Wenn i==j, dann gibt die Trag_noeq() -1 zurück,
//diesen Fall müssen wir abfangen.
if (i == j) cout << 0 << endl; 
else {
  int index = Trag_noeq(i, j, N);
  cout << Array[index] << endl; // Array[7] = 8
}

    Die Funktionen Trag_eq() und Trag_noeq() stammen aus diesem Artikel und werden dort noch genauer beschrieben:

    http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211

    int Trag_eq(int row, int col, int N)
{
   if (row <= col)
      return row*N - (row-1)*((row-1) + 1)/2 + col - row;
   else if (col<row)
      return col*N - (col-1)*((col-1) + 1)/2 + row - col;
}

    int Trag_noeq(int row, int col, int N)
{
   //assert(row != col);    //You can add this in if you like
   if (row<col)
      return row*(N-1) - (row-1)*((row-1) + 1)/2 + col - row - 1;
   else if (col<row)
      return col*(N-1) - (col-1)*((col-1) + 1)/2 + row - col - 1;
   else
      return -1;
}

    Das Berechnen des Indexes nimmt natürlich Rechenzeit in Anspruch. Beim direkten Zugriff auf die Matrix[i][j] entfällt dieser.

    Wir tauschen also Speicherplatz gegen Rechenzeit.

    Je nach Anwendungsfall muss man also abschätzen, welche Methode sinnvoller ist.

    Ich hoffe dem ein oder anderen hilft's 🙂

    0

  • Und wenn du den Wertebereich auf

    0...USHORT_MAX bzw. SHORT_MIN...SHORT_MAX

    begrenzen kannst, verwende statt <int> besser <short> und je nach Compiler spart das dann nochmal 50% Speicherplatz.

    0
Anmelden zum Antworten