verlinkte 2D-Matrix in C#

Question

Ich brauche dieses Szenario in C# implementieren:

Die Matrix sehr groß sein wird, vielleicht 10000x10000 oder größer. Ich werde dies für die Entfernungsmatrix im hierarchischen Clustering-Algorithmus verwenden. In jeder Iteration des Algorithmus sollte die Matrix aktualisiert werden (2 Reihen in 1 und 2 Spalten in 1). Wenn ich einfache doppelte [,] oder doppelte [] [] Matrix verwende, sind diese Operationen sehr "teuer". Bitte, kann jemand vorschlagen C# Implementierung dieses Szenarios?

Answer 1

Haben Sie einen Algorithmus im Moment? Und was meinst du mit teuer? Speicher oder Zeit teuer? Wenn Speicher teuer ist: Es gibt nicht viel, was Sie in C# tun können. Sie können jedoch in Erwägung ziehen, die Berechnung in einer Datenbank mit temporären Objekten auszuführen. Wenn es Zeit kostet: Sie können die Parallelität verwenden, um Spalten und Zeilen zu verbinden.

Aber abgesehen davon denke ich, ein einfaches Array double[,] ist die schnellste und speicherschonende Möglichkeit, die Sie in C# erhalten können, da der Zugriff auf die Array-Werte eine o (1) -Operation ist und Arrays den geringsten Speicher- und Verwaltungsaufwand haben. verglichen mit Listen und Wörterbüchern).

Answer 2

Wie bereits erwähnt, wird ein einfaches double [,] der effektivste Weg sein, dies in C# zu handhaben.

Denken Sie daran, dass C# oben auf dem verwalteten Speicher sitzt, und als solche weniger feinkörnigen Kontrolle über niedrige Ebene (in Bezug auf Speicher) Operationen im Gegensatz zu etwas wie grundlegende C. Erstellen Sie Ihre eigenen Objekte in C#, um Funktionalität hinzuzufügen verwendet in diesem Szenario nur mehr Speicher und verlangsamt wahrscheinlich auch den Algorithmus. Wenn Sie noch keinen Algorithmus ausgewählt haben, scheint CURE eine gute Wette zu sein. Die Wahl des Algorithmus kann sich auf die Wahl der Datenstruktur auswirken, aber das ist nicht wahrscheinlich.

Sie werden feststellen, dass der Algorithmus die theoretischen Grenzen von "Kosten" auf jeden Fall bestimmt. Zum Beispiel werden Sie lesen, dass Sie für CURE an eine O (n2 log n) Laufzeit und O (n) Speicherverbrauch gebunden sind.

Ich hoffe, das hilft. Wenn Sie mehr Details zur Verfügung stellen können, können wir möglicherweise weiter helfen!

N.

Answer 3

Es ist nicht möglich, ‚merge‘ zwei Zeilen oder zwei Spalten, dann würden Sie die ganze Matrix in eine neue kopieren müssen, kleinere, die in der Tat inakzeptabel teuer ist.

Sie sollten wahrscheinlich nur die Werte in einer Zeile zum vorherigen hinzufügen und dann die Werte ignorieren, so als ob sie entfernt wurden.

die Arrays von Arrays: double [] [] ist tatsächlich schneller als double [,]. Aber braucht mehr Speicher.

Die gesamte Array Sache Verschmelzung möglicherweise nicht erforderlich, wenn Sie die algoritm etwas ändern, aber dies könnte helfen, u:

