将锯齿状数组转换为2D数组C#

Question

我正在尝试将此函数从Jagged Array转换为2D数组,而我无法转换所有内容原始函数:

public static double[][] InvertMatrix(double[][] A)
{
    int n = A.Length;
    //e will represent each column in the identity matrix
    double[] e;
    //x will hold the inverse matrix to be returned
    double[][] x = new double[n][];
    for (int i = 0; i < n; i++)
    {
        x[i] = new double[A[i].Length];
    }
    /*
    * solve will contain the vector solution for the LUP decomposition as we solve
    * for each vector of x.  We will combine the solutions into the double[][] array x.
    * */
    double[] solve;

    //Get the LU matrix and P matrix (as an array)
    Tuple<double[][], int[]> results = LUPDecomposition(A);

    double[][] LU = results.Item1;
    int[] P = results.Item2;

    /*
    * Solve AX = e for each column ei of the identity matrix using LUP decomposition
    * */
    for (int i = 0; i < n; i++)
    {
        e = new double[A[i].Length];
        e[i] = 1;
        solve = LUPSolve(LU, P, e);
        for (int j = 0; j < solve.Length; j++)
        {
            x[j][i] = solve[j];
        }
    }
    return x;
}

我到目前为止所转换的内容:

public static double[,] InvertMatrix(double[,] A)
{
    int n = A.Length;
    //e will represent each column in the identity matrix
    double[] e;
    //x will hold the inverse matrix to be returned
    double[,] x = new double[n][];
    for (int i = 0; i < n; i++)
    {
        //how to convert this line?
        x[i] = new double[A[i].Length];
    }
    /*
    * solve will contain the vector solution for the LUP decomposition as we solve
    * for each vector of x.  We will combine the solutions into the double[][] array x.
    * */
    double[] solve;

    //Get the LU matrix and P matrix (as an array)
    Tuple<double[,], int[]> results = LUPDecomposition(A);

    double[,] LU = results.Item1;
    int[] P = results.Item2;

    /*
    * Solve AX = e for each column ei of the identity matrix using LUP decomposition
    * */
    for (int i = 0; i < n; i++)
    {
        //This one too?!
        e = new double[A[i].Length];
        e[i] = 1;
        solve = LUPSolve(LU, P, e);
        for (int j = 0; j < solve.Length; j++)
        {
            x[j,i] = solve[i,j];
        }
    }
    return x;
}

如何将x [i] = new double [A [i] .Length]转换为2D数组？

Answer 1

这个片段可能会有所帮助

static T[,] To2D<T>(T[][] source)
{
    try
    {
        int FirstDim = source.Length;
        int SecondDim = source.GroupBy(row => row.Length).Single().Key; // throws InvalidOperationException if source is not rectangular

        var result = new T[FirstDim, SecondDim];
        for (int i = 0; i < FirstDim; ++i)
            for (int j = 0; j < SecondDim; ++j)
                result[i, j] = source[i][j];

        return result;
    }
    catch (InvalidOperationException)
    {
        throw new InvalidOperationException("The given jagged array is not rectangular.");
    } 
}

用法:

double[][] array = { new double[] { 52, 76, 65 }, new double[] { 98, 87, 93 }, new double[] { 43, 77, 62 }, new double[] { 72, 73, 74 } };
double[,] D2 = To2D(array);

UPD:对于那些可以接受不安全环境的情况,有一个更快的解决方案,谢谢Styp:https://stackoverflow.com/a/51450057/3909293

Answer 2

注意：您的锯齿状数组应该是正交的，因此子数组长度应该全部相等，否则您无法将其转换为二维数组。

那个部分：

double[,] x = new double[n][];
for (int i = 0; i < n; i++)
{
    //how to convert this line?
    x[i] = new double[A[i].Length];
}

只是为了初始化一个新的锯齿状数组，它可以很容易地替换为

double[,] x = new double[A.GetLength(0),A.GetLength(1)];

并在

   //This one too?!
    e = new double[A[i].Length];

