sparse-matrix - 在 C# 中实现存储稀疏数据的表的最有效方法是什么

Question

我有一个存储非常稀疏数据的 DataTable，例如：

   P1 P2 P3 P4 P5 ...
J1 1  1
J2    1  1
J3             1
.
.
.

行数和列数可能超过 10^8。

如何以更有效的方式存储这些数据？

Answer 1

如果您的磁盘文件系统支持稀疏文件，您可以创建一个空文件，将其标记为稀疏，然后将其调整为rows * colums * datasize.

然后是通过 [row][column] 访问数据的问题，其中偏移量可以通过以下方式计算：

offset = ((columns.length * (row-1)) + column) * datasize

稀疏文件在分配方面也有一些开销，它通常分配 16-64kb 的页面，但取决于您的数据集群的方式，它可能会很好地工作。

Answer 2

首先，去掉那些数据计数的 DataTable。它的内存使用量在这里非常大。

如果您的数据始终为 0/1，那么最有效的方法应该是位掩码。

如果您的数据不仅是 0/1，请创建一个抽象所有列的结构。

这是该数据结构的概念原型。

class MyData {
    public MyData(int[] columns, object[] data) {
        _columns = columns;
        _data = data;
    }

    int[] _columns;
    object[] _data;

    public object this[int column] {
        get {
            int index = IndexOf(column);
            return index != -1 ? _data[index] : null;
        }
    }

    private int IndexOf(int column) {
        for (int i = 0; i < _columns.Length; i++)
            if (_columns[i] == column)
                return i;
        return -1;
    }
}

您还可以通过应用享元模式来节省 _columns 的内存。

希望这可以帮助

Answer 3

在有效存储备用矩阵方面有很多现有技术。

一种常见的方法称为“列表列表”。例如，Python 有一种内存高效的方式将备用矩阵存储为“基于行的链表稀疏矩阵”。