Difference between revisions of "Dense multidimensional arrays"

From D Wiki
Jump to: navigation, search
(Dense dynamic arrays: oops)
(Add std.range method)
 
(10 intermediate revisions by 5 users not shown)
Line 25: Line 25:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
However, this approach is not so memory-efficient, because the outer array is a separate block of memory containing references to the inner arrays, and the inner arrays are individually allocated. Array lookups also require multiple indirections, so there is a slight performance hit.
+
However, this approach is not so memory-efficient, because the outer array is a separate block of memory containing references to the inner arrays. Array lookups require multiple indirections, so there is a slight performance hit.
 +
 
 +
Note that with the "jagged" array scheme, the "2nd dimensions" arrays may either all be allocated individually, or simply be slices of a single very big 1D array. Both schemes are valid.
 +
 
 +
A dynamic rectangular jagged array may be dynamically allocated at once using the multi-dim allocation syntax:
 +
<syntaxhighlight lang=D>
 +
//Allocates a dynamic array containing
 +
//  2 dynamic arrays containing
 +
//    5 ints
 +
int[][] matrix = new int[][](5, 2);
 +
</syntaxhighlight>
 +
 
 +
Note that in this example, the dimensions don't need to be known at compile time. Also note that this works for any amount of dimensions.
  
 
==Static arrays==
 
==Static arrays==
Line 41: Line 53:
  
 
Dense arrays are fast and memory-efficient. But it requires that all array dimensions be known at compile-time, that is, it must be a static array. But what about dynamic arrays?
 
Dense arrays are fast and memory-efficient. But it requires that all array dimensions be known at compile-time, that is, it must be a static array. But what about dynamic arrays?
 +
 +
==Using std.range==
 +
 +
