Array slicing
From Free net encyclopedia
In computer programming, array slicing is an operation that extracts certain elements from an array and packages them as another array, possibly with different number of indices (or dimensions) and different index ranges. Two common examples are extracting a substring from a string of characters (e.g. "kipe" from "wikipedia"), and extracting a row (or a column) of a rectangular matrix to be used as a vector.
Depending on the language and context, the elements of the new array may be aliased to (i.e., share memory with) those of the original array.
Contents |
Details
For "one-dimensional" (single-indexed) arrays — vectors, sequence, strings etc. — the most common slicing operation is extraction of zero or more consecutive elements. Thus, if we have a vector containing elements (2, 5, 7, 3, 8, 6, 4, 1), and we want to create an array slice from index 2 to 5, we get (7, 3, 8, 6).
Reducing the range of any index to a single value effectively eliminates that index. This feature can be used, for example, to extract one-dimensional slices (vectors) or two-dimensional slices (rectangular matrices) from a three-dimensional array. However, since the range can be specified at run-time, type-checked languages may require an explicit (compile-time) notation to actually eliminate the trivial indices.
Array slicing is implemented by referencing every array through a descriptor, a record that contains the address of the first array element, and then the range of each index and the corresponding coefficient in the element indexing formula. This technique also allows instant array transposition, flipping (index reversal), subsampling, etc.. For languages like C, where the indices always start at zero, the descriptor of an array with d indices has at least 1 + 2d parameters. For languages which allow arbitrary lower bounds for indices, like Pascal, the descriptor needs 1 + 3d entries.
History
The concept of slicing was surely known even before the invention of compilers. Slicing as a language feature probably started with FORTRAN (1957), more as a consequence of non-existent type and range checking than by design.
Kenneth Iverson's APL (1957) had very flexible multi-dimensional array slicing, which contributed much to the languages' expressive power and popularity.
ALGOL 68 (1968) introduced comprehensive multi-dimension array slicing and trimming features.
Array slicing facilities have been incorporated in several modern languages, such as Fortran 90, D, Perl, Python, Matlab, GNU Octave, Boo and the S and R programming languages.
Examples in programming languages
Perl
If we have
@x = (2, 5, 7, 3, 8, 6, 4, 1)
as above,
@x[2..5]
will represent the sliced array (7, 3, 8, 6).
D
Consider the statically allocated array:
static int[] a = [2, 5, 7, 3, 8, 6, 4, 1];
Take a slice out of it:
int[] b = a[2 .. 5];
and the contents of b[] will be [7, 3, 8]. The first index of the slice is inclusive, the second is exclusive. D array slices are aliased to the original array, so:
b[2] = 10;
means that a[] now has the contents [2, 5, 7, 3, 10, 6, 4, 1];
MATLAB / GNU Octave
> A = round(rand(3,4,5)*10) # 3x4x5 three-dimensional or cubic array > A(:,:,3) # 3x4 two-dimensional array along first and second dimensions ans = 8 3 5 7 8 9 1 4 4 4 2 5 > A(:,2:3,3) # 3x2 two-dimensional array along first and second dimensions ans = 3 5 9 1 4 2 > A(1,:,3) # single-dimension array along second dimension ans = 8 3 5 7 > A(1,2,3) # single value ans = 3
S / R
Arrays in S and GNU R are always one-based, thus the indices of a new slice will begin with one for each dimension, regardless of the previous indices. Dimensions with length of one will be dropped (unless drop=FALSE). Dimension names (where present) will be preserved.
> A <- array(1:60,dim=c(3,4,5)) # 3x4x5 three-dimensional or cubic array
> A[,,3] # 3x4 two-dimensional array along first and second dimensions
[,1] [,2] [,3] [,4]
[1,] 25 28 31 34
[2,] 26 29 32 35
[3,] 27 30 33 36
> A[,2:3,3,drop=FALSE] # 3x2x1 cubic array subset (preserved dimensions)
, , 1
[,1] [,2]
[1,] 28 31
[2,] 29 32
[3,] 30 33
> A[,2,3] # single-dimension array along first dimension
[1] 28 29 30
> A[1,2,3] # single value
[1] 28