logo标签列表

将不规则数组转换为二维数组 C#

c#arraysjagged-arrays
11
我正在尝试将这个函数从不规则数组转换为二维数组，但我无法全部转换。原始函数如下：

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] 转换为二维数组？
4个回答
32

这段代码可能会有所帮助

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);

更新：对于那些不安全的情境，可以采用更快的解决方案，感谢Styp提供的建议：https://dev59.com/6ITba4cB1Zd3GeqP1yTZ#51450057

完成了，不是要无礼。当然，解决方案是有效的，但我认为由于LR分解，代码应该是“快速”的，就我所知，逐个值的操作总是很昂贵的！ - Styp
@Styp 谢谢，干得好！我已经在答案中添加了一个引用。 - Diligent Key Presser
6

如果运行时间不重要，勤奋的按键者所给出的答案是正确的。我经常使用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倍的加速！
谢谢！你尝试过不使用unsafe方式对To2DFast进行基准测试吗？ - Diligent Key Presser
不确定是否可能。据我所知，没有办法将[]复制到[,]中，这就是问题所在。使用fixed（T *）的不安全代码解决了该问题，通过获取引用而不知道目标数组的“形状”。这可以工作，因为[,]数组在一个块中被保存。也许您有解决此问题的想法... - Styp
我为两个数组的加法操作制作了一个基准测试。也许我们可以进一步扩展它... -> https://github.com/Styp/IntegerAdditionBenchmark - Styp
1
这里似乎有一个 bug：var dataOut = new T[source.Length, source.Length];，应该是 var dataOut = new T[source.Length, source[0].Length];。否则，代码将在方形数组上运行正确，但在非方形的二维矩形数组上运行时将不会正确。 - Alexander Higgins
5

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

需要注意的部分：

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];

你实际上是在创建一个与 A 中子数组 i 长度相同的数组，这样我们可以用它来替换。

    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;
    }
1

只是为了确保我们有相同的理解，锯齿数组是一个数组中包含数组的结构。所以当你执行

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

你正在为第一维数组的每个位置添加一个数组。

在你的情况下（在嵌套数组中），A.Length 表示数组的第一维长度，而 A[i].Length 表示包含在第一维索引 (i) 中的第二维数组的长度。如果你使用的是 2D 数组，则 A.Length 表示两个维度的长度乘积。虽然嵌套数组的每个第二维数组可以有不同的长度，但是 2D 数组必须在两个维度上具有相同的长度。

因此，在你的情况下，你需要获取 n = A.GetLength(0)（表示获取第一维长度）和 m = A.GetLength(1)（表示获取第二维长度）。然后你将初始化 'x'，double[,] x = new double[n, m];，并且你将不再需要 for 循环。

你的代码应该像这样：

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, m];

    /*
    * 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?! /// this one would become 
        e = new double[m];
        e[i] = 1;
        solve = LUPSolve(LU, P, e);
        for (int j = 0; j < solve.Length; j++)
        {
            x[j,i] = solve[i,j];
        }
    }
    return x;
}

所以，如果我的方法可行的话，这将修复您的问题并回答您的问题。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接