[https://dlang.org/phobos/std_range.html#.chunks std.range.chunks] can be used to provide a 2-dimensional view of a flat (1-dimensional) buffer:
 +
 +
<syntaxhighlight lang=D>
 +
unittest
 +
{
 +
    // 2D array
 +
    int cols = 3, rows = 2;
 +
    auto buf = new int[rows * cols];
 +
    auto view = buf.chunks(cols);
 +
 +
    // Now access view[row][column]:
 +
    view[1][2] = 2;
 +
 +
    // `view` is not a copy:
 +
    ++buf[];
 +
    assert(view[1][2] == 3);
 +
 +
    // Horizontal slicing works as usual:
 +
    ++view[1][];
 +
    assert(view[1][2] == 4);
 +
 +
    // Vertical slicing can be done using `transversal`:
 +
    view.transversal(2).each!((ref n) => ++n);
 +
    assert(view[1][2] == 5);
 +
}
 +
</syntaxhighlight>
 +
 +
This can be further combined with [https://dlang.org/phobos/std_algorithm_iteration.html#.map std.algorithm.iteration.map] to allow 3 or more dimensions:
 +
 +
<syntaxhighlight lang=D>
 +
unittest
 +
{
 +
    // 3D array
 +
    int cols = 2, rows = 3, layers = 4;
 +
    auto buf = new int[cols * rows * layers];
 +
    auto view = buf.chunks(rows * cols)
 +
        .map!(layer => layer.chunks(cols));
 +
 +
    // Now access view[layer][row][column]:
 +
    view[3][2][1] = 5;
 +
}
 +
</syntaxhighlight>
  
 
==Dense dynamic arrays==
 
==Dense dynamic arrays==
  
There is a way to make multidimensional dynamic arrays dense, if only the last dimension needs to be variable:
+
There is a way to make multidimensional dynamic arrays dense, if only the last dimension needs to be variable, or if the array is just too big to fit on stack:
  
 
<syntaxhighlight lang=D>
 
<syntaxhighlight lang=D>
Line 53: Line 110:
  
 
This creates a multidimensional dynamic array with dense storage: all the array elements are contiguous in memory.
 
This creates a multidimensional dynamic array with dense storage: all the array elements are contiguous in memory.
 +
 +
==Using mir==
 +
 +
[https://github.com/libmir/mir-algorithm mir-algorithm] library provides multidimensional shell over pointers, random access iterators, arrays, and random access ranges.
 +
Multidimensional arrays are located in  [http://docs.algorithm.dlang.io/latest/mir_ndslice.html mir.ndslice package].
 +
 +
<syntaxhighlight lang=D>
 +
import mir.ndslice;
 +
 +
auto slice = slice!int(5, 6, 7);
 +
assert(slice.length == 5);
 +
assert(slice.elementsCount == 5 * 6 * 7);
 +
static assert(is(typeof(slice) == Slice!(Contiguous, [3], int*)));
 +
 +
slice[1, 3, 4] = 5;
 +
 +
auto matrix = slice[1];
 +
matrix = slice.front; // Random Access Range API
 +
 +
auto matrix2 = slice.front!1; // Multidimensional Random Access Range API
 +
 +
</syntaxhighlight>
  
 
==Credits==
 
==Credits==
  
The idiom for creating dense multidimensional dynamic arrays was first posted to the D newsgroup by monarch_dodra.
+
The idiom for creating dense multidimensional dynamic arrays was first posted to the D newsgroup by [[User:Monarchdodra]].
 +
 
 +
[[Category:CommonIdiom]]

Latest revision as of 23:46, 9 May 2018

There are several ways of declaring multidimensional arrays in D.

Jagged arrays

The simplest way is to use an array of arrays:

int[][] matrix = [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
];
assert(matrix[0][0] == 1);
assert(matrix[1][1] == 5);

This creates a so-called jagged array, because each element of the outer array can have different lengths:

int[][] matrix = [
    [ 1, 2, 3 ],
    [ 4, 5, 6, 7, 8 ], // this is valid
    [ 9, 10, 11 ]
];

However, this approach is not so memory-efficient, because the outer array is a separate block of memory containing references to the inner arrays. Array lookups require multiple indirections, so there is a slight performance hit.

Note that with the "jagged" array scheme, the "2nd dimensions" arrays may either all be allocated individually, or simply be slices of a single very big 1D array. Both schemes are valid.

A dynamic rectangular jagged array may be dynamically allocated at once using the multi-dim allocation syntax:

//Allocates a dynamic array containing
//  2 dynamic arrays containing
//    5 ints
int[][] matrix = new int[][](5, 2);

Note that in this example, the dimensions don't need to be known at compile time. Also note that this works for any amount of dimensions.

Static arrays

D recognizes the inefficiency of jagged arrays, so when all the dimensions of the array are known at compile-time, the array is automatically implemented as a dense array: the elements are packed together into a single memory block, and array access requires only a single indexed lookup:

// This is a dense array
int[3][3] matrix = [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
];

Dense arrays are fast and memory-efficient. But it requires that all array dimensions be known at compile-time, that is, it must be a static array. But what about dynamic arrays?

Using std.range

std.range.chunks can be used to provide a 2-dimensional view of a flat (1-dimensional) buffer:

unittest
{
    // 2D array
    int cols = 3, rows = 2;
    auto buf = new int[rows * cols];
    auto view = buf.chunks(cols);

    // Now access view[row][column]:
    view[1][2] = 2;

    // `view` is not a copy:
    ++buf[];
    assert(view[1][2] == 3);

    // Horizontal slicing works as usual:
    ++view[1][];
    assert(view[1][2] == 4);

    // Vertical slicing can be done using `transversal`:
    view.transversal(2).each!((ref n) => ++n);
    assert(view[1][2] == 5);
}

This can be further combined with std.algorithm.iteration.map to allow 3 or more dimensions:

unittest
{
    // 3D array
    int cols = 2, rows = 3, layers = 4;
    auto buf = new int[cols * rows * layers];
    auto view = buf.chunks(rows * cols)
        .map!(layer => layer.chunks(cols));

    // Now access view[layer][row][column]:
    view[3][2][1] = 5;
}

Dense dynamic arrays

There is a way to make multidimensional dynamic arrays dense, if only the last dimension needs to be variable, or if the array is just too big to fit on stack:

enum columns = 100;
int rows = 100;
double[columns][] gridInfo = new double[columns][](rows);

This creates a multidimensional dynamic array with dense storage: all the array elements are contiguous in memory.

Using mir

mir-algorithm library provides multidimensional shell over pointers, random access iterators, arrays, and random access ranges. Multidimensional arrays are located in mir.ndslice package.

import mir.ndslice;

auto slice = slice!int(5, 6, 7);
assert(slice.length == 5);
assert(slice.elementsCount == 5 * 6 * 7);
static assert(is(typeof(slice) == Slice!(Contiguous, [3], int*)));

slice[1, 3, 4] = 5;

auto matrix = slice[1];
matrix = slice.front; // Random Access Range API

auto matrix2 = slice.front!1; // Multidimensional Random Access Range API

Credits

The idiom for creating dense multidimensional dynamic arrays was first posted to the D newsgroup by User:Monarchdodra.