在C#中迭代二维数组的最快方法:

huangapple go评论60阅读模式
英文:

Fastest way to iterate 2d array in C#

问题

我有一个包装2D float[][] 数组为1D float[] 数组的类:

class Wrapper
{
   int CountX;
   int CountY;
   float[] Values;
}

例如,像这样的数据:

{1, 2, 3, 4}
{5, 6, 7, 8}

可以包装为:

var wr = new Wrapper
{
  Values = new float[8] {1, 2, 3, 4, 5, 6, 7, 8},
  CountX = 4,
  CountY = 2
};

我想要找到获取其行或列的最快方式。目前我正在使用以下方法:

class Wrapper
{
   int CountX;
   int CountY;
   float[] Values;

   public float[] GetRow(int row)
   {
       var res = new float[CountX];
       for (int i = 0; i < CountX; i++)
       {
           res[i] = Values[CountX * row + i];
       }
       return res;
   }

   public float[] GetColumn(int column)
   {
       var res = new float[CountY];
       for (int i = 0; i < CountY; i++)
       {
           res[i] = Values[column + CountX * i];
       }
       return res;
   }
}

使用方式如下:

var wr = new Wrapper
{
  Values = new float[8] {1, 2, 3, 4, 5, 6, 7, 8},
  CountX = 4,
  CountY = 2
};

wr.GetRow(1) // 5 6 7 8
wr.GetColumn(3) // 4 8

我尝试提高性能。我相当确定可以使用不安全代码更快地完成,但我不太了解如何在C#中使用指针。

英文:

I have a class that wraps 2d float[][] array into 1d float[] array:

class Wrapper
{
   int CountX;
   int CountY;
   float[] Values;
}

for example something like this

{1, 2, 3, 4}
{5, 6, 7, 8}

would be wrapped into

var wr = new Wrapper
{
  Values = new float[8]{1,2,3,4,5,6,7,8},
  CountX = 4,
  CountY = 2
};

And I want to find the fastest way to get its row or column.
Currently I'm using these methods

class Wrapper
{
   int CountX;
   int CountY;
   float[] Values;

   public float[] GetRow(int row)
   {
       var res = new float[CountX];
       for(int i = 0; i &lt; CountX; i++)
       {
           res[i] = Values[CountX*row + i];
       }
       return res;
   }

   public float[] GetColumn(int column)
   {
       var res = new float[CountY];
       for (int i = 0; i &lt; CountY; i++)
       {
           res[i] = Values[column + CountX*i];
       }
       return res;
   }
}

With this usage:

var wr = new Wrapper
{
  Values = new float[8]{1,2,3,4,5,6,7,8},
  CountX = 4,
  CountY = 2
};

//{1, 2, 3, 4}
//{5, 6, 7, 8}

wr.GetRow(1) // 5 6 7 8
wr.GetColumn(3) // 4 8

And what I am trying to accomplish is increasing performance. I'm pretty sure there is a way to do it faster using unsafe code, but I don't really know how to use pointers in C#

答案1

得分: 2

以下是您要翻译的部分:

"The fastest way to do this would usually be to not allocate or copy anything. Switching to unsafe is not going to help much with the real cost here, which is the allocation and copy; at best you can avoid some bounds checks.

Assuming you keep a 1D backing array, on the minor axis (by which I mean: contiguous data), it should be trivially possible to get a Span<float> of the relevant chunk of data: nothing more than that i.e. new ReadOnlySpan<float>(Values, CountX*row, CountX); on the major axis, maybe return something that is simply a flyweight readonly struct with an indexer into the data?

However, honestly I wonder if you should just use a float[,] and use regular x/y indexing.


Example; note that choosing which dimension to use as the inner one is important, as the direct Span<T> access will be faster than the indirect Row<T> access:

using System.Runtime.InteropServices;

var obj = new ArrayWrapper<float>(2, 3);
obj[1, 2] = 4;
Write(obj);
var row = obj.GetColumn(1);
for (int i = 0; i < row.Length; i++)
    row[i] = i;
Write(obj);
var col = obj.GetRow(1);
for (int i = 0; i < col.Length; i++)
    col[i] = i + 10;
Write(obj);
col = obj.GetRow(2);
for (int i = 0; i < col.Length; i++)
    col[i] = i + 20;
Write(obj);
static void Write(ArrayWrapper<float> arr)
{
    for (int y = 0; y < arr.Height; y++)
    {
        for (int x = 0; x < arr.Width; x++)
        {
            Console.Write(arr[x, y]);
            Console.Write('\t');
        }
        Console.WriteLine();
    }
    Console.WriteLine();
}

