Array slicing - WikiHQ

In computer programming, array slicing is an operation that extracts a subset of elements from an array and packages them as another array, possibly in a different dimension from the original.

Common examples of array slicing are extracting a substring from a string of characters, the "ell" in "hello", extracting a row or column from a two-dimensional array, or extracting a vector from a matrix.

Depending on the programming language, an array slice can be made out of non-consecutive elements. Also depending on the language, the elements of the new array may be aliased to (i.e., share memory with) those of the original array.

Details

For "one-dimensional" (single-indexed) arrays vectors, sequences, strings etc. the most common slicing operation is extraction of zero or more consecutive elements. If we have a vector containing elements (2, 5, 7, 3, 8, 6, 4, 1), and want to create an array slice from the 3rd to the 6th elements, we get (7, 3, 8, 6). In programming languages that use a 0-based indexing scheme, the slice would be from index 2 to 5.

Reducing the range of any index to a single value effectively removes the need for that index. This feature can be used, for example, to extract one-dimensional slices (vectors in 3D, including rows, columns, and tubes) 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.

General array slicing can be implemented (whether or not built into the language) by referencing every array through a dope vector or 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 indexing formula. This technique also allows immediate array transposition, index reversal, subsampling, etc. For languages like C, where the indices always start at zero, the dope vector of an array with d indices has at least 1 + 2d parameters. For languages that allow arbitrary lower bounds for indices, like Pascal, the dope vector needs 1 + 3d entries.

If the array abstraction does not support true negative indices (as the arrays of Ada and Pascal do), then negative indices for the bounds of the slice for a given dimension are sometimes used to specify an offset from the end of the array in that dimension. In 1-based schemes, -1 generally indicates the second-to-last item, while in a 0-based system, it refers to the very last item.

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. The concept was also alluded to in the preliminary report for the IAL (ALGOL 58) in that the syntax allowed one or more indices of an array element (or, for that matter, of a procedure call) to be omitted when used as an actual parameter.

Kenneth Iverson's APL (1957) had very flexible multi-dimensional array slicing, which contributed much to the language's 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 Ada, Cobra, D, Fortran 90, Go, Rust, Julia, MATLAB, Perl, Python, S-Lang, Windows PowerShell and the mathematical/statistical languages GNU Octave, S and R.

Timeline of slicing in various programming languages

1964: PL/I

PL/I provides two facilities for array slicing.

Using iSub DEFINING, an array slice can be declared using iSUB variables to map specific elements in a "base array" onto elements of the "defined array". iSUBs can define rows, columns, diagonals, or many-to-one mappings. The following example defines <code>Y</code> as a one-dimensional slice consisting of the diagonal elements of the two-dimensional array <code>X</code>.

DECLARE X(5,5);

DECLARE Y(5) DEFINED(X(1SUB,1SUB));

A reference to <code>Y(2)</code> is a reference to <code>X(2,2)</code>, and so on.

A slice, called a cross-section, of an array can be referred to by using asterisk as the subscript for one or more dimensions. The following code sets all the elements in the first column of <code>X</code> to zero. One or more subscripts can be specified by asterisks in an expression. As the first microcomputers emerged in the mid-1970s, HP was often used as the pattern for their BASIC dialects as well. Notable examples include 1977's Apple BASIC, 1978's Atari BASIC, and 1979's Sinclair BASIC. This style of manipulation generally offers advantages in terms of memory use, and was often chosen on systems that shipped with small amounts of memory. Only Sinclair's dialect differed in any meaningful way, using the keyword instead of a comma-separated list:

10 LET a$="ABCDE"(2 TO 4)

20 PRINT a$

</syntaxhighlight>

Slicing was also selected as the basis for the ANSI Full BASIC standard, using the colon as the separator and thus differentiating between slicing and array access:

10 DIM A$(5)

20 LET A$(2)="HELLO, WORLD"

30 PRINT A$(2)(1:5)

</syntaxhighlight>

