www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Collapsing n-dimensional array to linear (1 dimensional)

reply abad <abad.flt gmail.com> writes:
Let's say I have an array like this:

int[][][] array;

And I want to generate a linear int[] based on its data. Is there 
a standard library method for achieving this, or must I iterate 
over the array manually?

What I'm thinking of is something like this:

int[] onedim = std.array.collapse(array);
Jan 22
next sibling parent NX <nightmarex1337 hotmail.com> writes:
On Friday, 22 January 2016 at 12:07:11 UTC, abad wrote:
 Let's say I have an array like this:

 int[][][] array;

 And I want to generate a linear int[] based on its data. Is 
 there a standard library method for achieving this, or must I 
 iterate over the array manually?

 What I'm thinking of is something like this:

 int[] onedim = std.array.collapse(array);
It's not the thing you want but I would suggest using one dimensional array like N dimensional array like this: int d1 = 10, d2 = 10, d3 = 10; int[] arr = new int[d1 * d2 * d3]; for(int i = 0; i < d1; i++) for(int j = 0; j < d2; j++) for(int k = 0; k < d3; k++) write(arr[(i * d1 * d2) + (j * d2) + (k)]); This will lead to cache friendly code in most cases as you ensure data is packed. It's elements can be iterated with a single foreach loop and easier to use in some (many?) cases like when using functions that works with one dimensional array. And if you seriously need multi dimensional array then it's too easier to do it yourself: int[][][] a = new int[][][](d1, d2, d3); int[] collapsed = new int[d1 * d2 * d3]; foreach(i, q; a) foreach(j, w; q) foreach(k, e; w) collapsed[(i * d1 * d2) + (j * d2) + (k)] = e;
Jan 22
prev sibling next sibling parent Xinok <xinok live.com> writes:
On Friday, 22 January 2016 at 12:07:11 UTC, abad wrote:
 Let's say I have an array like this:

 int[][][] array;

 And I want to generate a linear int[] based on its data. Is 
 there a standard library method for achieving this, or must I 
 iterate over the array manually?

 What I'm thinking of is something like this:

 int[] onedim = std.array.collapse(array);
You can use std.algorithm.joiner but you have to call it twice to flatten a 3D array to a 1D array. import std.algorithm, std.stdio, std.array; void main() { int[][][] arr = [[[1], [2, 3]], [[4, 5], [6, 7]], [[8], [9, 10], [11]]]; int[] arr2 = arr.joiner.joiner.array; writeln(arr); writeln(arr2); } http://dlang.org/phobos/std_algorithm_iteration.html#.joiner
Jan 22
prev sibling next sibling parent Ilya <ilyayaroshenko gmail.com> writes:
On Friday, 22 January 2016 at 12:07:11 UTC, abad wrote:
 Let's say I have an array like this:

 int[][][] array;

 And I want to generate a linear int[] based on its data. Is 
 there a standard library method for achieving this, or must I 
 iterate over the array manually?

 What I'm thinking of is something like this:

 int[] onedim = std.array.collapse(array);
You may want to look at upcoming Multidimensional Random Access Ranges, `std.experimental.ndslice` package. They are available with DMD 2.070 beta. Pacakge has `reshape` and `byElement` functions. Docs: http://dlang.org/phobos-prerelease/std_experimental_ndslice.html Ilya
Jan 22
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 01/22/2016 04:07 AM, abad wrote:
 Let's say I have an array like this:

 int[][][] array;

 And I want to generate a linear int[] based on its data. Is there a
 standard library method for achieving this, or must I iterate over the
 array manually?

 What I'm thinking of is something like this:

 int[] onedim = std.array.collapse(array);
