c# - 数据结构题

Question

我有一个包含大量行和一个数字列的数据库表，我想在内存中表示这些数据。我可以只使用一个大整数数组，这会非常快，但行数可能太大了。

大多数行(超过 99%)的值为零。是否有一种我可以使用的有效数据结构，它只会为具有非零值的行分配内存并且几乎与数组一样快？

更新:举个例子，我尝试的一件事是哈希表，它读取原始表并添加任何非零值，以原始表中的行号为键。如果未找到所请求的索引，我会使用返回 0 的函数获取值，否则返回 Hashtable 中的值。这可行，但与常规阵列相比速度很慢 - 我可能做得不对。

更新 2:这里是示例代码。

private Hashtable _rowStates;
private void SetRowState(int rowIndex, int state)
{
    if (_rowStates.ContainsKey(rowIndex))
    {
        if (state == 0)
        {
            _rowStates.Remove(rowIndex);
        }
        else
        {
            _rowStates[rowIndex] = state;
        }
    }
    else
    {
        if (state != 0) 
        {
            _rowStates.Add(rowIndex, state);
        }
    }
}
private int GetRowState(int rowIndex)
{
    if (_rowStates.ContainsKey(rowIndex))
    {
        return (int)_rowStates[rowIndex];
    }
    else
    {
        return 0; 
    }
}

Answer 1

这是一个稀疏数据结构的例子，有多种方法可以实现这种稀疏数组(或矩阵)——这完全取决于您打算如何使用它。两种可能的策略是:

• 只存储非零值。对于每个不同于零的元素存储一对(索引，值)，默认情况下所有其他值都已知为零。您还需要存储元素的总数。
• 压缩连续的零值。存储许多 (count, value) 对。例如，如果您在一行中有 12 个零，后面跟着 200 个零和另外 22 个零，则存储 (12, 0), (1, 200), (22, 0)。