While this style of access offered a number of advantages, especially for the small machines of the era, sometime after 1970 Digital Equipment Corporation introduced their own variation of BASIC that used the , and string functions. Microsoft BASIC was written on the PDP-10 and its BASIC was used as the pattern. Through the late 1970s the two styles were both widely used, but by the early 1980s the DEC-style functions were the de facto standard.

1970s: MATLAB

>> 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(2:end, :, 3) % 2x4 two-dimensional array using the 'end' keyword; works with GNU Octave 3.2.4

ans =

6 1 4 6

10 1 3 1

>> A(1, :, 3) % single-dimension array along second dimension

ans =

8 3 5 7

>> A(1, 2, 3) % single value

ans = 3

</syntaxhighlight>

The <code>:</code> operator implements the stride syntax (<code>lower_bound:upper_bound[:stride]</code>) by generating a vector. <code>1:5</code> evaluates as <code>[1, 2, 3, 4, 5]</code>. <code>1:9:2</code> evaluates as <code>[1, 3, 5, 7, 9]</code>. A bare <code>:</code> evaluates the same as <code>1:end</code>, with <code>end</code> determined by context.

1976: 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

</syntaxhighlight>

1977: Fortran 77

The Fortran 77 standard introduced the ability to slice and concatenate strings:

PROGRAM MAIN

PRINT *, 'ABCDE'(2:4)

END

</syntaxhighlight>

Produces:

BCD

</syntaxhighlight>

Such strings could be passed by <u>reference</u> to another subroutine, the length would also be passed transparently to the subroutine as a kind of short dope vector.

SUBROUTINE PRINT S(STR)

CHARACTER *(*)STR

PRINT *, STR

END

PROGRAM MAIN

CALL PRINT S('ABCDE'(2:4))

END

</syntaxhighlight>

Again produces:

BCD

</syntaxhighlight>

1983: Ada 83 and above

Ada 83 supports slices for all array types. Like Fortran 77 such arrays could be passed by <u>reference</u> to another subroutine, the length would also be passed transparently to the subroutine as a kind of short dope vector.

with Text_IO;

procedure Main is

Text : String := "ABCDE";

begin

Text_IO.Put_Line (Text (2 .. 4));

end Main;

</syntaxhighlight>

Produces:

BCD

</syntaxhighlight>

Note: Since in Ada indices are n-based the term <code>Text (2 .. 4)</code> will result in an Array with the base index of 2.

The definition for <code>Text_IO.Put_Line</code> is:

package Ada.Text_IO is

procedure Put_Line(Item : in String);

</syntaxhighlight>

The definition for <code>String</code> is:

package Standard is

subtype Positive is Integer range 1 .. Integer'Last;

type String is array(Positive range <>) of Character;

pragma Pack(String);

</syntaxhighlight>

As Ada supports true negative indices as in it places no special meaning on negative indices. In the example above the term <code> Some_History_Data (-30 .. 30)</code> would slice the <code>History_Data</code> from 31 BC to 30 AD (since there was no year zero, the year number 0 actually refers to 1 BC).

1987: Perl

If we have

as above, then the first 3 elements, middle 3 elements and last 3 elements would be:

@a[0..2]; # (2, 5, 7)

@a[2..4]; # (7, 3, 8)

@a[-3..-1]; # (8, 6, 4)

</syntaxhighlight>

Perl supports negative list indices. The -1 index is the last element, -2 the penultimate element, etc.

In addition, Perl supports slicing based on expressions, for example:

