Wycinanie szyku - Array slicing
W programowania , tablica krojenia jest operacją wyodrębnia podzbioru elementów z tablicy i pakiety je jako innej tablicy, ewentualnie w różnych wymiarach od oryginału.
Typowe przykłady dzielenia na tablice to wyodrębnianie podciągu z ciągu znaków, „ łokcia ” w „h ell o”, wyodrębnianie wiersza lub kolumny z dwuwymiarowej tablicy lub wyodrębnianie wektora z macierzy .
W zależności od języka programowania wycinek tablicy może składać się z elementów niekolejnych. Również w zależności od języka elementy nowej tablicy mogą być aliasowane (tj. Współdzielić pamięć) z elementami oryginalnej tablicy.
Detale
W przypadku tablic „jednowymiarowych” (jednowymiarowych) - wektorów, sekwencji, łańcuchów itd. - najczęściej wykonywaną operacją krojenia jest wyodrębnianie zera lub większej liczby kolejnych elementów. Tak więc, jeśli mamy wektor zawierający elementy (2, 5, 7, 3, 8, 6, 4, 1) i chcemy utworzyć wycinek tablicy od 3 do 6 pozycji, otrzymujemy (7, 3, 8, 6). W językach programowania, które używają schematu indeksowania opartego na 0, wycinek będzie miał indeks od 2 do 5 .
Zmniejszenie zakresu dowolnego indeksu do jednej wartości skutecznie eliminuje ten indeks. Tej funkcji można na przykład użyć do wyodrębnienia jednowymiarowych wycinków (wektorów: w 3D, rzędach, kolumnach i rurkach) lub dwuwymiarowych wycinków (prostokątnych macierzy) z trójwymiarowej tablicy. Jednakże, ponieważ zakres można określić w czasie wykonywania, języki ze sprawdzaniem typu mogą wymagać jawnej (w czasie kompilacji) notacji, aby faktycznie wyeliminować trywialne indeksy.
Ogólny podział tablicy można zaimplementować (niezależnie od tego, czy jest wbudowany w język, czy nie), odwołując się do każdej tablicy za pomocą wektora dope lub deskryptora - rekordu zawierającego adres pierwszego elementu tablicy, a następnie zakres każdego indeksu i odpowiedni współczynnik formuła indeksowania. Technika ta umożliwia również natychmiastową transpozycję tablicy , odwrócenie indeksu, podpróbkowanie itp. W językach takich jak C , w których indeksy zawsze zaczynają się od zera, wektor dope macierzy z indeksami d ma co najmniej 1 + 2 d parametrów. W przypadku języków, które dopuszczają dowolne dolne granice indeksów, takich jak Pascal , wektor dope wymaga wpisów 1 + 3 d .
Jeśli abstrakcja tablicy nie obsługuje prawdziwie ujemnych indeksów (jak na przykład tablice Ady i Pascala ), wówczas ujemne indeksy dla granic wycinka dla danego wymiaru są czasami używane do określenia przesunięcia od końca tablicy w ten wymiar. W schematach opartych na 1, -1 ogólnie oznaczałoby przedostatnią pozycję, podczas gdy w systemie opartym na 0 oznaczałoby to ostatnią pozycję.
Historia
Koncepcja krojenia była z pewnością znana jeszcze przed wynalezieniem kompilatorów . Cięcie na plasterki jako funkcja języka prawdopodobnie zaczęło się od FORTRANU (1957), bardziej jako konsekwencja nieistniejącego sprawdzania typu i zakresu niż przez projekt. Do koncepcji wspomniano również we wstępnym raporcie dotyczącym IAL (ALGOL 58), ponieważ składnia pozwalała na pominięcie jednego lub więcej indeksów elementu tablicy (lub, w tym przypadku, wywołania procedury), gdy jest używany jako rzeczywisty parametr.
Kenneth Iverson „s APL (1957) miał bardzo elastyczny wielowymiarowe tablicy krojenie, co przyczyniło się znacznie do ekspresyjnej władzy i popularności języku użytkownika.
ALGOL 68 (1968) wprowadził wszechstronne wielowymiarowe funkcje cięcia i przycinania tablic.
Funkcje wycinania tablic zostały włączone do kilku nowoczesnych języków, takich jak Ada 2005 , Cobra , D , Fortran 90 , Go , Rust , Julia , MATLAB , Perl , Python , S-Lang , Windows PowerShell i języki matematyczne / statystyczne GNU Octave , S i R .
Oś czasu wycinania w różnych językach programowania
1966: Fortran 66
Programiści Fortran 66 byli w stanie wykorzystać tylko cięcie macierzy po wierszu, a następnie tylko podczas przekazywania tego wiersza do podprogramu :
SUBROUTINE PRINT V(VEC, LEN)
REAL VEC(*)
PRINT *, (VEC(I), I = 1, LEN)
END
PROGRAM MAIN
PARAMETER(LEN = 3)
REAL MATRIX(LEN, LEN)
DATA MATRIX/1, 1, 1, 2, 4, 8, 3, 9, 27/
CALL PRINT V(MATRIX(1, 2), LEN)
END
Wynik:
2.000000 4.000000 8.000000
Zauważ, że w FORTRAN 66 nie ma wektora domieszki, dlatego długość wycinka musi być również przekazana jako argument - lub w inny sposób - do SUBROUTINE . Pascal i C w latach 70. mieli podobne ograniczenia.
1968: Algol 68
Raport końcowy Algol68 zawiera wczesny przykład krojenia, plastry są określone w postaci:
[lower bound:upper bound] ¢ for computers with extended character sets ¢
lub:
(LOWER BOUND..UPPER BOUND) # FOR COMPUTERS WITH ONLY 6 BIT CHARACTERS. #
Obie granice są włącznie i można je pominąć, w takim przypadku domyślnie odpowiadają zadeklarowanym granicom tablicy. Ani funkcja kroku, ani aliasy przekątnych nie są częścią poprawionego raportu.
Przykłady:
[3, 3]real a := ((1, 1, 1), (2, 4, 8), (3, 9, 27)); # declaration of a variable matrix # [,] real c = ((1, 1, 1), (2, 4, 8), (3, 9, 27)); # constant matrix, the size is implied #
ref[]real row := a[2,]; # alias/ref to a row slice # ref[]real col2 = a[, 2]; # permanent alias/ref to second column #
print ((a[:, 2], newline)); # second column slice # print ((a[1⌈a, :], newline)); # last row slice # print ((a[:, 2⌈a], newline)); # last column slice # print ((a[:2, :2], newline)); # leading 2-by-2 submatrix "slice" #
+1.000010+0 +4.000010+0 +9.000010+0 +3.000010+0 +9.000010+0 +2.700010+1 +1.000010+0 +8.000010+0 +2.700010+1 +1.000010+0 +1.000010+0 +2.000010+0 +4.000010+0
Lata 70 .: 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
1976: S / R
Tablice w S i GNU R są zawsze oparte na jedynkach, dlatego indeksy nowego wycinka będą rozpoczynać się od jednego dla każdego wymiaru, niezależnie od poprzednich indeksów. Wymiary o długości jednego zostaną pominięte (chyba że spadek = FAŁSZ). Nazwy wymiarów (jeśli są obecne) zostaną zachowane.
> 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
1977: Fortran 77
Standard Fortran 77 wprowadził możliwość cięcia i łączenia ciągów:
PROGRAM MAIN
PRINT *, 'ABCDE'(2:4)
END
Produkuje:
BCD
Takie łańcuchy mogłyby być przekazane przez odniesienie do innego podprogramu, długość byłby również przekazana w sposób przezroczysty do podprogramu jako rodzaj krótkiego wektora dope.
SUBROUTINE PRINT S(STR)
CHARACTER *(*)STR
PRINT *, STR
END
PROGRAM MAIN
CALL PRINT S('ABCDE'(2:4))
END
Ponownie daje:
BCD
1979: Sinclair BASIC ZX80 / 81 / Spectrum
Standardowa pamięć ROM ZX80 / 81 / Spectrum oferuje BASIC z możliwością cięcia i łączenia ciągów:
w części polecenia (x DO y), która wskazuje potrzebny wycinek tablicy, wartość xiy można pominąć, podając znaczenie użycia wszystkich połączonych komórek tablicy (OD x do końca) lub (początek do y). W przypadku tablic wielowymiarowych cięcie na plasterki jest możliwe tylko w przypadku wymiaru ostatniego poziomu.
10 LET a$="ABCDE"(2 to 4)
20 PRINT a$
Produkuje:
BCD
10 LET a$="ABCDE"
20 LET b$=a$(4 TO)+a$(2 TO 3)+a$(1)
30 PRINT b$
Produkuje:
DEBCA
1983: Ada 83 i wyżej
Ada 83 obsługuje plasterki dla wszystkich typów tablic. Podobnie jak w Fortranie 77, takie tablice mogą być przekazywane przez odniesienie do innego podprogramu, długość byłaby również przekazywana w sposób przezroczysty do podprogramu jako rodzaj krótkiego wektora dope.
with Text_IO;
procedure Main is
Text : String := "ABCDE";
begin
Text_IO.Put_Line (Text (2 .. 4));
end Main;
Produkuje:
BCD
Uwaga: Ponieważ indeksy Ady są oparte na n, termin Text (2 .. 4) da w wyniku Array z indeksem podstawowym równym 2.
Definicja Text_IO.Put_Line jest następująca:
package Ada.Text_IO is
procedure Put_Line(Item : in String);
Definicja String jest następująca:
package Standard is
subtype Positive is Integer range 1 .. Integer'Last;
type String is array(Positive range <>) of Character;
pragma Pack(String);
Ponieważ Ada obsługuje prawdziwie ujemne indeksy, ponieważ type History_Data_Array is array (-6000 .. 2010) of History_Data; nie nadaje specjalnego znaczenia indeksom ujemnym. W powyższym przykładzie termin Some_History_Data (-30 .. 30) przeciąłby okres History_Data od 31 rpne do 30 rne (ponieważ nie było roku zerowego, rok numer 0 w rzeczywistości odnosi się do 1 pne ).
1987: Perl
Jeśli mamy
@a = (2, 5, 7, 3, 8, 6, 4);
jak wyżej, to pierwsze 3 elementy, środkowe 3 elementy i ostatnie 3 elementy wyglądałyby następująco:
@a[0..2]; # (2, 5, 7)
@a[2..4]; # (7, 3, 8)
@a[-3..-1]; # (8, 6, 4)
Perl obsługuje indeksy list ujemnych. Indeks -1 to ostatni element, -2 przedostatni element itd. Ponadto Perl obsługuje wycinanie na podstawie wyrażeń, na przykład:
@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)
1991: Python
Jeśli masz następującą listę:
>>> nums = [1, 3, 5, 7, 8, 13, 20]
Następnie możliwe jest cięcie przy użyciu notacji podobnej do pobierania elementów:
>>> nums[3] # no slicing
7
>>> nums[:3] # from index 0 (inclusive) until index 3 (exclusive)
[1, 3, 5]
>>> nums[1:5]
[3, 5, 7, 8]
>>> nums[-3:]
[8, 13, 20]
Zauważ, że Python zezwala na indeksy list ujemnych. Indeks -1 reprezentuje ostatni element, -2 przedostatni element, itd. Python dopuszcza również właściwość step poprzez dołączenie dodatkowego dwukropka i wartości. Na przykład:
>>> nums[3:]
[7, 8, 13, 20]
>>> nums[3::] # == nums[3:]
[7, 8, 13, 20]
>>> nums[::3] # starting at index 0 and getting every third element
[1, 7, 20]
>>> nums[1:5:2] # from index 1 until index 5 and getting every second element
[3, 7]
Składnia stride ( nums[1:5:2] ) została wprowadzona w drugiej połowie lat 90. XX wieku w wyniku postulatów wysuwanych przez użytkowników naukowych w Pythonie „matrix-SIG” (grupa o szczególnych zainteresowaniach).
Semantyka wycinka może się różnić w zależności od obiektu; nową semantykę można wprowadzić, gdy operator przeciąża operator indeksowania. W przypadku standardowych list Pythona (które są tablicami dynamicznymi ) każdy wycinek jest kopią. Z kolei wycinki tablic NumPy są widokami na ten sam podstawowy bufor.
1992: Fortran 90 i nowsze
W Fortranie 90 plasterki są określone w formularzu
lower_bound:upper_bound[:stride]
Obie granice są włącznie i można je pominąć, w takim przypadku domyślnie odpowiadają zadeklarowanym granicom tablicy. Stride domyślnie przyjmuje wartość 1. Przykład:
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
1994: Analytica
Każdy wymiar wartości tablicy w Analytica jest identyfikowany przez zmienną indeksu. Podczas tworzenia wycinków lub indeksów dolnych składnia identyfikuje wymiar (y), według których wykonujesz wycinanie lub indeksowanie przez nazewnictwo wymiaru. Jak na przykład:
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}
Nazywanie indeksów w wycinaniu i indeksowaniu jest podobne do nazywania parametrów w wywołaniach funkcji, zamiast polegać na ustalonej sekwencji parametrów. Jedną z zalet nazywania indeksów przy wycinaniu jest to, że programista nie musi pamiętać sekwencji indeksów w wielowymiarowej tablicy. Głębszą zaletą jest to, że wyrażenia uogólniają się automatycznie i bezpiecznie bez konieczności przepisywania, gdy zmienia się liczba wymiarów X.
1998: S-Lang
Cięcie tablic zostało wprowadzone w wersji 1.0. Wcześniejsze wersje nie obsługiwały tej funkcji.
Załóżmy, że A jest tablicą 1-wymiarową, taką jak
A = [1:50]; % A = [1, 2, 3, ...49, 50]
Następnie tablicę B z pierwszych 5 elementów A można utworzyć za pomocą
B = A[[:4]];
Podobnie, B można przypisać do tablicy ostatnich 5 elementów A poprzez:
B = A[[-5:]];
Inne przykłady krojenia 1-w to:
A[-1] % The last element of A
A[*] % All elements of A
A[[::2]] % All even elements of A
A[[1::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
Cięcie tablic o wyższych wymiarach działa podobnie:
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
Indeksy tablicowe mogą być również tablicami liczb całkowitych. Na przykład załóżmy, że I = [0:9] jest to tablica 10 liczb całkowitych. To
A[I] jest odpowiednikiem tablicy pierwszych 10 elementów A . Praktycznym tego przykładem jest operacja sortowania, taka jak:
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.
1999: D.
Rozważ tablicę:
int[] a = [2, 5, 7, 3, 8, 6, 4, 1];
Wyjmij z tego kawałek:
int[] b = a[2 .. 5];
a zawartość b będzie [7, 3, 8] . Pierwszy indeks wycinka jest włączający, drugi wyłączny.
auto c = a[$ - 4 .. $ - 2];
oznacza, że tablica dynamiczna c zawiera teraz, [8, 6] ponieważ wewnątrz [] $ symbol odnosi się do długości tablicy.
D plasterki tablicy są aliasowane do oryginalnej tablicy, więc:
b[2] = 10;
oznacza, że a teraz ma zawartość [2, 5, 7, 3, 10, 6, 4, 1] . Aby utworzyć kopię danych tablicy zamiast aliasu, wykonaj:
auto b = a[2 .. 5].dup;
W przeciwieństwie do Pythona, granice wycinka D nie ulegają nasyceniu, więc kod odpowiadający temu kodowi w Pythonie jest błędem w D:
>>> d = [10, 20, 30]
>>> d[1 : 5]
[20, 30]
2004: SuperCollider
Język programowania SuperCollider implementuje pewne koncepcje z J / APL . Krojenie wygląda następująco:
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
a[[0, 3]] // return the first and the fourth element of a
a[[0, 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])
2005: ryby
Tablice w rybach są zawsze oparte na jedności, dlatego indeksy nowego wycinka będą rozpoczynać się od jedynki , niezależnie od poprzednich indeksów.
> 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
2006: Cobra
Cobra obsługuje krojenie w stylu Pythona. Jeśli masz listę
nums = [1, 3, 5, 7, 8, 13, 20]
wtedy pierwsze 3 elementy, środkowe 3 elementy, a ostatnie 3 elementy to:
nums[:3] # equals [1, 3, 5]
nums[2:5] # equals [5, 7, 8]
nums[-3:] # equals [8, 13, 20]
Cobra obsługuje również składnię w stylu wycinania dla `` numerycznych pętli dla '':
for i in 2 : 5
print i
# prints 2, 3, 4
for j in 3
print j
# prints 0, 1, 2
2006: Windows PowerShell
Tablice w programie PowerShell są liczone od zera i można je definiować przy użyciu operatora przecinka:
PS > $a = 2, 5, 7, 3, 8, 6, 4, 1
PS > # Print the first two elements of $a:
PS > "$($a[0, 1])"
2 5
PS > # Take a slice out of it using the range operator:
PS > "$($a[2..5])"
7 3 8 6
PS > # Get the last 3 elements:
PS > "$($a[-3..-1])"
6 4 1
PS > # Return the content of the array in reverse order:
PS > "$($a[($a.Length - 1)..0])" # Length is a property of System.Object[]
1 4 6 8 3 7 5 2
2009: Idź
Go obsługuje składnię w stylu Pythona do wycinania (z wyjątkiem ujemnych indeksów nie są obsługiwane). Tablice i plasterki można kroić. Jeśli masz kawałek
nums := []int{1, 3, 5, 7, 8, 13, 20}
wtedy pierwsze 3 elementy, środkowe 3 elementy, ostatnie 3 elementy i kopia całego wycinka wyglądałaby następująco:
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}
Plasterki w Go są typami odwołań, co oznacza, że różne wycinki mogą odnosić się do tej samej podstawowej tablicy.
2010: Cilk Plus
Cilk Plus obsługuje składnię wycinania tablic jako rozszerzenie C i C ++.
array_base [lower_bound:length[:stride]]*
Krojenie Cilk Plus wygląda następująco:
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
Cięcie macierzy Cilk Plus różni się od Fortrana na dwa sposoby:
- drugim parametrem jest długość (liczba elementów w wycinku) zamiast górnej granicy, aby zachować zgodność ze standardowymi bibliotekami C;
- krojenie nigdy nie tworzy tymczasowego, a zatem nigdy nie musi przydzielać pamięci. Przypisania muszą się nie nakładać lub całkowicie nakładać, w przeciwnym razie wynik będzie niezdefiniowany.
2012: Julia
Krojenie tablicy Julii jest podobne do cięcia w MATLAB-u , ale używa nawiasów kwadratowych. Przykład:
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