Linked Matrice 2D en C#

Question

que je dois mettre en œuvre ce scénario en C#:

La matrice sera très grande, peut-être 10000x10000 ou plus. Je vais l'utiliser pour la matrice de distance dans l'algorithme de classification hiérarchique. Dans chaque itération de l'algorithme, la matrice doit être mise à jour (en joignant 2 lignes en 1 et 2 colonnes en 1). Si j'utilise une simple matrice double [,] ou double [] [], ces opérations seront très "chères". S'il vous plaît, quelqu'un peut-il suggérer la mise en œuvre C# de ce scénario?

Answer 1

Avez-vous un algorithme en ce moment? Et que voulez-vous dire par cher? Mémoire ou temps cher? Si la mémoire est chère: Il n'y a pas grand chose à faire en C#. Mais vous pouvez envisager d'exécuter le calcul dans une base de données en utilisant des objets temporaires. Si le temps est cher: vous pouvez utiliser le parallélisme pour joindre des colonnes et des lignes. Mais à côté de cela, je pense qu'un simple tableau double[,] est le moyen le plus rapide et le moins utilisé en mémoire car l'accès aux valeurs du tableau est une opération o (1) et les tableaux ont un minimum de mémoire et de gestion (comparé aux listes et aux dictionnaires).

Answer 2

Comme mentionné ci-dessus, un double basique [,] sera le moyen le plus efficace de gérer cela en C#. Rappelez-vous que C# se trouve au sommet de la mémoire gérée, et que vous avez moins de contrôle sur les opérations de bas niveau (en termes de mémoire) contrairement à C de base. Création de vos propres objets en C# pour ajouter des fonctionnalités utilise uniquement plus de mémoire dans ce scénario et ralentit probablement l'algorithme.

Si vous n'avez pas encore choisi un algorithme, CURE semble être un bon pari. Le choix de l'algorithme peut affecter votre choix de structure de données, mais ce n'est pas probable.

Vous constaterez que l'algorithme détermine les limites théoriques du «coût» en tout cas. Par exemple, vous allez lire que pour CURE, vous êtes lié par un temps d'exécution O (n2 log n) et une utilisation de la mémoire O (n).

J'espère que cela aide. Si vous pouvez fournir plus de détails, nous pourrions être en mesure d'aider davantage!

N.

Answer 3

Il est impossible de « fusionner » deux lignes ou deux colonnes, vous auriez à copier toute la matrice dans une nouvelle, plus petite, ce qui est en effet inacceptable cher.

Vous devriez probablement simplement ajouter les valeurs dans une rangée à la précédente, puis ignorer les valeurs, agissant comme si elles avaient été supprimées.

les tableaux de tableaux: double [] [] est réellement plus rapide que double [,]. Mais prend plus de mémoire.

Le tableau entier chose la fusion pourrait ne pas être nécessaire si vous modifiez le Algoritm un peu, mais cela pourrait aider 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

Dans ce code que j'utilise deux listes d'aide 1D pour calculer l'indice dans un grand tableau contenant les données. Supprimer des lignes/colonnes est vraiment bon marché car je n'ai besoin que de supprimer cet index des listes d'aide. Mais bien sûr, la mémoire dans le grand tableau reste, c'est-à-dire en fonction de votre utilisation, vous avez une fuite de mémoire.

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, pour moi, cela ressemble à un simple arbre binaire. Le noeud gauche représente la valeur suivante dans une ligne et le noeud droit représente la colonne.

Il devrait donc être facile d'itérer des lignes et des colonnes et de les combiner.

Answer 6

Merci pour les réponses.

En ce moment je suis en utilisant cette solution:

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); 

Ensuite, je construis les liens entre les nœuds. Après cela, la matrice est prête.

Cela nécessitera plus de mémoire, mais des opérations comme l'ajout de lignes et de colonnes, la jonction de lignes et de colonnes seront beaucoup plus rapides.