C# 中二维密集数组的通用、快速实现
4.68/5 (9投票s)
简要解释了为什么二维数组速度慢，为什么不使用交错数组，以及如何使用密集数组存储来克服这些问题
引言
多维数组几乎存在于每种编程语言中，但由于各种原因，通常它们并不是任何问题的最佳解决方案。 在本文中，我将展示 C# 提供的创建二维数组的不同方法。 本文主要关注这些，因为它是多维数组最常见的用法。
“标准”方式
C# 提供了两种类型的数组。 “标准”多维数组具有以下语法
var myarray = new int[2, 3];
第一个数字指定行数，而第二个数字指定列数。 它具有简洁且易于理解的语法，没有什么花哨或复杂的。 但最大的问题是性能。 如果您必须将此数组传递给函数，那么它将非常慢。
速度慢来自 CLR 的内部结构。 多维数组没有 Length 属性。 相反，它有一个 GetLength(int dimension) 方法，该方法返回指定维度的长度。 这比标准 Length 属性调用需要更多的算术运算，因为 length 返回一个可以比较和使用的内存段。
交错数组
另一种更好的方法是使用交错数组。 交错数组是一维数组的一维数组。 由于这种布局，行的长度可能不同。 这样就增加了额外的内存消耗开销。 交错数组具有以下语法
var jaggedArray = new int[2][];
for (int i=0; i<2; i++) jaggedArray[i] = new int[3];
额外的内存开销来自我们存储的是数组的数组。 每个数组都有一些内部属性需要存储。 如果我们处理的是大型数组，这可能会带来很大的开销。 另请注意初始化子数组所需的额外初始化周期。
密集数组
除了这两种方法之外，还存在另一种实现，称为密集数组。 密集术语来自矩阵。 密集数组实际上是以特殊方式索引的一维数组，因此您可以将二维数组放入一维数组中。
这有一些非常好的好处，例如，您可以使用 Array.Copy 调用轻松复制元素。 这样做的缺点是您必须使用一些巧妙的索引，这可能会导致严重的性能问题。 通常，您可以使用以下方法计算给定行和列的元素索引
var index = column * rows + row;
array[index] = 33;
该公式中最大的问题是乘法。 现代编译器和 CPU 可以很好地处理乘法，但在大数时这需要一些时间。 如果您有一个 10000x10000 的数组，那么您必须在每次索引时执行 100000000 次乘法。 这个问题可以通过将列和行乘法值存储在另一个数组中，并在索引时查找该值来解决，当然这会花费一些额外的内存，但性能不会像每次都相乘那么糟糕。
实现
每次都实现密集数组方法有点过头了。 幸运的是，自 .net 2.0 以来，我们在 c# 中有泛型，所以我提出了一个泛型密集数组类。 该实现目前处于概念验证阶段，但可以很容易地扩展到功能齐全的实现。
namespace DenseArray
{
public class DenseArray<T> : IEnumerable<T>
{
private T[] _dataarray;
private int[] _columnindexes;
/// <summary>
/// Calculates the column indexes
/// </summary>
private void CalculateColumnIndexes()
{
_columnindexes = new int[Columns];
for (int i=0; i<Columns; i++)
{
_columnindexes[i] = i * Rows;
}
}
/// <summary>
/// Creates a new instance of DenseArray
/// </summary>
/// <param name="rows">Number of rows</param>
/// <param name="columns">Number of columns</param>
public DenseArray(int rows, int columns)
{
_dataarray = new T[rows * columns];
Rows = rows;
Columns = columns;
CalculateColumnIndexes();
}
/// <summary>
/// Creates a new instance of DenseArray
/// </summary>
/// <param name="source">Source DenseArray</param>
public DenseArray(DenseArray<T> source)
{
_dataarray = new T[source.Rows * source.Columns];
Rows = source.Rows;
Columns = source.Columns;
Array.Copy(source._dataarray, this._dataarray, source._dataarray.LongLength);
_columnindexes = new int[Columns];
Array.Copy(source._columnindexes,
this._columnindexes,
source._columnindexes.LongLength);
}
/// <summary>
/// Creates a new instance of DenseArray
/// </summary>
/// <param name="array">source 2d array</param>
public DenseArray(T[,] array)
{
Rows = array.GetLength(0);
Columns = array.GetLength(1);
_dataarray = new T[Rows * Columns];
CalculateColumnIndexes();
for (int i = 0; i < Rows; i++)
{
for (int j = 0; j < Columns; j++)
{
this[i, j] = array[i, j];
}
}
}
/// <summary>
/// Gets the number of columns
/// </summary>
public int Columns { get; private set; }
/// <summary>
/// Gets the number of rows
/// </summary>
public int Rows { get; private set; }
/// <summary>
/// Gets or sets an element of the array
/// </summary>
/// <param name="row">Row index</param>
/// <param name="column">Column index</param>
/// <returns>Value at row and column index</returns>
public T this[int row, int column]
{
get { return _dataarray[_columnindexes[column] + row]; }
set { _dataarray[_columnindexes[column] + row] = value; }
}
/// <summary>
/// Gets or sets an element of the array
/// </summary>
/// <param name="i">Index</param>
/// <returns>Value at index</returns>
public T this[int i]
{
get { return _dataarray[i]; }
set { _dataarray[i] = value; }
}
/// <summary>
/// IEnumerable implementation.
/// </summary>
/// <returns>internal array enumerator</returns>
public IEnumerator<T> GetEnumerator()
{
return (IEnumerator<T>)_dataarray.GetEnumerator();
}
/// <summary>
/// IEnumerable Implementation
/// </summary>
/// <returns>internal array enumerator</returns>
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return _dataarray.GetEnumerator();
}
/// <summary>
/// Gets a row as an Array
/// </summary>
/// <param name="rowindex">Row index</param>
/// <returns>Row values in an array</returns>
public T[] GetRow(int rowindex)
{
T[] ret = new T[this.Columns];
for (int i = 0; i < this.Columns; i++)
{
ret[i] = this[rowindex, i];
}
return ret;
}
/// <summary>
/// Gets a column as an Array
/// </summary>
/// <param name="columnindex">Column index</param>
/// <returns>Column values in an array</returns>
public T[] GetColumn(int columnindex)
{
T[] ret = new T[this.Rows];
for (int i = 0; i < this.Rows; i++)
{
ret[i] = this[i, columnindex];
}
return ret;
}
/// <summary>
/// Sets a row's values from an array
/// </summary>
/// <param name="row">the row index</param>
/// <param name="items">items in an array</param>
public void SetRow(int row, T[] items)
{
if (row < 0 || row > this.Rows)
throw new ArgumentOutOfRangeException("row");
if (items == null)
throw new ArgumentNullException("items");
int limit = Math.Min(items.Length, this.Columns);
for (int i = 0; i < limit; i++)
{
this[row, i] = items[i];
}
}
/// <summary>
/// Sets a column's values from an array
/// </summary>
/// <param name="column">the column index</param>
/// <param name="items">items in an array</param>
public void SetColumn(int column, T[] items)
{
if (column < 0 || column > this.Columns)
throw new ArgumentOutOfRangeException("column");
if (items == null)
throw new ArgumentNullException("items");
int limit = Math.Min(items.Length, this.Rows);
for (int i = 0; i < limit; i++)
{
this[i, column] = items[i];
}
}
}
}
使用代码
使用该实现非常容易，它就像一个二维数组，因为该类提供了对象索引器
var dense = new DenseArray<int>(3, 3); dense[0, 2] = 42;
该实现提供了以简单方式获取和设置整个列数据的方法。 它还实现了 IEnumerable 接口，该接口目前是
性能
我使用一个简单的程序（源代码在可下载的 zip 中）测量了本文中显示的方法的性能，该程序使用标准二维数组方法、交错方法和我的实现来分配一个 10000x10000 元素数组。 结果是在一台配备 Intel i3 530 CPU、运行 64 位 Windows 10 和 .NET framework 4.6 和 4GiB RAM 的机器上测量的。
| 二维数组 | 交错数组 | DenseArray | ||
| 第一次运行 | 内存分配（字节） | 400527360 | 403034112 | 400023552 |
| 随机填充时间（毫秒） | 2292 | 1599 | 1962 | |
| 内存开销（百分比） | 0,6259 | -0,1258 | ||
| 速度增益（百分比） | 43,3396 | 16,8196 | ||
| 第二次运行 | 内存分配（字节） | 400510976 | 403079168 | 400023552 |
| 随机填充时间（毫秒） | 2285 | 1556 | 1990 | |
| 内存开销（百分比） | 0,6412 | -0,1217 | ||
| 速度增益（百分比） | 46,8509 | 14,8241 | ||
| 第三次运行 | 内存分配（字节） | 400502784 | 403087360 | 400039936 |
| 随机填充时间（毫秒） | 2271 | 1373 | 1958 | |
| 内存开销（百分比） | 0,6453 | -0,1156 | ||
| 速度增益（百分比） | 65,4042 | 15,9857 | ||
| 平均内存（字节） | 400513706,7 | 403066880 | 400029013,3 | |
| 平均随机填充时间（毫秒） | 2282,666667 | 1509,333333 | 1970 | |
| 与二维数组相比的平均内存开销（百分比） | 0,6375 | -0,1210 | ||
| 与二维数组相比的平均速度增益（百分比） | 51,2367 | 15,8714 | ||
进一步改进
将来可能会使用适当的 GetHashCode() 和 ToString() 重写来扩展该实现，并且可以添加 Enumeratior 的良好实现，因为当前的枚举器枚举项目的方式与底层数组中的方式相同。
历史
- 2015-12-16 首次发布