Something feels extra down there but it seems to work. :) import std.stdio; import std.range; import std.algorithm; auto collapse(R)(R r) if (isArray!R) { return r.joiner.collapse.joiner; } auto collapse(R)(R r) if (!isArray!R) { return r; } unittest { auto r = 3.iota .map!(i => iota(3 * i, 3 * i + 3) .map!(j => iota(3 * j, 3 * j + 3) .array) .array) .array; writeln("Original:\n", r); writeln("\nCollapsed:\n", r.collapse); assert(r.collapse.equal(iota(27))); } void main() { } Original: [[[0, 1, 2], [3, 4, 5], [6, 7, 8]], [[9, 10, 11], [12, 13, 14], [15, 16, 17]], [[18, 19, 20], [21, 22, 23], [24, 25, 26]]] Collapsed: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26] Ali
Jan 22
parent reply Solomon E <default avatar.org> writes:
On Saturday, 23 January 2016 at 07:57:55 UTC, Ali Çehreli wrote:
 auto collapse(R)(R r)
         if (isArray!R) {
     return r.joiner.collapse.joiner;
 }

 auto collapse(R)(R r)
         if (!isArray!R) {
     return r;
 }
Ali, that code only passed the one test it had for collapsing a three level array. It wouldn't collapse arrays of other numbers of levels. It wasn't recursing as appeared to be intended. Is the following code better D? (I don't know because I'm still learning D, so I'd like to be corrected if the comments in my code are inaccurate or misleading.) (See https://issues.dlang.org/show_bug.cgi?id=12062 for where I got the idea that `flatten` should be defined to mutate by reference. A comment there suggests to use std.experimental.ndslice and byElement for that, but ndlslice doesn't seem to be in the library anymore.) import std.stdio; import std.range; import std.algorithm; import std.traits; /** `collapse` returns an array that can be type inferred * and can be cast to [] without effect */ auto collapse(R)(R r) if (isArray!(ElementType!R)) { return r.joiner.array.collapse; } auto collapse(R)(R r) if (!isArray!(ElementType!R)) { return r; } /** `flatten` returns a range Result that can modify the original by ref * and .flatten.array is equivalent to .collapse */ auto flatten(R)(R r) if (isIterable!R && isIterable!(ElementType!R)) { return r.joiner.flatten; } auto flatten(R)(R r) if (!(isIterable!R && isIterable!(ElementType!R))) { return r; } unittest { auto r1 = 3.iota.array; auto r2 = 3.iota.map!(i => iota(3 * i, 3 * i + 3).array).array; assert(r2 == [[0,1,2],[3,4,5],[6,7,8]]); auto r3 = 3.iota .map!(i => iota(3 * i, 3 * i + 3) .map!(j => iota(3 * j, 3 * j + 3) .array) .array) .array; auto r4 = 3.iota .map!(i => iota(3 * i, 3 * i + 3) .map!(j => iota(3 * j, 3 * j + 3) .map!(j => iota(3 * j, 3 * j + 3) .array) .array) .array) .array; auto r5 = 3.iota .map!(i => iota(3 * i, 3 * i + 3) .map!(j => iota(3 * j, 3 * j + 3) .map!(j => iota(3 * j, 3 * j + 3) .map!(j => iota(3 * j, 3 * j + 3) .array) .array) .array) .array) .array; writeln("\nOriginal 1 level:\n", r1); writeln("Collapsed:\n", r1.collapse); writeln("\nOriginal 2 level:\n", r2); writeln("Collapsed:\n", r2.collapse); writeln("\nOriginal 3 level:\n", r3); writeln("Collapsed:\n", r3.collapse); writeln("\nOriginal 4 level:\n", r4); writeln("Collapsed:\n", r4.collapse); writeln("\nOriginal 5 level:\n", r5); writeln("Collapsed:\n", r5.collapse); // equality (collapse is eager and iota is lazy) assert(r1.collapse.equal(iota(3))); assert(r2.collapse.equal(iota(9))); assert(r3.collapse.equal(iota(27))); assert(r4.collapse.equal(iota(81))); assert(r5.collapse.equal(iota(243))); // value equality assert(r1.collapse == iota(3).array); assert(r2.collapse == iota(9).array); assert(r3.collapse == iota(27).array); assert(r4.collapse == iota(81).array); assert(r5.collapse == iota(243).array); // cast is allowed and does not affect the result assert(cast(int[]) r1.collapse == iota(3).array); assert(cast(int[]) r2.collapse == iota(9).array); assert(cast(int[]) r3.collapse == iota(27).array); assert(cast(int[]) r4.collapse == iota(81).array); assert(cast(int[]) r5.collapse == iota(243).array); // type inference auto ar1 = r1.collapse; assert(ar1 == iota(3).array); auto ar2 = r2.collapse; assert(ar2 == iota(9).array); auto ar3 = r3.collapse; assert(ar3 == iota(27).array); auto ar4 = r4.collapse; assert(ar4 == iota(81).array); auto ar5 = r5.collapse; assert(ar5 == iota(243).array); // lazy equality assert(r1.flatten.equal(iota(3))); assert(r2.flatten.equal(iota(9))); assert(r3.flatten.equal(iota(27))); assert(r4.flatten.equal(iota(81))); assert(r5.flatten.equal(iota(243))); // equivalence between .flatten.array and .collapse assert(r1.flatten.array == ar1); assert(r2.flatten.array == ar2); assert(r3.flatten.array == ar3); assert(r4.flatten.array == ar4); assert(r5.flatten.array == ar5); // mutation by reference through a flatten foreach (ref x; r3.flatten) { x++; } writeln("r3 scalar incremented ", r3); auto r3i = iota(1, 4) .map!(i => iota(3 * i - 2, 3 * i + 1) .map!(j => iota(3 * j - 2, 3 * j + 1) .array) .array) .array; assert(r3.equal(r3i)); } void main() { }
Jan 24
parent reply abad <abad.flt gmail.com> writes:
On Monday, 25 January 2016 at 02:27:57 UTC, Solomon E wrote:
 On Saturday, 23 January 2016 at 07:57:55 UTC, Ali Çehreli wrote:
 auto collapse(R)(R r)
         if (isArray!R) {
     return r.joiner.collapse.joiner;
 }

 auto collapse(R)(R r)
         if (!isArray!R) {
     return r;
 }
Ali, that code only passed the one test it had for collapsing a three level array. It wouldn't collapse arrays of other numbers of levels. It wasn't recursing as appeared to be intended. Is the following code better D? (I don't know because I'm still learning D, so I'd like to be corrected if the comments in my code are inaccurate or misleading.) (See https://issues.dlang.org/show_bug.cgi?id=12062 for where I got the idea that `flatten` should be defined to mutate by reference. A comment there suggests to use std.experimental.ndslice and byElement for that, but ndlslice doesn't seem to be in the library anymore.)
I will give this a try later. Ruby's Array class includes this sort method for flattening and for me it was surprisingly useful, for instance when it was necessary to write the array to file. I will also take a look at ndslice and see how intuitive its approach for achieving this would be.
Jan 25
parent ixid <nuaccount gmail.com> writes:
On Monday, 25 January 2016 at 08:31:14 UTC, abad wrote:
 On Monday, 25 January 2016 at 02:27:57 UTC, Solomon E wrote:
 On Saturday, 23 January 2016 at 07:57:55 UTC, Ali Çehreli
Ruby's Array class includes this sort method for flattening and for me it was surprisingly useful, for instance when it was necessary to write the array to file.
D could certainly add a few more helper functions to work on multidimensional data or perhaps an article, I admit I was unaware joiner could be chained without mapping like that. One that regularly irritates me is arrays of results that you want to make eager such that you can map a lazy function to a 2D array and then store the result in a 2D array again. This seems messy and I'd like a function that will take absolutely anything and force eager assessment. auto a = res.map!array.array; // De-lazying 2D result Would like: auto a = res.eager;
Jan 25