public static void MergeMatrix() 
    { 
     int size = 100; 
     // Initialize the matrix 
     double[,] matrix = new double[size, size]; 
     for (int i = 0; i < size; i++) 
      for (int j = 0; j < size; j++) 
       matrix[i, j] = ((double)i) + (j/100.0); 

     int rowMergeCount = 0, colMergeCount = 0; 
     // Merge last row. 
     for (int i = 0; i < size; i++) 
      matrix[size - rowMergeCount - 2, i] += matrix[size - rowMergeCount - 1, i]; 
     rowMergeCount++; 
     // Merge last column. 
     for (int i = 0; i < size; i++) 
      matrix[i, size - colMergeCount - 2] += matrix[i, size - colMergeCount - 1]; 
     colMergeCount++; 

     // Read the newly merged values. 
     int newWidth = size - rowMergeCount, newHeight = size - colMergeCount; 
     double[,] smaller = new double[newWidth, newHeight]; 
     for (int i = 0; i < newWidth; i++) 
      for (int j = 0; j < newHeight; j++) 
       smaller[i, j] = matrix[i, j]; 

     List<int> rowsMerged = new List<int>(), colsMerged = new List<int>(); 
     // Merging row at random position. 
     rowsMerged.Add(15); 
     int target = rowsMerged[rowMergeCount - 1]; 
     int source = rowsMerged[rowMergeCount - 1] + 1; 
     // Still using the original matrix since it's values are still usefull. 
     for (int i = 0; i < size; i++) 
      matrix[target, i] += matrix[source, i]; 
     rowMergeCount++; 

     // Merging col at random position. 
     colsMerged.Add(37); 
     target = colsMerged[colMergeCount - 1]; 
     source = colsMerged[colMergeCount - 1] + 1; 
     for (int i = 0; i < size; i++) 
      matrix[i, target] += matrix[i, source]; 
     colMergeCount++; 

     newWidth = size - rowMergeCount; 
     newHeight = size - colMergeCount; 
     smaller = new double[newWidth, newHeight]; 
     for (int i = 0, j = 0; i < newWidth && j < size; i++, j++) 
     { 
      for (int k = 0, m = 0; k < newHeight && m < size; k++, m++) 
      { 
       smaller[i, k] = matrix[j, m]; 
       Console.Write(matrix[j, m].ToString("00.00") + " "); 

       // So merging columns is more expensive because we have to check for it more often while reading. 
       if (colsMerged.Contains(m)) m++; 
      } 

      if (rowsMerged.Contains(j)) j++; 
      Console.WriteLine(); 
     } 

     Console.Read(); 
    } 

Answer 4

In diesem Code verwende ich zwei 1D-Helferlisten den Index in einem großen berechnen Array mit den Daten. Löschen von Zeilen/Spalten ist wirklich billig, da ich nur diesen Index aus den Helferlisten entfernen muss. Aber natürlich bleibt der Speicher in dem großen Array, d. H. Abhängig von Ihrer Verwendung haben Sie ein Speicherleck.

public class Matrix 
{ 
    double[] data; 
    List<int> cols; 
    List<int> rows; 

    private int GetIndex(int x,int y) 
    { 
     return rows[y]+cols[x]; 
    } 

    public double this[int x,int y] 
    { 
     get{return data[GetIndex(x,y)];} 
     set{data[GetIndex(x,y)]=value;} 
    } 

    public void DeleteColumn(int x) 
    { 
     cols.RemoveAt(x); 
    } 

    public void DeleteRow(int y) 
    { 
     rows.RemoveAt(y); 
    } 

    public Matrix(int width,int height) 
    { 
     cols=new List<int>(Enumerable.Range(0,width)); 
     rows=new List<int>(Enumerable.Range(0,height).Select(i=>i*width)); 
     data=new double[width*height]; 
    } 
} 

Answer 5

Hm, mir sieht es wie ein einfacher binärer Baum. Der linke Knoten repräsentiert den nächsten Wert in einer Reihe und der rechte Knoten repräsentiert die Spalte.

Es sollte also einfach sein, Zeilen und Spalten zu iterieren und zu kombinieren.

Answer 6

Vielen Dank für die Antworten.

Im Moment bin ich mit dieser Lösung:

public class NodeMatrix 
{ 

    public NodeMatrix Right { get; set;} 
    public NodeMatrix Left { get; set; } 
    public NodeMatrix Up { get; set; } 
    public NodeMatrix Down { get; set; } 
    public int I { get; set; } 
    public int J { get; set; } 
    public double Data { get; set; } 

    public NodeMatrix(int I, int J, double Data) 
    { 
     this.I = I; 
     this.J = J; 
     this.Data = Data; 
    } 
} 

List<NodeMatrix> list = new List<NodeMatrix>(10000); 

Ich baue die Verbindungen zwischen den Knoten dann. Danach ist die Matrix fertig.

Dies wird mehr Speicher verwenden, aber Operationen wie das Hinzufügen von Zeilen und Spalten, das Verbinden von Zeilen und Spalten, denke ich, wird viel schneller sein.