将T [,]转换为T [] []的最快方法？

Question

因此,事实证明并非创建的所有阵列等.多维数组可以具有非零下限.请参阅Excel PIA的Range.Value属性object[,] rectData = myRange.Value;

我需要将这些数据转换为锯齿状数组.我第一次尝试下面的复杂气味.有什么优化建议吗？它需要处理下限可能不为零的一般情况.

我有这个ex方法:

    public static T[][] AsJagged<T>( this T[,] rect )
    {
        int row1 = rect.GetLowerBound(0);
        int rowN = rect.GetUpperBound(0);
        int col1 = rect.GetLowerBound(1);
        int colN = rect.GetUpperBound(1);

        int height = rowN - row1 + 1;
        int width = colN - col1 + 1;
        T[][] jagged = new T[height][];

        int k = 0;
        int l;
        for ( int i = row1; i < row1 + height; i++ )
        {
            l = 0;
            T[] temp = new T[width];
            for ( int j = col1; j < col1 + width; j++ )
                temp[l++] = rect[i, j];
            jagged[k++] = temp;
        }

        return jagged;
    }

像这样使用:

    public void Foo()
    {
        int[,] iRect1 = { { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 } };
        int[][] iJagged1 = iRect1.AsJagged();

        int[] lengths = { 3, 5 };
        int[] lowerBounds = { 7, 8 };
        int[,] iRect2 = (int[,])Array.CreateInstance(typeof(int), lengths, lowerBounds);
        int[][] iJagged2 = iRect2.AsJagged();

    }

好奇,如果Buffer.BlockCopy()可以工作或更快？

编辑:AsJagged需要处理引用类型.

编辑:在AsJagged()中发现错误.补充int l; 并添加col1 + width到内循环.

Answer 1

预先观察/假设:

• 您似乎只使用int您的数据类型(或者至少看起来可以使用Buffer.BlockCopy,这意味着您可以使用基本类型的生活).
• 对于您展示的测试数据,我认为使用任何有点理智的方法都不会有太大的不同.

话虽如此,下面的实现(需要专门针对特定的基本类型(这里int),因为它使用fixed)比使用内部循环的方法快10倍:

    unsafe public static int[][] AsJagged2(int[,] rect)
    {
        int row1 = rect.GetLowerBound(0);
        int rowN = rect.GetUpperBound(0);
        int col1 = rect.GetLowerBound(1);
        int colN = rect.GetUpperBound(1);

        int height = rowN - row1 + 1;
        int width = colN - col1 + 1;
        int[][] jagged = new int[height][];

        int k = 0;
        for (int i = row1; i < row1 + height; i++)
        {
            int[] temp = new int[width];

            fixed (int *dest = temp, src = &rect[i, col1])
            {
                MoveMemory(dest, src, rowN * sizeof(int));
            }

            jagged[k++] = temp;
        }

        return jagged;
    }

    [DllImport("kernel32.dll", EntryPoint = "RtlMoveMemory")]
    unsafe internal static extern void MoveMemory(void* dest, void* src, int length);

使用以下"测试代码":

    static void Main(string[] args)
    {
        Random rand = new Random();
        int[,] data = new int[100,1000];
        for (int i = 0; i < data.GetLength(0); i++)
        {
            for (int j = 0; j < data.GetLength(1); j++)
            {
                data[i, j] = rand.Next(0, 1000);
            }
        }

        Stopwatch sw = Stopwatch.StartNew();

        for (int i = 0; i < 100; i++)
        {
            int[][] dataJagged = AsJagged(data);
        }

        Console.WriteLine("AsJagged:  " + sw.Elapsed);

        sw = Stopwatch.StartNew();

        for (int i = 0; i < 100; i++)
        {
            int[][] dataJagged2 = AsJagged2(data);
        }

        Console.WriteLine("AsJagged2: " + sw.Elapsed);
    }

其中AsJagged(第一种情况)是您的原始函数,我得到以下输出:

AsJagged:  00:00:00.9504376
AsJagged2: 00:00:00.0860492

所以确实有一种更快的方法,但是根据测试数据的大小,实际执行此操作的次数,以及您是否愿意允许不安全和P/Invoke代码,您可能不会需要它.

话虽如此,我们使用的是大型矩阵double(比如7000x10000元素),确实确实产生了巨大的差异.

更新:关于使用Buffer.BlockCopy

我可能会忽略一些Marshal或其他技巧,但我不认为Buffer.BlockCopy在这里可以使用.这是因为它要求源和目标数组都是一个Array.

在我们的示例中,目标是一个数组(例如int[] temp = ...),但源不是.虽然我们"知道"对于原始类型的二维数组,布局是这样的,每个"行"(即第一维)是内存中类型的数组,没有安全(如unsafe)的方式来获得该数组没有先复制它的开销.所以我们基本上需要使用一个简单处理内存而不关心它的实际内容的函数 - 比如MoveMemory.顺便说一句,内部实现Buffer.BlockCopy做了类似的事情.

Answer 2

您的复杂性是O(N*M)N - 行数,M - 列数.复制N*M值时,这是最好的...

Buffer.BlockCopy可能比你的内部for循环更快,但如果编译器知道如何正确处理这段代码并且你不会获得任何进一步的速度,我也不会感到惊讶.你应该测试它以确保.

您可以通过不复制数据来获得更好的性能(可能会略微减慢查找速度).如果创建一个"数组行"类,它包含rect和行号,并提供访问正确列的索引器,则可以创建此类行的数组,并完全保存复制.

创建这种"数组行"数组的复杂性是O(N).

编辑:一个ArrayRow类,只是因为它让我烦恼...

ArrayRow看起来像这样:

class ArrayRow<T>
{
    private T[,] _source;
    private int _row;

    public ArrayRow(T[,] rect, int row)
    {
         _source = rect;
         _row = row;
    }

    public T this[int col] { get { return _source[_row, col]; } }
}

现在您创建了一个ArrayRows数组,您根本不复制任何内容,优化器很有可能优化顺序访问整行.