digitalmars.D.learn - Collapsing n-dimensional array to linear (1 dimensional)
- abad (7/7) Jan 22 2016 Let's say I have an array like this:
- NX (21/28) Jan 22 2016 It's not the thing you want but I would suggest using one
- Xinok (13/20) Jan 22 2016 You can use std.algorithm.joiner but you have to call it twice to
- Ilya (8/15) Jan 22 2016 You may want to look at upcoming Multidimensional Random Access
- =?UTF-8?Q?Ali_=c3=87ehreli?= (33/40) Jan 22 2016 Something feels extra down there but it seems to work. :)
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 2016
NX <nightmarex1337 hotmail.com> 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 2016
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); }
Jan 22 2016
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 2016
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 2016
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 2016
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: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.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.)
Jan 25 2016
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: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;On Saturday, 23 January 2016 at 07:57:55 UTC, Ali ÇehreliRuby'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.
Jan 25 2016