i您本质上是在创建一个具有相同长度的子数组的数组，A因此我们可以将其替换为

    e = new double[A.GetLength(1)]; //NOTE: second dimension

如前所述，所有子数组长度都相等，因此我们可以使用第二维长度。

整个方法是：

    public static double[,] InvertMatrix2D(double[,] A)
    {
        int n = A.Length;
        //e will represent each column in the identity matrix
        double[] e;
        //x will hold the inverse matrix to be returned
        double[,] x = new double[A.GetLength(0),A.GetLength(1)];

        /*
        * solve will contain the vector solution for the LUP decomposition as we solve
        * for each vector of x.  We will combine the solutions into the double[][] array x.
        * */
        double[] solve;

        //Get the LU matrix and P matrix (as an array)
        Tuple<double[,], int[]> results = LUPDecomposition(A);

        double[,] LU = results.Item1;
        int[] P = results.Item2;

        /*
        * Solve AX = e for each column ei of the identity matrix using LUP decomposition
        * */
        for (int i = 0; i < n; i++)
        {
            e = new double[A.GetLength(1)]; //NOTE: second dimension
            e[i] = 1;
            solve = LUPSolve(LU, P, e);
            for (int j = 0; j < solve.Length; j++)
            {
                x[j,i] = solve[j];
            }
        }
        return x;
    }

Answer 3

如果运行时间不重要，Diligent Key Pressers 的答案是正确的。我经常使用 3D 数组，我了解到逐值复制操作非常昂贵！记在脑子里！另一件事是 Linq 很慢，而且先决条件也在消耗时间！

在我看来，如果时间很重要，这个解决方案可能会有用：

using System;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace ArrayConverter {
   public class Benchmark {
        [Params(10, 100, 1000, 10000)] 
        public int size;

        public double[][] data;

        [GlobalSetup]
        public void Setup() {
            var rnd = new Random();

            data = new double[size][];
            for (var i = 0; i < size; i++) {
                data[i] = new double[size];
                for (var j = 0; j < size; j++) {
                    data[i][j] = rnd.NextDouble();
                }
            }
        }

        [Benchmark]
        public void ComputeTo2D() {
            var output = To2D(data);
        }

       [Benchmark]
       public void ComputeTo2DFast() {
           var output = To2DFast(data);
       }

       public static T[,] To2DFast<T>(T[][] source) where T : unmanaged{
           var dataOut = new T[source.Length, source.Length];
           var assertLength = source[0].Length;

           unsafe {
               for (var i=0; i<source.Length; i++){
                   if (source[i].Length != assertLength) {
                       throw new InvalidOperationException("The given jagged array is not rectangular.");
                   }

                   fixed (T* pDataIn = source[i]) {
                       fixed (T* pDataOut = &dataOut[i,0]) {
                           CopyBlockHelper.SmartCopy<T>(pDataOut, pDataIn, assertLength);
                       }
                   }
               }
           }

           return dataOut;
       }

        public static T[,] To2D<T>(T[][] source) {
            try {
                var FirstDim = source.Length;
                var SecondDim =
                    source.GroupBy(row => row.Length).Single()
                        .Key; // throws InvalidOperationException if source is not rectangular

                var result = new T[FirstDim, SecondDim];
                for (var i = 0; i < FirstDim; ++i)
                for (var j = 0; j < SecondDim; ++j)
                    result[i, j] = source[i][j];

                return result;
            }
            catch (InvalidOperationException) {
                throw new InvalidOperationException("The given jagged array is not rectangular.");
            }
        }
    }

    public class Programm {
        public static void Main(string[] args) {
            BenchmarkRunner.Run<Benchmark>();
//            var rnd = new Random();
//            
//            var size = 100;
//            var data = new double[size][];
//            for (var i = 0; i < size; i++) {
//                data[i] = new double[size];
//                for (var j = 0; j < size; j++) {
//                    data[i][j] = rnd.NextDouble();
//                }
//            }
//
//            var outSafe = Benchmark.To2D(data);
//            var outFast = Benchmark.To2DFast(data);
//
//            for (var i = 0; i < outSafe.GetLength(0); i++) {
//                for (var j = 0; j < outSafe.GetLength(1); j++) {
//                    if (outSafe[i, j] != outFast[i, j]) {
//                        Console.WriteLine("Error at: {0}, {1}", i, j);
//                    }
//                }
//            }
//
//            Console.WriteLine("All Good!");

        }
    }
}

