Krájení pole - Array slicing
V programování počítače , array krájení je operace, která vybírá podmnožinu prvků z pole a balíků ně jako jiná pole, případně v jiném rozměru od originálu.
Běžnými příklady krájení pole je extrahování podřetězce z řetězce znaků, „ ell “ v „h ell o“, extrahování řádku nebo sloupce z dvourozměrného pole nebo extrahování vektoru z matice .
V závislosti na programovacím jazyce může být řez pole vytvořen z nenasledujících prvků. Také v závislosti na jazyce mohou být prvky nového pole aliasovány (tj. Sdílet paměť) s prvky původního pole.
Detaily
Pro „jednorozměrná“ (jednoindexovaná) pole - vektory, sekvence, řetězce atd. - je nejběžnější operací krájení extrakce nulového nebo více po sobě jdoucích prvků. Pokud tedy máme vektor obsahující prvky (2, 5, 7, 3, 8, 6, 4, 1) a chceme vytvořit řez pole od 3. do 6. položky, dostaneme (7, 3, 8, 6). V programovacích jazycích, které používají schéma indexování na základě 0, by byl řez od indexu 2 do 5 .
Omezení rozsahu libovolného indexu na jednu hodnotu tento index účinně eliminuje. Tuto funkci lze použít například k extrakci jednorozměrných řezů (vektory: ve 3D, řádků, sloupců a trubek) nebo dvourozměrných řezů (obdélníkové matice) z trojrozměrného pole. Vzhledem k tomu, že rozsah lze určit za běhu, mohou jazyky s kontrolou typu vyžadovat explicitní notaci (kompilaci), aby skutečně eliminovaly triviální indexy.
Obecný výřez pole lze implementovat (ať už je nebo není zabudován do jazyka) odkazem na každé pole prostřednictvím dope vektoru nebo deskriptoru - záznamu, který obsahuje adresu prvního prvku pole a poté rozsah každého indexu a odpovídající koeficient v indexovací vzorec. Tato technika také umožňuje okamžitou transpozici pole , obrácení indexu, podvzorkování atd. U jazyků jako C , kde indexy vždy začínají nulou, má dopingový vektor pole s d indexy alespoň 1 + 2 d parametry. U jazyků, které umožňují libovolné nižší meze indexů, jako je Pascal , potřebuje dope vektor 1 + 3 d položky.
Pokud abstrakce pole nepodporuje skutečné záporné indexy (jako například pole Ada a Pascal ), pak se záporné indexy pro hranice řezu pro danou dimenzi někdy používají k určení posunu od konce pole v tu dimenzi. V schématech založených na 1 by -1 obecně označovalo předposlední položku, zatímco v systému založeném na 0 by to znamenalo úplně poslední položku.
Dějiny
Koncept krájení byl jistě známý už před vynálezem kompilátorů . Řezání jako jazyková funkce pravděpodobně začalo u FORTRANU (1957), spíše jako důsledek neexistující kontroly typu a rozsahu než podle návrhu. Tento koncept byl zmiňován také v předběžné zprávě pro IAL (ALGOL 58) v tom smyslu, že syntaxe umožňovala vynechat jeden nebo více indexů prvku pole (nebo, tedy, volání procedury), když se používá jako skutečný parametr.
Kenneth Iverson ‚s APL (1957) měla velmi flexibilní multi-dimenzionální pole krájení, který přispěl hodně expresivní síly jazykovém a popularity.
ALGOL 68 (1968) představil komplexní vícerozměrné funkce krájení a ořezávání pole.
Zařízení pro krájení polí byla začleněna do několika moderních jazyků, jako jsou Ada 2005 , Cobra , D , Fortran 90 , Go , Rust , Julia , MATLAB , Perl , Python , S-Lang , Windows PowerShell a matematické / statistické jazyky GNU Octave , S a R .
Časová osa krájení v různých programovacích jazycích
1966: Fortran 66
Programátoři Fortranu 66 byli schopni využít výhody krájení matic po řádcích, a to pouze při předávání řádku 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
Výsledek:
2.000000 4.000000 8.000000
Všimněte si, že ve FORTRANU 66 není žádný dopovací vektor, proto musí být délka řezu také předána jako argument - nebo nějakým jiným způsobem - do SUBROUTINE . 1970 Pascal a C měli podobná omezení.
1968: Algol 68
Závěrečná zpráva Algol68 obsahuje časný příklad krájení, plátky jsou specifikovány ve tvaru:
[lower bound:upper bound] ¢ for computers with extended character sets ¢
nebo:
(LOWER BOUND..UPPER BOUND) # FOR COMPUTERS WITH ONLY 6 BIT CHARACTERS. #
Obě hranice jsou inkluzivní a lze je vynechat, v takovém případě mají výchozí hodnoty deklarovaných hranic pole. Součástí revidované zprávy není ani krok, ani aliasy diagonálních řezů.
Příklady:
[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
70. léta: 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
Pole v S a GNU R jsou vždy jedna, takže indexy nového řezu začnou pro každou dimenzi jedním , bez ohledu na předchozí indexy. Rozměry s délkou jednoho budou vynechány (pokud drop = FALSE). Názvy dimenzí (pokud jsou k dispozici) zůstanou zachovány.
> 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 představil schopnost krájení a zřetězení řetězců:
PROGRAM MAIN
PRINT *, 'ABCDE'(2:4)
END
Vyrábí:
BCD
Takové řetězce by mohly být předány odkazem na jiný podprogram, délka by byla také předána transparentně podprogramu jako druh krátkého dopovaného vektoru.
SUBROUTINE PRINT S(STR)
CHARACTER *(*)STR
PRINT *, STR
END
PROGRAM MAIN
CALL PRINT S('ABCDE'(2:4))
END
Opět produkuje:
BCD
1979: Sinclair BASIC ZX80 / 81 / Spectrum
Standardní ROM ZX80 / 81 / Spectrum nabízí BASIC se schopností krájet a zřetězovat řetězce:
v příkazové části (x TO y), která poukazuje na potřebný řez pole, lze hodnoty xay vynechat, což dává smysl použít všechny zřetězené buňky pole (FROM x TO end) nebo (begin TO y). U vícerozměrných polí je krájení možné pouze s dimenzí poslední úrovně.
10 LET a$="ABCDE"(2 to 4)
20 PRINT a$
Vyrábí:
BCD
10 LET a$="ABCDE"
20 LET b$=a$(4 TO)+a$(2 TO 3)+a$(1)
30 PRINT b$
Vyrábí:
DEBCA
1983: Ada 83 a vyšší
Ada 83 podporuje řezy pro všechny typy polí. Podobně jako Fortran 77 by taková pole mohla být předána odkazem na jiný podprogram, délka by byla také předána transparentně podprogramu jako jakýsi krátký dopovací vektor.
with Text_IO;
procedure Main is
Text : String := "ABCDE";
begin
Text_IO.Put_Line (Text (2 .. 4));
end Main;
Vyrábí:
BCD
Poznámka: Jelikož indexy Ada jsou založeny na n, Text (2 .. 4) bude mít termín za následek pole se základním indexem 2.
Definice pro Text_IO.Put_Line je:
package Ada.Text_IO is
procedure Put_Line(Item : in String);
Definice pro String je:
package Standard is
subtype Positive is Integer range 1 .. Integer'Last;
type String is array(Positive range <>) of Character;
pragma Pack(String);
Protože Ada podporuje skutečné záporné indexy, type History_Data_Array is array (-6000 .. 2010) of History_Data; nedává záporným indexům žádný zvláštní význam. Ve výše uvedeném příkladu Some_History_Data (-30 .. 30) by tento výraz rozdělil období History_Data od 31 př. N. L. Do 30 n. L. (Protože neexistoval rok nula, rok číslo 0 ve skutečnosti odkazuje na 1 př . N. L. ).
1987: Perl
Pokud ano
@a = (2, 5, 7, 3, 8, 6, 4);
jako výše, pak první 3 prvky, prostřední 3 prvky a poslední 3 prvky by byly:
@a[0..2]; # (2, 5, 7)
@a[2..4]; # (7, 3, 8)
@a[-3..-1]; # (8, 6, 4)
Perl podporuje záporné indexy seznamů. -1 index je poslední prvek, -2 předposlední prvek atd. Kromě toho Perl podporuje krájení na základě výrazů, například:
@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
Pokud máte následující seznam:
>>> nums = [1, 3, 5, 7, 8, 13, 20]
Pak je možné řezat pomocí notace podobné načítání prvků:
>>> 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]
Upozorňujeme, že Python umožňuje záporné indexy seznamů. Index -1 představuje poslední prvek, -2 předposlední prvek atd. Python také umožňuje vlastnost step přidáním dvojtečky a hodnoty. Například:
>>> 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]
Stride syntax ( nums[1:5:2] ) byl představen ve druhé polovině 90. let jako výsledek požadavků předložených vědeckými uživateli v Pythonu „matrix-SIG“ (zájmová skupina).
Sémantika řezu se potenciálně liší podle objektu; nová sémantika může být zavedena při přetížení operátoru indexování operátorem. Se standardními seznamy Pythonu (což jsou dynamická pole ) je každý řez kopií. Plátky polí NumPy jsou naopak pohledy na stejnou podkladovou vyrovnávací paměť.
1992: Fortran 90 a vyšší
Ve Fortranu 90 jsou řezy specifikovány ve formuláři
lower_bound:upper_bound[:stride]
Obě hranice jsou inkluzivní a lze je vynechat, v takovém případě mají výchozí hodnoty deklarovaných hranic pole. Výchozí hodnota kroku je 1. Příklad:
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ždá dimenze hodnoty pole v Analytica je identifikována indexovou proměnnou. Při krájení nebo dolním indexu syntaxe identifikuje dimenzi (dimenze), nad nimiž krájíte nebo dolní index, pojmenováním dimenze. Jako:
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}
Pojmenování indexů při krájení a dolním indexování je podobné jako pojmenování parametrů ve volání funkcí namísto spoléhání se na pevnou sekvenci parametrů. Jednou z výhod pojmenování indexů při krájení je, že si programátor nemusí pamatovat sekvenci indexů ve vícerozměrném poli. Hlubší výhodou je, že výrazy se generalizují automaticky a bezpečně, aniž by bylo nutné přepsat, když se počet kót X změní.
1998: S-Lang
Řezání polí bylo zavedeno ve verzi 1.0. Starší verze tuto funkci nepodporovaly.
Předpokládejme, že A je 1-d pole jako např
A = [1:50]; % A = [1, 2, 3, ...49, 50]
Potom může být vytvořeno pole B prvních 5 prvků A pomocí
B = A[[:4]];
Podobně může být B přiřazeno k poli posledních 5 prvků A prostřednictvím:
B = A[[-5:]];
Mezi další příklady 1-d krájení patří:
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
Krájení polí vyšších rozměrů funguje podobně:
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
Pole indexy mohou být také pole celých čísel. Předpokládejme například, že I = [0:9] jde o pole 10 celých čísel. Pak
A[I] je ekvivalentní k poli prvních 10 prvků A . Praktickým příkladem je operace řazení, jako například:
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
Zvažte pole:
int[] a = [2, 5, 7, 3, 8, 6, 4, 1];
Vyjměte z toho plátek:
int[] b = a[2 .. 5];
a obsah b bude [7, 3, 8] . První index řezu je inkluzivní, druhý je exkluzivní.
auto c = a[$ - 4 .. $ - 2];
znamená, že dynamické pole c nyní obsahuje, [8, 6] protože uvnitř [] $ symbol odkazuje na délku pole.
Řezy pole D jsou aliasovány k původnímu poli, takže:
b[2] = 10;
znamená, že a nyní má obsah [2, 5, 7, 3, 10, 6, 4, 1] . Chcete-li vytvořit kopii dat pole, nikoli pouze alias, postupujte takto:
auto b = a[2 .. 5].dup;
Na rozdíl od Pythonu hranice D řezu nenasycují, takže kód ekvivalentní tomuto kódu Pythonu je chyba v D:
>>> d = [10, 20, 30]
>>> d[1 : 5]
[20, 30]
2004: SuperCollider
Programovací jazyk SuperCollider implementuje některé koncepty z J / APL . Krájení vypadá následovně:
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
Pole v rybách jsou vždy jedna, takže indexy nového řezu budou začínat jedním , bez ohledu na předchozí indexy.
> 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 podporuje krájení ve stylu Pythonu. Pokud máte seznam
nums = [1, 3, 5, 7, 8, 13, 20]
pak první 3 prvky, prostřední 3 prvky a poslední 3 prvky by byly:
nums[:3] # equals [1, 3, 5]
nums[2:5] # equals [5, 7, 8]
nums[-3:] # equals [8, 13, 20]
Cobra také podporuje syntaxi ve stylu krájení pro „numeric for loops“:
for i in 2 : 5
print i
# prints 2, 3, 4
for j in 3
print j
# prints 0, 1, 2
2006: Windows PowerShell
Pole jsou v PowerShellu založená na nule a lze je definovat pomocí čárky:
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: Jdi
Go podporuje syntaxi pro krájení ve stylu Pythonu (kromě toho, že záporné indexy nejsou podporovány). Pole a plátky lze krájet. Pokud máte plátek
nums := []int{1, 3, 5, 7, 8, 13, 20}
pak první 3 prvky, prostřední 3 prvky, poslední 3 prvky a kopie celého řezu budou:
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}
Řezy v Go jsou referenční typy, což znamená, že různé řezy mohou odkazovat na stejné základní pole.
2010: Cilk Plus
Cilk Plus podporuje syntaxi pro krájení pole jako rozšíření C a C ++.
array_base [lower_bound:length[:stride]]*
Krájení Cilk Plus vypadá následovně:
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
Řezání pole Cilk Plus se od Fortranu liší dvěma způsoby:
- druhým parametrem je délka (počet prvků v řezu) namísto horní hranice, aby byla konzistentní se standardními knihovnami C;
- krájení nikdy neprodukuje dočasné, a proto nikdy nepotřebuje přidělit paměť. Přiřazení musí být buď nepřekrývající se, nebo dokonale se překrývající, jinak je výsledek nedefinovaný.
2012: Julia
Řezání pole Julia je podobné jako u MATLABu , ale používá hranaté závorky. Příklad:
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