在 C# 中快速访问矩阵作为锯齿状数组

Question

我创建了一个下三角距离矩阵（由于大小问题）作为锯齿状数组 注意：对象之间的距离是对称的

var dm = new double[size][]
for (var i = 0; i < size; i++)
{
   dm[i] = new double[i+1];
   for (var j = 0; j < i+1; j++)
   {
      dm[i][j] = distance(data[i], data[j]);
   }
 }

我需要经常访问这个矩阵，所以我为它做了下面的方法

private double GetValueOfDM(int row, int column, double[][] dm)
{
    return column <= row ? distanceMatrix[row][column] : distanceMatrix[column][row];
}

通过 Visual Studio 性能分析，可以看出主要的速度问题在于 GetValueOfDM 方法的唯一行。

有人知道如何加快速度吗？

Answer 1

您可以删除方法中的条件并增加内存使用量以提高访问性能，如下所示：

var dm = new double[size][];
for (var i = 0; i < size; i++)
{
   dm[i] = new double[size];
   for (var j = 0; j < i+1; j++)
   {
      dm[i][j] = distance(data[i], data[j]);
      dm[j][i] = dm[i][j];
   }
 }

private double GetValueOfDM(int row, int column, double[][] dm)
{
    return dm[row][column];
}

现在您没有条件，编译器可以删除分支预测。此外，您应该运行测试您的实际用例，以确保它确实会成为一个问题。分析可能会表明分支条件将是代码中最慢的部分，但这并不一定意味着它实际上会显着减慢任何速度。此外，您可以尝试运行在 Release 模式下使用它（使用编译器优化）以查看它如何影响性能。

如果您所处的系统没有足够的内存来使数组的大小翻倍，那么您的代码可能接近于访问锯齿状数组的最佳代码。

Answer 2

我猜你是在紧密循环中使用它？由于自动边界检查，.NET 中的数组并不/那么/快。如果您需要快速数组性能，请使用带缓冲区的指针：

sealed unsafe class DistanceData : IDisposable {
    private Double* buffer;
    private IntPtr  bufferLength; // .NET uses IntPtr as a size_t equivalent.
    private Int32   dim0Length;

    public DistanceData(Int32 size, Double[] data) {
        this.buffer       = (Double*)Marshal.AllocHGlobal( size * size );
        this.bufferLength = size * size;
        this.dim0Length   = size;

        for(int y = 0; y < size; y++) {
            for(int x = 0; x < y + 1; x++) {
                this.buffer[ y * this.dim0Length + x ] = Distance( data[y], data[x] );
            }
        }
    }

    public void Dispose() {
        Marshal.FreeHGlobal( this.buffer );
    }

    public Double GetValueOfDM(Int32 row, Int32 column) {
        // WARNING: Without validation or your own bounds-checking, invalid values of `row` and `column` will cause access-violation errors and crash your program. Ensure that code that calls `GetValueOfDM` is correct and will never submit invalid values.
        return this.buffer[ row * this.dim0Length  + column];
    }
}

Answer 3

您可以使用一维数组并像这样计算索引

i = (r * r + r) / 2 + c;

但是您仍然需要检查 r <= c 并进行翻转。（r=行，c=列）

但这真的会更快吗？

在 C# 中快速访问矩阵作为锯齿状数组

Fast access to matrix as jagged array in C#

c#

performance

matrix

jagged-arrays