CopyBlock Helper 是从这里获得的：https ://gist.github.com/theraot/1bfd0deb4a1aab0a27d8

我刚刚为 IL 函数制作了一个包装器：

using System;
using System.Reflection.Emit;

namespace ArrayConverter {

    // Inspired by:
    // http://xoofx.com/blog/2010/10/23/high-performance-memcpy-gotchas-in-c/
    public class CopyBlockHelper {

        private const int BlockSize = 16384;

        private static readonly CopyBlockDelegate CpBlock = GenerateCopyBlock();

        private unsafe delegate void CopyBlockDelegate(void* des, void* src, uint bytes);

        private static unsafe void CopyBlock(void* dest, void* src, uint count) {
            var local = CpBlock;
            local(dest, src, count);
        }

        static CopyBlockDelegate GenerateCopyBlock() {
            // Don't ask...
            var method = new DynamicMethod("CopyBlockIL", typeof(void),
                new[] {typeof(void*), typeof(void*), typeof(uint)}, typeof(CopyBlockHelper));
            var emitter = method.GetILGenerator();
            // emit IL
            emitter.Emit(OpCodes.Ldarg_0);
            emitter.Emit(OpCodes.Ldarg_1);
            emitter.Emit(OpCodes.Ldarg_2);
            emitter.Emit(OpCodes.Cpblk);
            emitter.Emit(OpCodes.Ret);

            // compile to delegate
            return (CopyBlockDelegate) method.CreateDelegate(typeof(CopyBlockDelegate));
        }

        public static unsafe void SmartCopy<T>(T* pointerDataOutCurrent, T* pointerDataIn, int length) where T : unmanaged {
            var sizeOfType = sizeof(T);

            var numberOfBytesInBlock = Convert.ToUInt32(sizeOfType * length);

            var numOfIterations = numberOfBytesInBlock / BlockSize;
            var overheadOfLastIteration = numberOfBytesInBlock % BlockSize;

            uint offset;
            for (var idx = 0u; idx < numOfIterations; idx++) {
                offset = idx * BlockSize;
                CopyBlock(pointerDataOutCurrent + offset / sizeOfType, pointerDataIn + offset / sizeOfType, BlockSize);
            }

            offset = numOfIterations * BlockSize;
            CopyBlock(pointerDataOutCurrent + offset / sizeOfType, pointerDataIn + offset / sizeOfType, overheadOfLastIteration);
        }
    }
}

这导致以下结果：

          Method |  size |             Mean |            Error |           StdDev |
---------------- |------ |-----------------:|-----------------:|-----------------:|
     ComputeTo2D |    10 |         972.2 ns |        18.981 ns |        17.755 ns |
 ComputeTo2DFast |    10 |         233.1 ns |         6.672 ns |         6.852 ns |
     ComputeTo2D |   100 |      21,082.5 ns |       278.679 ns |       247.042 ns |
 ComputeTo2DFast |   100 |       6,100.2 ns |        66.566 ns |        62.266 ns |
     ComputeTo2D |  1000 |   2,481,061.0 ns |    13,724.850 ns |    12,166.721 ns |
 ComputeTo2DFast |  1000 |   1,939,575.1 ns |    18,519.845 ns |    16,417.358 ns |
     ComputeTo2D | 10000 | 340,687,083.2 ns | 1,671,837.229 ns | 1,563,837.429 ns |
 ComputeTo2DFast | 10000 | 279,996,210.4 ns |   955,032.923 ns |   745,626.822 ns |

如果可能，请尝试使用 ArrayCopy、BlockCopy 或 IL-CopyBlock 来提高转换性能。逐值复制操作很慢，因此不是最好的选择！通过优化一些东西并删除 if 子句，可以找到进一步的加速。应该可以实现至少 2 倍的系数！