473,699 Members | 2,746 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

flatten multi-dimensional array to on-dimensional array

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.ToArr ay(),
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.WriteLi ne("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.WriteLi ne();
}

Console.WriteLi ne("B:");
foreach (double b in B)
Console.Write(" {0}", b);
Console.WriteLi ne();

Console.WriteLi ne("C:");
foreach (double c in C)
Console.Write(" {0}", c);
Console.WriteLi ne();
}

Nov 30 '06 #1
8 11825

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" <pe*****@gmail. comwrote:
>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.
Nov 30 '06 #2
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" <pe*****@gmail. comschrieb im Newsbeitrag
news:11******** **************@ n67g2000cwd.goo glegroups.com.. .
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.ToArr ay(),
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.WriteLi ne("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.WriteLi ne();
}

Console.WriteLi ne("B:");
foreach (double b in B)
Console.Write(" {0}", b);
Console.WriteLi ne();

Console.WriteLi ne("C:");
foreach (double c in C)
Console.Write(" {0}", c);
Console.WriteLi ne();
}

Nov 30 '06 #3
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<T>
{
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(i nt rowOrder)
{
int rowSize = this._matrix.Ge tLength(0);
if (rowSize == 0)
{
throw new IndexOutOfRange Exception(...);
}
return this._matrix[rowOrder / rowSize, rowOrder % rowSize];
}

public T GetByColumnOrde r(int columnOrder)
{
int columnSize = this._matrix.Ge tLength(1);
if (columnSize == 0)
{
throw new IndexOutOfRange Exception(...);
}
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" <pe*****@gmail. comwrote:
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.
Nov 30 '06 #4
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.Collecti ons.Generic;
using System.Text;

namespace PER9000
{
class ArrTest
{
[DllImport("ArrS ub.dll")]
public static extern void printArr(int[,] A, int I, int J);

static void Main(string[] args)
{
Console.WriteLi ne("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.WriteLi ne("C# >calling printArr.");
printArr(A, I, J);
Console.WriteLi ne("C# >Good night.");
}
}
}
// ------------------
// C code
void __declspec(dlle xport) __stdcall printArr(void* A, int I, int J);
void __declspec(dlle xport) __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

per9000 wrote:
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.Collecti ons.Generic;
using System.Text;

namespace PER9000
{
class ArrTest
{
[DllImport("ArrS ub.dll")]
public static extern void printArr(int[,] A, int I, int J);

static void Main(string[] args)
{
Console.WriteLi ne("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.WriteLi ne("C# >calling printArr.");
printArr(A, I, J);
Console.WriteLi ne("C# >Good night.");
}
}
}
// ------------------
// C code
void __declspec(dlle xport) __stdcall printArr(void* A, int I, int J);
void __declspec(dlle xport) __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.
Two points.

First, the only way faster than O(n) is something equivalent to C's
memcpy method that copies chunks of memory at a time. I think that this
is what you're looking for, but so far as I know C# doesn't allow you
to do things like this for security reasons. On modern CPUs the loop
operation should be fast enough anyway, as the whole row will likely
fit into on-board cache and the loop for copying a row (at least) will
not have to fetch from memory. I don't know about the writing of the
array to its new "flattened" structure... that may fit into cache as
well. Anyway, using pure C#, there's no "memcpy" any more, so there's
nothing faster than O(n).

Second, I think that you're thinking about the problem from a
too-low-level point of view. In situations like this, you have two
possible solutions:

1) Maintain the values in their most logical form (i.e. a
two-dimensional array) and whenever you need to read them in another
form (e.g. flattened into a column-then-row order) then do the
necessary calculations to fetch them in that order. This is the
solution I proposed. This solution makes sense if most of the time you
are manipulating / using the values as a 2-D array and only
occasionally do you need them in their row-major or column-major order.
>From a performance point of view, this solution works well if you spend
most of your time in the C# code, but only occasionally have to call
other languages and thus translate the array into column-major order.
(As you've seen, C# stores multidimensiona l arrays in row-major order
and so is compatible with C, for example, although I don't know if that
is guaranteed to be so into the future.)

If, however, you make repeated calls to other languages and you have to
transform the array each time, and you suspect that this will be a
performance problem, the solution is not to find a way to transform the
array faster, but to find a way to not transform the array at all.

2) One solution along those lines is to maintain the values in multiple
orders and use whichever order is most useful at any given moment. This
makes sense if the values are read much more than they are modified,
and the reads are as often in one order as another. The code for a
solution like that might look something like this:

public class MyMatrix<T>
{
private T[] _rowMajor;
private T[] _columnMajor;
private int _rowCount;
private int _columnCount;

public MyMatrix(int rows, int columns)
{
if (rows <= 0) throw new ArgumentExcepti on(...);
if (columns <= 0) throw new ArgumentExcepti on(...);
this._rowCount = rows;
this._columnCou nt = columns;
this._rowMajor = new T[rows * columns];
this._columnMaj or = new T[rows * columns];
}

public T this[int row, int column]
{
get { return this._rowMajor[row * this._columnCou nt + column];
}
set
{
this._rowMajor[row * this._columnCou nt + column] = value;
this._columnMaj or[column * this._rowCount + row] = value;
}
}

...etc...
}

As you can see, the cost here is writing to the structure, which is now
more expensive. The return on that investment is that you have row and
column-major order arrays constantly maintained for quick read-back. If
the C# program is constantly reading the values as a two-dimensional
array then you could add that as a third, constantly-maintained form
for the data. In other words, store the data in triplicate:
two-dimensional, row-major, and column-major orders.

This becomes more complicated, however, if the programs you call will
be modifying the arrays. In that case when you return from calling the
other language you have to synch any changes from the array you passed
back to the other copy or copies. So, if you pass a row-major array to
a program that makes changes to it, you then have to copy that back
into the column-major version (and potentially to the two-dimensional
version, if you're maintaining that) so that they remain in synch.
Since you can't know what the program changed, that would cost you at
least one entire array copy on every call, which would be the same cost
as the first solution.

So, if the other-language programs you're calling do nothing but read
the arrays, and you call them frequently, solution #2 is better. If
they update the arrays, or if they are called infrequently and your C#
program does frequent updates to the array then solution #1 is at least
no worse, and probably better. Finally, if the programs you call in
other languages update the arrays they're passed then you're going to
have performance problems no matter what you do.

Dec 1 '06 #6
Hi,
First, the only way faster than O(n) is something equivalent to C's
memcpy method that copies chunks of memory at a time. I think that this
is what you're looking for, but so far as I know C# doesn't allow you
to do things like this for security reasons.
Ok, that is what I needed to hear. Thanks.

2) One solution along those lines is to maintain the values in multiple
orders and use whichever order is most useful at any given moment. This
makes sense if the values are read much more than they are modified...
Excellent idea! In my case the values are created once, then pretty
much only read. This will of course require some more memory, but that
is compensated with speed so I think this might be nice for me -
especially since I might end up with repeated scans of the matrix.

Another bonus with this is that I could use shallow copying if I only
read the values (this is not true in general but might work sometimes).
I send a pointer to the appropriate one-dimensional array instead of
copying the values. O(1) I guess, but on the other hand - I do not
really copy the values.

/Per

Dec 3 '06 #7

per9000 wrote:
I send a pointer to the appropriate one-dimensional array instead of copying the values.
Exactly. No copying = no performance problem.

BTW, it's common to trade memory for performance when solving computing
problems. It's rare that you can save memory and increase speed at the
same time (unless the original design stank). Usually there are several
good designs, ranging from compact and slow to memory-hungry and fast,
and the problem is to choose the right one based on how the data are
used.

Dec 4 '06 #8
Another related thing:
Do you know how efficient/fast...

// non-shallow copy of myMatrix to yourMatrix
myMatrix.CopyTo (yourMatrix,0);

....is compared to...

for (int i = 0; i < myMatrix.Length ; i++)
yourMatrix[i] = myMatrix[i]

?

/Per

Dec 4 '06 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

23
3726
by: Francis Avila | last post by:
Below is an implementation a 'flattening' recursive generator (take a nested iterator and remove all its nesting). Is this possibly general and useful enough to be included in itertools? (I know *I* wanted something like it...) Very basic examples: >>> rl = , '678', 9]] >>> list(flatten(rl)) >>> notstring = lambda obj: not isinstance(obj, type(''))
0
1877
by: Francis Avila | last post by:
A few days ago (see the 'itertools.flatten()?' thread from October 28) I became obsessed with refactoring a recursive generator that yielded the leaves of nested iterables. When the dust settled, I had many flatten functions at hand. So I had to time them. Results below. History of the functions (from flattrial.py): # There are three basic features:
10
4138
by: bearophile | last post by:
This is my first Python program (it's an improvement of a recursive version by Luther Blissett). Given a list like this: , ]]] It produces the "flatted" version: I think this operation is quite important, and it's similar to the built-in Mathematica Flatten function: l = {{"a", 2, {}, {3, 5, {4}}}}
3
1345
by: Bengt Richter | last post by:
What am I missing? (this is from 2.4b1, so probably it has been fixed?) def flatten(list): l = for elt in list: ^^^^--must be expecting list instance or other sequence t = type(elt) if t is tuple or t is list: ^^^^--looks like it expects to refer to the type, not the arg
18
2623
by: Ville Vainio | last post by:
For quick-and-dirty stuff, it's often convenient to flatten a sequence (which perl does, surprise surprise, by default): ]]] -> One such implementation is at http://aspn.activestate.com/ASPN/Mail/Message/python-tutor/2302348
181
8805
by: Tom Anderson | last post by:
Comrades, During our current discussion of the fate of functional constructs in python, someone brought up Guido's bull on the matter: http://www.artima.com/weblogs/viewpost.jsp?thread=98196 He says he's going to dispose of map, filter, reduce and lambda. He's going to give us product, any and all, though, which is nice of him.
32
2781
by: Robin Becker | last post by:
Is there some smart/fast way to flatten a level one list using the latest iterator/generator idioms. The problem arises in coneverting lists of (x,y) coordinates into a single list of coordinates eg f() --> or g(,) -->
2
3915
by: wenmang | last post by:
Hi, As part of simple serialization, I like to determine which is the right way to do: flatten a class containing flat C-structs with some member functions or just plain C-structs. We need to store those data as context in shared memory. I just want to know what is pro and cons for this idea: class Context { public: memFun1();
25
4089
by: beginner | last post by:
Hi, I am wondering how do I 'flatten' a list or a tuple? For example, I'd like to transform or ] to . Another question is how do I pass a tuple or list of all the aurgements of a function to the function. For example, I have all the arguments of a function in a tuple a=(1,2,3). Then I want to pass each item in the tuple to a function f so that I make a function call f(1,2,3). In perl it is a given, but in python, I haven't figured out
1
2180
by: farooq.omar | last post by:
Is there a way to specify to Flatten() method as to how many points it should return. example I just want the Flatten() method to give back 100 points (basicallt gp.PointCount==100). Thanks
0
8704
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, weíll explore What is ONU, What Is Router, ONU & Routerís main usage, and What is the difference between ONU and Router. Letís take a closer look ! Part I. Meaning of...
0
8623
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9187
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
9053
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8936
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
5879
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4636
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3071
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
2015
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.