Fast way to convert a two dimensional array to a List ( one dimensional )

Question

I have a two dimensional array and I need to convert it to a List (same object). I don't want to do it with for or foreach loop that will take each element and add it to the List. Is there some other way to do it?

Answer 1

Well, you can make it use a "blit" sort of copy, although it does mean making an extra copy :(

double[] tmp = new double[array.GetLength(0) * array.GetLength(1)];    
Buffer.BlockCopy(array, 0, tmp, 0, tmp.Length * sizeof(double));
List<double> list = new List<double>(tmp);

If you're happy with a single-dimensional array of course, just ignore the last line :)

Buffer.BlockCopy is implemented as a native method which I'd expect to use extremely efficient copying after validation. The List<T> constructor which accepts an IEnumerable<T> is optimized for the case where it implements IList<T>, as double[] does. It will create a backing array of the right size, and ask it to copy itself into that array. Hopefully that will use Buffer.BlockCopy or something similar too.

Here's a quick benchmark of the three approaches (for loop, Cast<double>().ToList(), and Buffer.BlockCopy):

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        double[,] source = new double[1000, 1000];
        int iterations = 1000;

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < iterations; i++)
        {
            UsingCast(source);
        }
        sw.Stop();
        Console.WriteLine("LINQ: {0}", sw.ElapsedMilliseconds);

        GC.Collect();
        GC.WaitForPendingFinalizers();

        sw = Stopwatch.StartNew();
        for (int i = 0; i < iterations; i++)
        {
            UsingForLoop(source);
        }
        sw.Stop();
        Console.WriteLine("For loop: {0}", sw.ElapsedMilliseconds);

        GC.Collect();
        GC.WaitForPendingFinalizers();

        sw = Stopwatch.StartNew();
        for (int i = 0; i < iterations; i++)
        {
            UsingBlockCopy(source);
        }
        sw.Stop();
        Console.WriteLine("Block copy: {0}", sw.ElapsedMilliseconds);
    }


    static List<double> UsingCast(double[,] array)
    {
        return array.Cast<double>().ToList();
    }

    static List<double> UsingForLoop(double[,] array)
    {
        int width = array.GetLength(0);
        int height = array.GetLength(1);
        List<double> ret = new List<double>(width * height);
        for (int i = 0; i < width; i++)
        {
            for (int j = 0; j < height; j++)
            {
                ret.Add(array[i, j]);
            }
        }
        return ret;
    }

    static List<double> UsingBlockCopy(double[,] array)
    {
        double[] tmp = new double[array.GetLength(0) * array.GetLength(1)];    
        Buffer.BlockCopy(array, 0, tmp, 0, tmp.Length * sizeof(double));
        List<double> list = new List<double>(tmp);
        return list;
    }
}

Results (times in milliseconds);

LINQ: 253463
For loop: 9563
Block copy: 8697

EDIT: Having changed the for loop to call array.GetLength() on each iteration, the for loop and the block copy take around the same time.

Answer 2

To convert double[,] to List<double>, if you are looking for a one-liner, here goes

double[,] d = new double[,]
{
    {1.0, 2.0},
    {11.0, 22.0},
    {111.0, 222.0},
    {1111.0, 2222.0},
    {11111.0, 22222.0}
};
List<double> lst = d.Cast<double>().ToList();

---

But, if you are looking for something efficient, I'd rather say you don't use this code.
Please follow either of the two answers mentioned below. Both are implementing much much better techniques.

Answer 3

A for loop is the fastest way.

You may be able to do it with LINQ, but that will be slower. And while you don't write a loop yourself, under the hood there is still a loop.

• For a jagged array you can probably do something like arr.SelectMany(x=>x).ToList().
• On T[,] you can simply do arr.ToList() since the IEnumerable<T> of T[,] returns all elements in the 2D array. Looks like the 2D array only implements IEnumerable but not IEnumerable<T> so you need to insert a Cast<double> like yetanothercoder suggested. That will make it even slower due to boxing.

The only thing that can make the code faster than the naive loop is calculating the number of elements and constructing the List with the correct capacity, so it doesn't need to grow.
If your array is rectangular you can obtain the size as width*height, with jagged arrays it can be harder.

int width=1000;
int height=3000;
double[,] arr=new double[width,height];
List<double> list=new List<double>(width*height);
int size1=arr.GetLength(1);
int size0=arr.GetLength(0);
for(int i=0;i<size0;i++)
{  
  for(int j=0;j<size1;j++)
    list.Add(arr[i,j]);
}

In theory it might be possible to use private reflection and unsafe code to make it a bit faster doing a raw memory copy. But I strongly advice against that.