readonly struct ArrayWrapper<T>
{
    private readonly T[,] _array;
    public int Width => _array.GetLength(0);
    public int Height => _array.GetLength(1);
    public ArrayWrapper(int width, int height) => _array = new T[width, height];
    public ref T this[int x, int y] => ref _array[x, y];
    public readonly Span<T> GetColumn(int x)
        => MemoryMarshal.CreateSpan(ref _array[x, 0], Height);
    public readonly Row<T> GetRow(int y) => new(_array, y);
}
readonly struct Row<T>
{
    private readonly T[,] _array;
    private readonly int _y;

    public Row(T[,] array, int y)
    {
        _array = array;
        _y = y;
    }
    public bool IsEmpty => Length == 0;
    public int Length => _array.GetLength(0); // Width
    public ref T this[int x] => ref _array[x, _y];
}

希望这对您有所帮助。如果您有任何其他问题,请随时提出。

英文:

The fastest way to do this would usually be to not allocate or copy anything. Switching to unsafe is not going to help much with the real cost here, which is the allocation and copy; at best you can avoid some bounds checks.

Assuming you keep a 1D backing array, on the minor axis (by which I mean: contiguous data), it should be trivially possible to get a Span&lt;float&gt; of the relevant chunk of data: nothing more than that i.e. new ReadOnlySpan&lt;float&gt;(Values, CountX*row, CountX); on the major axis, maybe return something that is simply a flyweight readonly struct with an indexer into the data?

However, honestly I wonder if you should just use a float[,] and use regular x/y indexing.


Example; note that choosing which dimension to use as the inner one is important, as the direct Span&lt;T&gt; access will be faster than the indirect Row&lt;T&gt; access:

using System.Runtime.InteropServices;

var obj = new ArrayWrapper&lt;float&gt;(2, 3);
obj[1, 2] = 4;
Write(obj);
var row = obj.GetColumn(1);
for (int i = 0; i &lt; row.Length; i++)
    row[i] = i;
Write(obj);
var col = obj.GetRow(1);
for (int i = 0; i &lt; col.Length; i++)
    col[i] = i + 10;
Write(obj);
col = obj.GetRow(2);
for (int i = 0; i &lt; col.Length; i++)
    col[i] = i + 20;
Write(obj);
static void Write(ArrayWrapper&lt;float&gt; arr)
{
    for (int y = 0; y &lt; arr.Height; y++)
    {
        for (int x = 0; x &lt; arr.Width; x++)
        {
            Console.Write(arr[x, y]);
            Console.Write(&#39;\t&#39;);
        }
        Console.WriteLine();
    }
    Console.WriteLine();
}

readonly struct ArrayWrapper&lt;T&gt;
{
    private readonly T[,] _array;
    public int Width =&gt; _array.GetLength(0);
    public int Height =&gt; _array.GetLength(1);
    public ArrayWrapper(int width, int height) =&gt; _array = new T[width, height];
    public ref T this[int x, int y] =&gt; ref _array[x, y];
    public readonly Span&lt;T&gt; GetColumn(int x)
        =&gt; MemoryMarshal.CreateSpan(ref _array[x, 0], Height);
    public readonly Row&lt;T&gt; GetRow(int y) =&gt; new(_array, y);
}
readonly struct Row&lt;T&gt;
{
    private readonly T[,] _array;
    private readonly int _y;

    public Row(T[,] array, int y)
    {
        _array = array;
        _y = y;
    }
    public bool IsEmpty =&gt; Length == 0;
    public int Length =&gt; _array.GetLength(0); // Width
    public ref T this[int x] =&gt; ref _array[x, _y];
}

答案2

得分: 1

对于行,你应该返回一个 ReadonlySpan<T>,因为这将是零拷贝操作。这是基于假设你的存储是按行主要排列的。

对于列,你将需要复制元素。将目标作为参数传递可能会很有用,这样可以避免重复分配。你还可以在循环中直接更新索引,我期望这会稍微提高性能,但我没有进行任何性能分析。

public void CopyColumn(int column, Span<float> res)
{
       for (int i = column; i < Values.Length; i += CountX)
       {
           res[i] = Values[i];
       }
}

如果你想要一个数组作为结果,你可以添加一个辅助方法:

public float[] GetColumn(int column){
    var res = new float[CountY];
    CopyColumn(column, res);
    return res;
}
英文:

For rows you should return a ReadonlySpan&lt;T&gt; since that would be a zero-copy operation. This is assuming your storage is row-major.

For columns you will need to copy elements. It can be useful to take the destination as a parameter. That way it might be possible to avoid repeated allocations. You can also update the index directly in the loop, I would expect that to help a little bit, but I have not done any profiling.

public void CopyColumn(int column, Span&lt;float&gt; res)
{
       for (int i = column; i &lt; Values.Length; i += CountX)
       {
           res[i] = Values[i];
       }
}

If you want an array as a result you can add a helper method:

public float[] GetColumn(int column){
    var res = new float[CountY];
    CopyColumn(column, res);
    return res;
}

huangapple
  • 本文由 发表于 2023年2月6日 21:45:11
  • 转载请务必保留本文链接:https://go.coder-hub.com/75362113.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定