C# 中的链接二维矩阵

Question

我需要在 C# 中实现此场景：

矩阵将是非常大，可能是 10000x10000 或更大。我将在层次聚类算法中使用它作为距离矩阵。在算法的每次迭代中，矩阵都应该更新（将 2 行连接成 1 行，将 2 列连接成 1 列）。如果我使用简单的 double[,] 或 double[][] 矩阵，此操作将非常“昂贵”。 请问，有人可以建议这个场景的 C# 实现吗？

Answer 1

你现在有算法吗？你说的贵是什么意思？内存贵还是时间贵？如果内存昂贵：在 C# 中您无能为力。但您可以考虑使用临时对象在数据库内执行计算。如果时间昂贵：您可以使用并行性来连接列和行。

但除此之外，我认为简单的 double[,] 数组是 c# 中最快且节省内存的方式，因为访问数组值是一个 o(1) 操作，并且数组的数量最少内存和管理开销（与列表和字典相比）。

Answer 2

如上所述，基本的 double[,] 将是 C# 中处理此问题的最有效方法。

请记住，C# 位于托管内存的顶部，因此与基本 C 之类的操作相比，您对低级（就内存而言）操作的细粒度控制较少。在 C# 中创建自己的对象来添加功能只会使用更多在这种情况下，内存可能会减慢算法的速度。

如果您尚未选择算法，CURE 似乎是一个不错的选择。算法的选择可能会影响您的数据结构选择，但这不太可能。

您会发现该算法无论如何决定了“成本”的理论限制。例如，您将了解到，对于 CURE，您受到 O(n2 log n) 运行时间和 O(n) 内存使用的限制。

我希望这有帮助。如果您能提供更多详细信息，我们也许可以为您提供更多帮助！

N。

Answer 3

不可能“合并”两行或两列，您必须将整个矩阵复制到一个新的、更小的矩阵中，这确实昂贵得令人无法接受。

您可能应该将一行中的值添加到前一行，然后忽略这些值，就像删除它们一样。

数组的数组：double[][] 实际上比 double[,] 更快。但需要更多内存。

如果你稍微改变一下算法，整个数组合并的事情可能就不需要了，但这可能对你有帮助：

    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

在此代码中，我使用两个一维帮助器列表来计算包含数据的大数组的索引。删除行/列非常便宜，因为我只需要从辅助列表中删除该索引。但当然，大数组中的内存仍然存在，即根据您的使用情况，您会出现内存泄漏。

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

嗯，对我来说这看起来像一个简单的二叉树。左节点代表行中的下一个值，右节点代表列。

因此，迭代行和列并将它们组合起来应该很容易。

Answer 6

谢谢您的回答。

目前我正在使用这个解决方案：

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

然后我正在构建节点之间的连接。之后矩阵就准备好了。

这将使用更多内存，但我认为添加行和列、连接行和列等操作会快得多。