@a[ 3.. $#a ]; # 4th element until the end (3, 8, 6, 4)

@a[ grep { !($_ % 3) } (0...$#a) ]; # 1st, 4th and 7th element (2,3,4)

@a[ grep { !(($_+1) % 3) } (0..$#a) ]; # every 3rd element (7,6)

</syntaxhighlight>

1991: Python

For the following list:

nums: list[int] = [1, 3, 5, 7, 8, 13, 20]

</syntaxhighlight>

It is possible to slice by using a notation similar to element retrieval:

print(nums[3]) # no slicing

prints: 7

print(nums[:3]) # from index 0 (inclusive) until index 3 (exclusive)

prints: [1, 3, 5]

print(nums[1:5])

prints: [3, 5, 7, 8]

print(nums[-3:])

prints: [8, 13, 20]

</syntaxhighlight>

Note that Python allows negative list indices. The index -1 represents the last element, -2 the penultimate element, etc.

Python also allows a step property by appending an extra colon and a value. For example:

print(nums[3:])

prints: [7, 8, 13, 20]

print(nums[3::]) # == nums[3:]

prints: [7, 8, 13, 20]

print(nums[::3]) # starting at index 0 and getting every third element

prints: [1, 7, 20]

print(nums[1:5:2]) # from index 1 until index 5 and getting every second element

prints: [3, 7]

</syntaxhighlight>

The stride syntax (<code>nums[1:5:2]</code>) was introduced in the second half of the 1990s, as a result of requests put forward by scientific users in the Python "matrix-SIG" (special interest group).

Slice semantics potentially differ per object; new semantics can be introduced when operator overloading the indexing operator. With Python standard lists (which are dynamic arrays), every slice is a copy. Slices of NumPy arrays, by contrast, are views onto the same underlying buffer.

1992: Fortran 90 and above

In Fortran 90, slices are specified in the form

lower_bound:upper_bound[:stride]

</syntaxhighlight>

Both bounds are inclusive and can be omitted, in which case they default to the declared

array bounds. Stride defaults to 1. Example:

real, dimension(m, n):: a ! declaration of a matrix

print *, a(:, 2) ! second column

print *, a(m, :) ! last row

print *, a(:10, :10) ! leading 10-by-10 submatrix

</syntaxhighlight>

1994: Analytica

Each dimension of an array value in Analytica is identified by an Index variable. When slicing or subscripting, the syntax identifies the dimension(s) over which you are slicing or subscripting by naming the dimension. Such as:

Index I := 1..5 { Definition of a numerical Index }

Index J := ['A', 'B', 'C'] { Definition of a text-valued Index }

Variable X := Array(I, J, [[10, 20, 30], [1, 2, 3], ....]) { Definition of a 2D value }

X[I = 1, J = 'B'] -> 20 { Subscript to obtain a single value }

X[I = 1] -> Array(J, [10, 20, 30]) { Slice out a 1D array. }

X[J = 2] -> Array(I, [20, 2, ....]) { Slice out a 1D array over the other dimension. }

X[I = 1..3] {Slice out first four elements over I with all elements over J}

</syntaxhighlight>

Naming indexes in slicing and subscripting is similar to naming parameters in function calls instead of relying on a fixed sequence of parameters. One advantage of naming indexes in slicing is that the programmer does not have to remember the sequence of Indexes, in a multidimensional array. A deeper advantage is that expressions generalize automatically and safely without requiring a rewrite when the number of dimensions of X changes.

1998: S-Lang

Array slicing was introduced in version 1.0. Earlier versions did not

support this feature.

Suppose that A is a 1-d array such as

<pre>

A = [1:50]; % A = [1, 2, 3, ...49, 50]

</pre>

Then an array B of first 5 elements of A may be created using

<pre>

B = A:4;

</pre>

Similarly, B may be assigned to an array of the last 5 elements of A via:

<pre>

B = A-5:;

</pre>

Other examples of 1-d slicing include:

<pre>

A[-1] % The last element of A

A[*] % All elements of A

A::2 % All even elements of A

A1::2 % All odd elements of A

A-1::-2 % All even elements in the reversed order

A[[[0:3], [10:14]]] % Elements 0-3 and 10-14

</pre>

Slicing of higher-dimensional arrays works similarly:

<pre>

A[-1, *] % The last row of A

A[[1:5], [2:7]] % 2d array using rows 1-5 and columns 2-7

A[[5:1:-1], [2:7]] % Same as above except the rows are reversed

</pre>

Array indices can also be arrays of integers. For example, suppose

that <code>I = [0:9]</code> is an array of 10 integers. Then

<code>A[I]</code> is equivalent to an array of the first 10 elements

of <code>A</code>. A practical example of this is a sorting

operation such as:

<pre>

I = array_sort(A); % Obtain a list of sort indices

B = A[I]; % B is the sorted version of A

C = A[array_sort(A)]; % Same as above but more concise.

</pre>

1999: D

Consider the array:

int[] a = [2, 5, 7, 3, 8, 6, 4, 1];

</syntaxhighlight>

Take a slice out of it:

int[] b = a[2 .. 5];

</syntaxhighlight>

and the contents of <code>b</code> will be <code>[7, 3, 8]</code>. The first index of the slice is inclusive, the second is exclusive.

auto c = a[$ - 4 .. $ - 2];

</syntaxhighlight>

means that the dynamic array <code>c</code> now contains <code>[8, 6]</code> because inside the [] the <code>$</code> symbol refers to the length of the array.

D array slices are aliased to the original array, so:

b[2] = 10;

</syntaxhighlight>

means that <code>a</code> now has the contents <code>[2, 5, 7, 3, 10, 6, 4, 1]</code>. To create a copy of the array data, instead of only an alias, do:

auto b = a[2 .. 5].dup;

</syntaxhighlight>

Unlike Python, D slice bounds don't saturate, so code equivalent to this Python code is an error in D:

d: list[int] = [10, 20, 30]

print(d[1 : 5])

prints: [20, 30]

</syntaxhighlight>

2004: SuperCollider

The programming language SuperCollider implements some concepts from J/APL. Slicing looks as follows:

a = [3, 1, 5, 7] // assign an array to the variable a

a[0..1] // return the first two elements of a

a[..1] // return the first two elements of a: the zero can be omitted

a[2..] // return the element 3 till last one

a0, 3 // return the first and the fourth element of a

a0, 3 = [100, 200] // replace the first and the fourth element of a

a[2..] = [100, 200] // replace the two last elements of a

// assign a multidimensional array to the variable a

a = [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14], [15, 16, 17, 18, 19]];

a.slice(2, 3); // take a slice with coordinates 2 and 3 (returns 13)

a.slice(nil, 3); // take an orthogonal slice (returns [3, 8, 13, 18])

</syntaxhighlight>

2005: fish

Arrays in fish are always one-based, thus the indices of a new slice will begin with one, regardless of the previous indices.

> set A (seq 3 2 11) # $A is an array with the values 3, 5, 7, 9, 11

> echo $A[(seq 2)] # Print the first two elements of $A

3 5

> set B $A[1 2] # $B contains the first and second element of $A, i.e. 3, 5

> set -e A[$B]; echo $A # Erase the third and fifth elements of $A, print $A

3 5 9

</syntaxhighlight>

2006: Cobra

Cobra supports Python-style slicing. If you have a list

nums = [1, 3, 5, 7, 8, 13, 20]

</syntaxhighlight>

then the first 3 elements, middle 3 elements, and last 3 elements would be:

nums[:3] # equals [1, 3, 5]

nums[2:5] # equals [5, 7, 8]

nums[-3:] # equals [8, 13, 20]

</syntaxhighlight>

Cobra also supports slicing-style syntax for 'numeric for loops':

for i in 2 : 5

print i

prints 2, 3, 4

for j in 3

print j

prints 0, 1, 2

</syntaxhighlight>

2006: Windows PowerShell

Arrays are zero-based in PowerShell and can be defined using the comma operator:

PS> $a = 2, 5, 7, 3, 8, 6, 4, 1

PS> # Print the first two elements of $a:

PS> Write-Host -NoNewline $a[0, 1]

2 5

PS> # Take a slice out of it using the range operator:

PS> Write-Host -NoNewline $a[2..5]

7 3 8 6

PS> # Get the last 3 elements:

PS> Write-Host -NoNewline $a[-3..-1]

6 4 1

PS> # Return the content of the array in reverse order:

PS> Write-Host -NoNewline $a[($a.Length - 1)..0] # Length is a property of System.Object[]

1 4 6 8 3 7 5 2

</syntaxhighlight>

2009: Go

Go supports Python-style syntax for slicing (except negative indices are not supported). Arrays and slices can be sliced. If you have a slice

nums := []int{1, 3, 5, 7, 8, 13, 20}

</syntaxhighlight>

then the first 3 elements, middle 3 elements, last 3 elements, and a copy of the entire slice would be:

nums[:3] // equals []int{1, 3, 5}

nums[2:5] // equals []int{5, 7, 8}

nums[4:] // equals []int{8, 13, 20}

nums[:] // equals []int{1, 3, 5, 7, 8, 13, 20}

</syntaxhighlight>

Slices in Go are reference types, which means that different slices may refer to the same underlying array.

2010: Cilk Plus

Cilk Plus supports syntax for array slicing as an extension to C and C++.

array_base [lower_bound:length[:stride]]*

</syntaxhighlight>

Cilk Plus slicing looks as follows:

A[:] // All of vector A

B[2:6] // Elements 2 to 7 of vector B

C[:][5] // Column 5 of matrix C

D[0:3:2] // Elements 0, 2, 4 of vector D

</syntaxhighlight>

Cilk Plus's array slicing differs from Fortran's in two ways:

the second parameter is the length (number of elements in the slice) instead of the upper bound, in order to be consistent with standard C libraries;
slicing never produces a temporary, and thus never needs to allocate memory. Assignments are required to be either non-overlapping or perfectly overlapping, otherwise the result is undefined.

2012: Julia

Julia array slicing is like that of MATLAB, but uses square brackets. Example:

julia> x = rand(4, 3)

4x3 Array{Float64,2}:

0.323877 0.186253 0.600605

0.404664 0.894781 0.0955007

0.223562 0.18859 0.120011

0.149316 0.779823 0.0690126

julia> x[:, 2] # get the second column.

4-element Array{Float64,1}:

0.186253

0.894781

0.18859

0.779823

julia> x[1, :] # get the first row.

1x3 Array{Float64,2}:

0.323877 0.186253 0.600605

julia> x[1:2,2:3] # get the submatrix spanning rows 1,2 and columns 2,3

2x2 Array{Float64,2}:

0.186253 0.600605

0.894781 0.0955007

</syntaxhighlight>

2015: Rust

Rust supports array slicing, which are of type <code>&[T]</code> for an array type <code>[T]</code>.

let arr: [i32; 9] = [1, 2, 3, 4, 5, 6, 7, 8, 9];

let slice: &[i32] = &arr[2..6];

println("{:?}", slice); // prints: [3, 4, 5, 6]

</syntaxhighlight>

2017: C#

C# has two means of array slicing.

One way is the class <code>System.ArraySegment</code>. There is also the class <code>System.Span</code>, which allows for stack-allocated arrays or string slicing.

using System;

// ...

int[] a = [1, 2, 3, 4, 5, 6, 7, 8, 9];

// using an ArraySegment

ArraySegment<int> s1 = new(a, 2, 4); // [3, 4, 5, 6]

// using a Span

Span<int> s2 = a.AsSpan().Slice(2, 4); // [3, 4, 5, 6]

</syntaxhighlight>

2020: C++

In C++, an array slice can be created with <code>std::span</code>, which allows for non-owning views over collections or arrays.

import std;

using std::span;

using std::vector;

// ...

vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9};

// Creates a span using index 2, taking 4 elements

span<int> s1(v + 2, 4); // [3, 4, 5, 6]

// Creates a span over the whole vector and then takes a subspan beginning

// at index 2, taking 4 elements

span<int> s2 = span<int>(v, v.size()).subspan(2, 4); // [3, 4, 5, 6]

</syntaxhighlight>

References

Details

History

Timeline of slicing in various programming languages

1964: PL/I

1970s: MATLAB

1976: S/R

1977: Fortran 77

1983: Ada 83 and above

1987: Perl

1991: Python

1992: Fortran 90 and above

1994: Analytica

1998: S-Lang

1999: D

2004: SuperCollider

2005: fish

2006: Cobra

2006: Windows PowerShell

2009: Go

2010: Cilk Plus

2012: Julia

2015: Rust

2017: C#

2020: C++

See also

References