Multi-dimensional array
For the purposes of this task, the actual memory layout or access method of this data structure is not mandated. It is enough to:
- State the number and extent of each index to the array.
- Provide specific, ordered, integer indices for all dimensions of the array together with a new value to update the indexed value.
- Provide specific, ordered, numeric indices for all dimensions of the array to obtain the arrays value at that indexed position.
- The task is to
- State if the language supports multi-dimensional arrays in its syntax and usual implementation.
- Show how to create a four dimensional array in your language and set, access, set to another value; and access the new value of an integer-indexed item of the array.
The idiomatic method for the language is preferred.
- The array should allow a range of five, four, three and two (or two three four five if convenient), in each of the indices, in order. (For example, if indexing starts at zero for the first index then a range of 0..4 inclusive would suffice).
- State if memory allocation is optimised for the array - especially if contiguous memory is likely to be allocated.
- If the language has exceptional native multi-dimensional array support such as optional bounds checking, reshaping, or being able to state both the lower and upper bounds of index ranges, then this is the task to mention them.
Show all output here, (but you may judiciously use ellipses to shorten repetitive output text).
ALGOL 68
Algol 68 supports multi-dimensional arrays as standard. The maximum values for the indexes and the number of indexes is up to the implementation.
The upper and optionally the lower bounds of each index are specified when the array is created. If omitted the, the lower bound defaults to 1. The bounds can be arbitrary integer expressions.
The upper and lower bounds are separated by ":" and each bound is separated from the next by a ",". The array required by the task could be declared as follows: # <lang algol68>[ 1 : 5, 1 : 4, 1 : 3, 1 : 2 ]INT a;</lang>
As the lower bounds are all 1, this could be abbreviated to: <lang algol68>[ 5, 4, 3, 2 ]INT a;</lang>
Note that the lower and upper bounds can be 0 or negative, e.g. the following declares an array of the same size but different bounds: <lang algol68>[ -7 : -3. -3 : 0, -1 : 1, 0 : 1 ]INT x;</lang>
Individual array elements can be set and accessed by stating the index values separated by ",". The following sets the lowest element of the array to 0: <lang algol68>a[ 1, 1, 1, 1 ] := 0;</lang>
The following sets the highest element to the lowest: <lang algol68>a[ 5, 4, 3, 2 ] := a[ 1, 1, 1, 1 ];</lang>
Subsets of the array can be set and accessed by stating the index values of the subsets, e.g. the following sets a pair of elements near the start of the array to a pair of elements near the end: Selecting a subset of an array is known as slicing. <lang algol68>a[ 3 : 4, 1, 1, 1 ] := a[ 5, 4, 2 : 3, 1 ];</lang>
The whole array can also be assigned, e.g., the following sets the entire array to some values, using nested "literal arrays" (known as row-displays): <lang algol68># Note this requires the lower bounds of each index be 1 # a := ( ( ( ( 1111, 1112 ), ( 1121, 1122 ), ( 1131, 1132 ) )
, ( ( 1211, 1212 ), ( 1221, 1222 ), ( 1231, 1232 ) )
, ( ( 1311, 1312 ), ( 1321, 1322 ), ( 1331, 1332 ) )
, ( ( 1411, 1412 ), ( 1421, 1422 ), ( 1431, 1432 ) ) )
, ( ( ( 2111, 2112 ), ( 2121, 2122 ), ( 2131, 2132 ) )
, ( ( 2211, 2212 ), ( 2221, 2222 ), ( 2231, 2232 ) )
, ( ( 2311, 2312 ), ( 2321, 2322 ), ( 2331, 2332 ) )
, ( ( 2411, 2412 ), ( 2421, 2422 ), ( 2431, 2432 ) ) )
, ( ( ( 3111, 3112 ), ( 3121, 3122 ), ( 3131, 3132 ) )
, ( ( 3211, 3212 ), ( 3221, 3222 ), ( 3231, 3232 ) )
, ( ( 3311, 3312 ), ( 3321, 3322 ), ( 3331, 3332 ) )
, ( ( 3411, 3412 ), ( 3421, 3422 ), ( 3431, 3432 ) ) )
, ( ( ( 4111, 4112 ), ( 4121, 4122 ), ( 4131, 4132 ) )
, ( ( 4211, 4212 ), ( 4221, 4222 ), ( 4231, 4232 ) )
, ( ( 4311, 4312 ), ( 4321, 4322 ), ( 4331, 4332 ) )
, ( ( 4411, 4412 ), ( 4421, 4422 ), ( 4431, 4432 ) ) )
, ( ( ( 5111, 5112 ), ( 5121, 5122 ), ( 5131, 5132 ) )
, ( ( 5211, 5212 ), ( 5221, 5222 ), ( 5231, 5232 ) )
, ( ( 5311, 5312 ), ( 5321, 5322 ), ( 5331, 5332 ) )
, ( ( 5411, 5412 ), ( 5421, 5422 ), ( 5431, 5432 ) ) ) );</lang>
If the lower bounds are not 1, they can be temporarily be changed to 1 by using the "AT" construct, e.g. as in the following:
<lang algol68># declare an array the same size as a, but with all lower bounds equal to 2: # [ 2 : 6, 2 : 5, 2 : 4, 2 : 3 ]INT b;
- set b to the same values as a above: #
b[ AT 1, AT 1, AT 1, AT 1 ] :=
( ( ( ( 1111, 1112 ), ( 1121, 1122 ), ( 1131, 1132 ) )
, ( ( 1211, 1212 ), ( 1221, 1222 ), ( 1231, 1232 ) )
, ( ( 1311, 1312 ), ( 1321, 1322 ), ( 1331, 1332 ) )
, ( ( 1411, 1412 ), ( 1421, 1422 ), ( 1431, 1432 ) ) )
, ( ( ( 2111, 2112 ), ( 2121, 2122 ), ( 2131, 2132 ) )
, ( ( 2211, 2212 ), ( 2221, 2222 ), ( 2231, 2232 ) )
, ( ( 2311, 2312 ), ( 2321, 2322 ), ( 2331, 2332 ) )
, ( ( 2411, 2412 ), ( 2421, 2422 ), ( 2431, 2432 ) ) )
, ( ( ( 3111, 3112 ), ( 3121, 3122 ), ( 3131, 3132 ) )
, ( ( 3211, 3212 ), ( 3221, 3222 ), ( 3231, 3232 ) )
, ( ( 3311, 3312 ), ( 3321, 3322 ), ( 3331, 3332 ) )
, ( ( 3411, 3412 ), ( 3421, 3422 ), ( 3431, 3432 ) ) )
, ( ( ( 4111, 4112 ), ( 4121, 4122 ), ( 4131, 4132 ) )
, ( ( 4211, 4212 ), ( 4221, 4222 ), ( 4231, 4232 ) )
, ( ( 4311, 4312 ), ( 4321, 4322 ), ( 4331, 4332 ) )
, ( ( 4411, 4412 ), ( 4421, 4422 ), ( 4431, 4432 ) ) )
, ( ( ( 5111, 5112 ), ( 5121, 5122 ), ( 5131, 5132 ) )
, ( ( 5211, 5212 ), ( 5221, 5222 ), ( 5231, 5232 ) )
, ( ( 5311, 5312 ), ( 5321, 5322 ), ( 5331, 5332 ) )
, ( ( 5411, 5412 ), ( 5421, 5422 ), ( 5431, 5432 ) ) ) );</lang>
Bounds checking is standard and there is no standard way to turn it off. There may be implementation-specific mechanisms ( probably using pragmatic comments ) to do so.
The memory layout of an array is determined by the implementation and is not visible to the programmer.
"Flexible" arrays whose size can change during the execution of the program can be created. These are used e.g. for the builtin STRING mode.
The size of a flexible array can be changed only be assigning a new array to it.
The bounds of the array can be determined using the LWB and UPB operators. <lang algol68># E.g. the following prints the lower and upper bounds of the first two #
- indexes of a ( in this case, 1, 5, 1 and 4 ) #
print( ( 1 LWB a, 1 UPB a, 2 LWB a, 2 UPB a, newline ) );</lang>
For a 1 dimensional array, the unary LWB and UPB operators can be used.
ALGOL W
Algol W supports multi-dimensional arrays as standard. The maximum values for the indexes and the number of indexes is up to the implementation. The upper and lower bounds of each index are specified when the array is declared. The bounds are evaluated on entry to the block containing the declaration and can be arbitrary integer expressions.
The upper and lower bounds are separated by "::" and each bound is separated from the next by a ",". The array required by the task could be declared as follows: <lang algolw>integer array a ( 1 :: 5, 1 :: 4, 1 :: 3, 1 :: 2 );</lang> note that the lower and upper bounds can be 0 or negative, e.g. the following declares an array of the same size but different bounds: <lang algolw>integer array x ( -7 :: -3. -3 :: 0, -1 :: 1, 0 :: 1 );</lang>
individual array elements can be set and accessed by stating the index values separated by ",". The following sets the lowest element of the array to 0: <lang algolw>a( 1, 1, 1, 1 ) := 0;</lang>
The following sets the highest element to the lowest: <lang algolw>a( 5, 4, 3, 2 ) := a( 1, 1, 1, 1 );</lang>
Subsets of an array can be specified as parameters to procedures. E.g.: <lang algolw>% declare a procedure that has a three-dimensional array parameter % procedure p ( integer array a1 ( *, *, * ) ) ; a1( 1, 2, 1 ) := 3 ;
% call the procedure with a subset of the 4 dimensional array % p( a( *, 2, *, * ) );</lang>
The elements of the array can only be set individually, it is not possible to assign the whole array or multiple elements other than with element-by-element assignments.
Bounds checking is standard and there is no standard way to turn it off. There may be implementation-specific mechanisms to do so.
The memory layout of an array is determined by the implementation and is not visible to the programmer.
J
J supports multi-dimensional arrays, and provides a variety of ways of creating and working with them.
Perhaps the simplest mechanism to create a multidimensional array is to reshape a smaller dimensioned array with the desired dimensions:
<lang J>A1=:5 4 3 2$0</lang>
This creates an array of 120 zeros arranged in contiguous memory.
Note that items along the leading dimension of the array being reshaped are repeated as necessary to fill in all the values of the array. Thus, this is equivalent:
<lang J>A2=:5 4 $ 1 3 2$ 0</lang>
Another candidate for the simplest mechanism to create a multidimensional array is to ask for an array of indices with those dimensions:
<lang J> i.2 3 4 5
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 27 28 29 30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119</lang>
Note that these indices are not multi-dimensional indices but simple counting numbers. To obtain the corresponding index, you can use J's antibase verb. For example:
<lang J> 2 3 4 5#:118 1 2 3 3</lang>
Normally, in J, you operate on "everything at once", which can be challenging if you have not worked in a language (such as sql or any of a variety of others) which encourages that kind of thinking. Nevertheless, here's some introductory "one at a time" operations:
Pulling a single value from an array:
<lang J> (<1 2 3 3) { i.2 3 4 5 118</lang>
Setting a single value in an array:
<lang J>A3=: 987 (<1 2 3 3)} i. 2 3 4 5</lang>
And, to reduce vertical space used in this task, here's an example of extracting a sub-array:
<lang J> (<1 2){A3 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 987 119</lang>
Note that bounds are checked when indexing from the array, or when combining with another array.
<lang J> (<5 5 5 5){A3 |index error</lang>
and
<lang J> A1+A3 |length error</lang>
For more introductory material on multi-dimensional arrays, you might be interested in chapter 5 and chapter 7 of the Learning J book.
Python
Python: In-built
Python has syntax (and hidden) support for the access of multi-dimensional arrays, but no in-built datatype that supports it.
A common method of simulating multi-dimensional arrays is to use dicts with N-element tuples as keys.
Function dict_as_mdarray allows for the creation of an initialised multi-dimensional array of a given size. Note how indexing must use the round brackets of a tuple inside the square brackets of normal dict indexing:
<lang python>>>> from pprint import pprint as pp # Pretty printer
>>> from itertools import product
>>>
>>> def dict_as_mdarray(dimensions=(2, 3), init=0.0):
... return {indices: init for indices in product(*(range(i) for i in dimensions))}
...
>>>
>>> mdarray = dict_as_mdarray((2, 3, 4, 5))
>>> pp(mdarray)
{(0, 0, 0, 0): 0.0,
(0, 0, 0, 1): 0.0, (0, 0, 0, 2): 0.0, (0, 0, 0, 3): 0.0, (0, 0, 0, 4): 0.0, (0, 0, 1, 0): 0.0,
...
(1, 2, 3, 0): 0.0, (1, 2, 3, 1): 0.0, (1, 2, 3, 2): 0.0, (1, 2, 3, 3): 0.0, (1, 2, 3, 4): 0.0}
>>> mdarray[(0, 1, 2, 3)] 0.0 >>> mdarray[(0, 1, 2, 3)] = 6.78 >>> mdarray[(0, 1, 2, 3)] 6.78 >>> mdarray[(0, 1, 2, 3)] = 5.4321 >>> mdarray[(0, 1, 2, 3)] 5.4321 >>> pp(mdarray) {(0, 0, 0, 0): 0.0,
(0, 0, 0, 1): 0.0, (0, 0, 0, 2): 0.0,
...
(0, 1, 2, 2): 0.0, (0, 1, 2, 3): 5.4321, (0, 1, 2, 4): 0.0,
...
(1, 2, 3, 3): 0.0, (1, 2, 3, 4): 0.0}
>>> </lang>
Python: numpy library
Python has the widely available numpy library for array specific operations. It creates numpy array types that take full advantage of Python's syntax support for multi-dimensional arrays.
Numpy arrays contain values of a single type arranged in a contiguous block of memory that can be further arranged to be compatible with C language or Fortran array layouts to aid the use of C and Fortran libraries. <lang python>>>> from numpy import * >>> >>> mdarray = zeros((2, 3, 4, 5), dtype=int8, order='F')
>>> mdarray array([[[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]]],
[[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]],
[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]]]], dtype=int8)
>>> mdarray[0, 1, 2, 3] 0 >>> mdarray[0, 1, 2, 3] = 123 >>> mdarray[0, 1, 2, 3] 123 >>> mdarray[0, 1, 2, 3] = 666 >>> mdarray[0, 1, 2, 3] -102 >>> mdarray[0, 1, 2, 3] = 255 >>> mdarray[0, 1, 2, 3] -1 >>> mdarray[0, 1, 2, 3] = -128 >>> mdarray[0, 1, 2, 3] -128 >>> mdarray array([[[[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0]],
[[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, -128, 0],
[ 0, 0, 0, 0, 0]],
[[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0]]],
[[[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0]],
[[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0]],
[[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 0]]]], dtype=int8)
>>> </lang>
Racket
Racket has multi-dimensional arrays as part of the standard math library. Instead of repeating the whole thing here, see the quick start page of the documentation, which describes all of what's asked here.
REXX
REXX supports multi-dimension (stemmed) arrays and the limit of the number of dimension varies with individual REXX interpreters, most (but not all) will probably be limited by the largest allowable clause length or source-line length, the smallest of which is 250 characters (included the periods), which would be around 125 dimensions.
The REXX language has something called stemmed arrays. For instance, for a stemmed array named antenna with two dimensions, to reference the element 2, 0 (and set that value to the variable g), one could code (note the use of periods after the variable name and also between the indices to the array dimensions: <lang rexx>g = antenna.2.0</lang> Memory allocation for stemmed arrays is not optimized, and the array elements are not contiguous.
The index to the array dimensions may be any integer, and indeed, even non-numeric.
The REXX language does not do bounds checking, but if signal on novalue is in effect, it can be used to trap (read) references of array elements that haven't been assigned a value (at the time of the read reference). <lang rexx>/*REXX pgm shows how to assign/show values of a multi-dimension array.*/
/*REXX arrays can start anywhere.*/
y.=0 /*set all values of Y array to 0.*/
/* [↑] bounds need not be given.*/
- =0 /*count for the number of SAYs. */
y.4.3.2.0= 3**7 /*set penultimate element to 2187*/
do i=0 for 5
do j=0 for 4
do k=0 for 3
do m=0 for 2; #=#+1 /*bump the SAY counter.*/
say 'y.'i"."j'.'k"."m '=' y.i.j.k.m
end /*m*/
end /*k*/
end /*j*/
end /*i*/
say say '# of elements displayed = ' # /*should be 5 * 4 * 3 * 2 or 5! */ exit /*stick a fork in it, we're done.*/
/*other versions of the 1st SAY */
say 'y.' || i || . || k || . || m '=' y.i.j.k.m
say 'y.'||i||.||k||.||m '=' y.i.j.k.m
say 'y.'i||.||k||.||m '=' y.i.j.k.m</lang>
output:
y.0.0.0.0 = 0 y.0.0.0.1 = 0 y.0.0.1.0 = 0 y.0.0.1.1 = 0 y.0.0.2.0 = 0 y.0.0.2.1 = 0 y.0.1.0.0 = 0 y.0.1.0.1 = 0 · · · y.4.2.2.1 = 0 y.4.3.0.0 = 0 y.4.3.0.1 = 0 y.4.3.1.0 = 0 y.4.3.1.1 = 0 y.4.3.2.0 = 2187 y.4.3.2.1 = 0 # of elements displayed = 120
Tcl
In Tcl, arrays are associative maps and lists are closer to what other languages name "arrays". Either can be used for multidimensional data, but the implementations (and implications!) are quite different.
It's worth briefly discussing both here. Since lists are closer to the theme of this page, they come first.
lists
Multi-dimensional lists are easily handled by nesting. Let's define a helper proc to construct such lists using lrepeat:
<lang Tcl>proc multilist {value args} {
set res $value
foreach dim [lreverse $args] {
set res [lrepeat $dim $res]
}
return $res
}</lang>
- Output:
<lang Tcl>% multilist x 2 x x % multilist x 2 3 {x x x} {x x x} % multilist x 2 3 4 {{x x x x} {x x x x} {x x x x}} {{x x x x} {x x x x} {x x x x}} </lang>
Both lset and lindex know how to access multi-dimensional lists:
<lang Tcl>% set ml [multilist 0 2 3 4] {{0 0 0 0} {0 0 0 0} {0 0 0 0}} {{0 0 0 0} {0 0 0 0} {0 0 0 0}} % lset ml 1 2 3 11 {{0 0 0 0} {0 0 0 0} {0 0 0 0}} {{0 0 0 0} {0 0 0 0} {0 0 0 11}} % lset ml 1 1 4 12 {{0 0 0 0} {0 0 0 0} {0 0 0 0}} {{0 0 0 0} {0 0 0 0 12} {0 0 0 11}} % lindex $ml 1 2 3 11</lang>
lsort and lsearch are among other useful commands that support nested lists.
arrays
Tcl arrays are collections of variables, not collections of values: thus they cannot nest. But since keys are simply strings, multidimensional data can be kept like this:
<lang Tcl>% array set x {
0,0 a 0,1 b 1,0 c 1,1 d
} % parray x x(0,0) = a x(0,1) = b x(1,0) = c x(1,1) = d % puts $x(0,1) b % set a 0 1 % set b 1 % puts $x($b,$a) c % set $x($b,$a) "not c" not c % parray x $b,$a x(1,0) = not c</lang>
Such an array can also be "sliced" with the array command:
<lang Tcl>% array get x 1,* 1,0 c 1,1 d % array names x 0,* 0,0 0,1</lang>
Note however that the order in which elements are returned from these operations is undefined! The last command might return {0,0 0,1} or {0,1 0,0} depending on how its keys are hashed, which is not under the programmer's control.
Using arrays like this for ordered data is suboptimal for this reason, and because iterating over elements is cumbersome. But it's a common technique for records:
<lang Tcl>% array set players {
1,name Fido 1,score 0 1,colour green
2,name Scratchy 2,score 99 2,colour pink
} % foreach player {1 2} {
puts "$players($player,name) is $players($player,colour) and has $players($player,score) points"
} Fido is green and has 0 points Scratchy is pink and has 99 points % </lang>
The interested reader should also be aware of the difference between arrays and dictionaries, and know that the latter are often preferred for record-like structures.