432,414 Members | 1,024 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,414 IT Pros & Developers. It's quick & easy.

# flatten multi-dimensional array to on-dimensional array

 P: n/a Hi all, I have a two-dimensional array of data, f.x int's. We can imagine that the array is "really large". Now I want the data in it and store this in a one-dimensional array. The obvious way to do this is a nested for-loop - but we all know O(n^2) is bad. So I am looking for something like ArrayList.ToArray(), or Matlabs A(:). C# // D is an ArrayList D.ToArray(); Matlab % A is a matrix A(:) I tried a cast that could have been perfect for at least one of the cases. ((int[])A).CopyTo(D, 0); But I learn that I "Cannot convert type 'int[*,*]' to 'int[]'" Another problem here is that I sometimes want the data rowbased - sometimes columnbased. Right now I do something like the below code, that is horribly 2*O(n^2), I guess I could perhaps live with 1*O(n^2), but any shortcuts are welcome. Thanks, Per // // sample code below // static void Main(string[] args) { int dim1 = 2; int dim2 = 4; int k = 0; // create arrays int[,] A = new int[dim1 , dim2]; int[] B = new int[dim1 * dim2]; int[] C = new int[dim1 * dim2]; // fill A with silly values for (int i = 0; i < A.GetLength(0); i++) for (int j = 0; j < A.GetLength(1); j++) A[i, j] = k++; // // copy from A to B - rowbased // O(N^2) // int idx = 0; for (int i = 0; i < A.GetLength(0); i++) for (int j = 0; j < A.GetLength(1); j++) B[idx++] = A[i, j]; // // copy from A to C - column-based // O(N^2) // idx = 0; for (int j = 0; j < A.GetLength(1); j++) for (int i = 0; i < A.GetLength(0); i++) C[idx++] = A[i, j]; Console.WriteLine("A:"); for (int i = 0; i < A.GetLength(0); i++) { for (int j = 0; j < A.GetLength(1); j++) Console.Write(" {0}", A[i, j]); Console.WriteLine(); } Console.WriteLine("B:"); foreach (double b in B) Console.Write(" {0}", b); Console.WriteLine(); Console.WriteLine("C:"); foreach (double c in C) Console.Write(" {0}", c); Console.WriteLine(); } Nov 30 '06 #1
8 Replies

 P: n/a Perhaps you can create a custom class that wraps a one dimensional array of data and use methods to receive data as if it's two dimensional. Then you never actually convert the entire stored data from two-dimensional to one-dimensional you just map accesses to the data. However, why do you need to do this at all? If the data in inherintly two-dimensional then leave it that way. Why convert it to one-dimensional? The answer to that question could help come up with more ideas on how to accomplish your end goal. HTH, Sam ------------------------------------------------------------ We're hiring! B-Line Medical is seeking Mid/Sr. .NET Developers for exciting positions in medical product development in MD/DC. Work with a variety of technologies in a relaxed team environment. See ads on Dice.com. On 30 Nov 2006 03:13:46 -0800, "per9000" Hi all,I have a two-dimensional array of data, f.x int's. We can imagine thatthe array is "really large". Now I want the data in it and store thisin a one-dimensional array. Nov 30 '06 #2

 P: n/a Hi Per, it isn't O(n^2) but O(n) if n is the overall size of the array. No method would perform better than that, since all the content has to be copied. There could be some advantages in a build in ToOneDimension() but i don't think so and it would be very small. But the complexity of the problem will still be O(n). "per9000"

 P: n/a I agree, although given the requirements I would suggest the opposite: store the data in a two-dimensional array and then provide ways to fetch it as though it were a row-based one-dimensional array or a column-based one-dimensional array. Since you are really using a two-dimensional array and not a jagged array, the math will be simple. In .NET 2.0 you can even write two iterators: one that iterates over the array in row order, the other that iterates over the array in column order. Those plus simple access routines will allow you to treat the array in all three ways: public class MyMatrix { private T[,] _matrix; public MyMatrix(int size) { this._matrix = new T[size, size]; } public T this[int row, int column] { return this._matrix[row, column]; } public T GetByRowOrder(int rowOrder) { int rowSize = this._matrix.GetLength(0); if (rowSize == 0) { throw new IndexOutOfRangeException(...); } return this._matrix[rowOrder / rowSize, rowOrder % rowSize]; } public T GetByColumnOrder(int columnOrder) { int columnSize = this._matrix.GetLength(1); if (columnSize == 0) { throw new IndexOutOfRangeException(...); } return this._matrix[columnOrder % columnSize, columnOrder / columnSize]; } ...etc... } Samuel R. Neff wrote: Perhaps you can create a custom class that wraps a one dimensional array of data and use methods to receive data as if it's two dimensional. Then you never actually convert the entire stored data from two-dimensional to one-dimensional you just map accesses to the data. However, why do you need to do this at all? If the data in inherintly two-dimensional then leave it that way. Why convert it to one-dimensional? The answer to that question could help come up with more ideas on how to accomplish your end goal. HTH, Sam ------------------------------------------------------------ We're hiring! B-Line Medical is seeking Mid/Sr. .NET Developers for exciting positions in medical product development in MD/DC. Work with a variety of technologies in a relaxed team environment. See ads on Dice.com. On 30 Nov 2006 03:13:46 -0800, "per9000"

 P: n/a Hi, yes I could make a class that wraps my matrix, and that is pretty much the situation I am in. The need to flatten the array comes from a babel-problem, I need the values in external resources written in languages that are not in the .NET family. I did a small example in C/C# that illustrates a horribly ugly solution, but that works and that answers one of my questions. I pretty much create an array (in two dims) in C# and send it to C. C# looks at the array as an int[,]. But somewhere underneath this it is just a pointer. In the C level I receive a void* (by 'pure' luck it is a match). The from the below code is: C# >Hello. C# >calling printArr. 0 1 2 3 4 5 6 7 8 9 C# >Good night. That means to me that C# orders its elements "row based" (assuming the second index corresponds to rows). // C# code // ------------------ using System; using System.Runtime.InteropServices; using System.Collections.Generic; using System.Text; namespace PER9000 { class ArrTest { [DllImport("ArrSub.dll")] public static extern void printArr(int[,] A, int I, int J); static void Main(string[] args) { Console.WriteLine("C# >Hello."); int I = 2; int J = 5; int[,] A = new int[I, J]; int c = 0; for (int i = 0; i < I; i++) for (int j = 0; j < J; j++) A[i, j] = c++; Console.WriteLine("C# >calling printArr."); printArr(A, I, J); Console.WriteLine("C# >Good night."); } } } // ------------------ // C code void __declspec(dllexport) __stdcall printArr(void* A, int I, int J); void __declspec(dllexport) __stdcall printArr(void* A, int I, int J) { int c = 0; int * B = (int *) A; for (c = 0; c < I * J; c++) printf(" %d", B[c]); printf("\n"); } // ------------------ This somehow answers part of my question. It seems that I have to use a nested for-loop (I agree the complexity is O(number of elements)) to hand-pick the elements one by one (I am afraid this will be a bottleneck when it comes to speed). So my conclusion is that there are no 'better' way to flatten an array in two dims ordered by column. /Per Dec 1 '06 #5 