Odsecanje niza

U programiranju, odsecanje niza je operacija koja izvlači određene elemente iz jednog niza i smešta ih u drugi, uz izmene u dimenziji niza i u rasponu indeksa. Dva školska primera u kojima se ovakav metod koristi su izvlačenje podniske iz niza karaktera (npr: „gram” iz „programiranje”) ili vađenje reda ili kolone iz pravougaon matrice radi korišćenja iste kao vektor.

U zavisnosti od programskog jezika koji se koristi, elementi novonastalog niza mogu biti adresirani na određen način tako da dele memoriju sa elementima početnog niza.

Opis[уреди | уреди извор]

U jednodimenzionalnim nizovima kao što su vektori, redovi i niske, odsecanje se uglavnom se vrši tako što se vade uzastopni elementi u nizu. Na primer, kada osoba iz niza brojeva 2, 5, 7, 3, 8, 6, 4, 1 želi da odseče od 3. do 6. člana, dobija brojeve 7, 3, 8, 6. U programskim jezicima koji indeksiraju od 0, odsecanje bi se vršilo od indeksa "2" do "5".

Smanjivanje opsega indeksa na jedinstvenu vrednost s lakoćom odstranjuje taj indeks. Ovo se koristi u slučajevima kada osoba treba izvaditi vektore ili matrice iz trodimenzionalnih nizova. Meutim, budući da se opseg indeksa može definisati pri pokretanju, tipizirani jezici mogu da zahtevaju eksplicitno obeležje da bi eliminisali trivijalne indekse.

Opšti algoritam za odsecanje niza može biti implementiran referenciranjem svakog niza preko vektora dope, u kome bi se skladištile informacije o nizu ili pomoću deskriptora, koji sadrži adresu početka niza, rastojanje svakog indeksa od početka i odgovarajući koeficijent za indeksiranje. Ovaj metod omogućava veoma brzo transponovanje (premeštanje) niza, njegovo obrtanje, subsemplovanje, itd. U jezicima gde indeksiranje počinje od nule, kao što je slučaj sa programskim jezikom C, vektor dope niza koji sadrži d indeksa ima najmanje 1+2d parametra. U jezicima koji dozvoljavaju korišćenje nižih vrednosti, kao što je slučaj s Paskalom, vektor dope ima 1 + 3d parametra.

Istorijat[уреди | уреди извор]

Odsecanje niza je postojalo i pre otkrivanja kompilatora. U programskim jezicima kao funkcija ovaj metod počeo je da se koristi s Fortranom, više kao posledica nepostojećeg tipa i provere opsega, nego kao sam algoritam. Ovaj algoritam je implementiran u više programskih jezika, kao što su: Ada, Algol, Basic, Fortran, Gou, Matlab, Pajton, Perl i R.

U različitim programskim jezicima kroz istoriju[уреди | уреди извор]

1968: Algol[уреди | уреди извор]

 [3, 3]real a := ((1, 1, 1), (2, 4, 8), (3, 9, 27)); # deklaracija matrice promenljivih #
 [,]  real c = ((1, 1, 1), (2, 4, 8), (3, 9, 27));   # konstantna matrica, dimenzije # 
                                                     # matrice su implicitno deklarisane #

 ref[]real row := a[2,];                    # pseudoniz za odsečak niza #
 ref[]real col2 = a[, 2];                   # permanentni pseudoniz za drugu kolonu #

 print ((a[:, 2], newline));                # odsečak druge kolone #
 print ((a[1?a, :], newline));              # odsečak poslednjeg reda #
 print ((a[:, 2?a], newline));              # odsečak poslednje kolone #
 print ((a[:2, :2], newline));              # vodeći odsečak 2x2 podmatrice #

+1.0000₁₀+0 +4.0000₁₀+0 +9.0000₁₀+0
+3.0000₁₀+0 +9.0000₁₀+0 +2.7000₁₀+1
+1.0000₁₀+0 +8.0000₁₀+0 +2.7000₁₀+1
+1.0000₁₀+0 +1.0000₁₀+0 +2.0000₁₀+0 +4.0000₁₀+0

1970-e: MATLAB[уреди | уреди извор]

 > A = round(rand(3, 4, 5)*10) % 3x4x5 trodimenzionalna matrica ili kubni niz
 > A(:, :, 3) % 3x4 dvodimenzionalni niz
 
 ans =
 
   8  3  5  7
   8  9  1  4
   4  4  2  5
 
 > A(:, 2:3, 3) % 3x2 dvodimenzionalni niz
 
 ans =
 
   3 5
   9 1
   4 2

 > A(2:end, :, 3) % 2x4 dvodimenzionalni niz sa 'end' oznakom; radi na GNU Octave 3.2.4
 
 ans =

    6    1    4    6
   10    1    3    1

 > A(1, :, 3) % jednodimenzionalan niz
 
 ans =
 
   8  3  5  7
 
 > A(1, 2, 3) % vrednost jednog polja
 ans = 3

1976: R[уреди | уреди извор]

U programskom jeziku GNU R indeksiranje uvek počinje brojem 1 i, na osnovu toga, novi odsečci uvek počinju indeksom 1 za svaku dimenziju bez obzira na prethodne indekse. Dimenzije dužine 1 se ispuštaju (osim u slučaju deklaracije drop = FALSE ).

 > A <- array(1:60, dim = c(3, 4, 5)) # 3x4x5 trodimenzionalni niz
 > A[, , 3] # 3x4 dvodimenzionalan niz 
      [, 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 podskup trodimenzionalnog niza sa sačuvanim dimenzijama
 , , 1
 
      [, 1] [, 2]
 [1,]   28   31
 [2,]   29   32
 [3,]   30   33
 > A[, 2, 3]  # jednodimenzionalni niz
 [1] 28 29 30
 > A[1, 2, 3] # vrednost jednog polja
 [1] 28

1979: Bejsik (ZX80/81/Spektrum)[уреди | уреди извор]

Standardni ROM računara ZX80/81/Spektrum podržava operacije za odsecanje nizova i spajanje niski u Bejsiku:

10 LET a$="ABCDE"(2 to 4)
20 PRINT a$

Rezultat:

BCD

10 LET a$="ABCDE"
20 LET b$=a$(4 TO)+a$(2 TO 3)+a$(1)
30 PRINT b$

Rezultat:

DEBCA

1987: Perl[уреди | уреди извор]

Naveden je niz:

@a = (2, 5, 7, 3, 8, 6, 4);

prva tri elementa, središnja tri i poslednja tri elementa biće:

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

Perl podržava negativno indeksiranje. Indeks -1 je indeks poslednjeg elementa, -2 je indeks pretposlednjeg, itd.

@a[ 3.. $#a ];   # elementi od četvrtog do kraja niza (3, 8, 6, 4)
@a[ grep { !($_ % 3) } (0...$#a) ];    # prvi, četvrti i sedmi element niza (2,3,4)
@a[ grep { !(($_+1) % 3) } (0..$#a) ]; # svaki treći element niza (7,6)

1991: Pajton[уреди | уреди извор]

Ako postoji sledeća lista:

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

Onda se može uzeti odsečak korišćenjem notacije slične operaciji uzimanja elementa iz niza:

nums[3]   # jednako 7, tj. nema odsecanja
nums[:3]  # jednako [1, 3, 5], tj. od indeksa 0 do indeksa 3
nums[1:5] # jednako [3, 5, 7, 8]
nums[-3:] # jednako [8, 13, 20]

Pajton podržava negativno indeksiranje. Indeks -1 je indeks poslednjeg elementa, -2 je indeks pretposlednjeg itd. Takođe podržava i dodelu dodatnih kolona i vrednosti, primer:

nums[3::]  # jednako [7, 8, 13, 20], isti ispis kao za kod nums[3:]
nums[::3]  # jednako [1, 7, 20] (polazeći od indeksa 0 uzima se svaki treći element niza)
nums[1:5:2] # jednako [3, 7] (uzima se svaki drugi element niza od indeksa 1 do indeksa 5)

1992: Fortran[уреди | уреди извор]

U programskom jeziku Fortran odsečci su određeni sledećom formom:

lower_bound:upper_bound[:stride]

Obe granice su inkluzivne i mogu biti izostavljene. U tom slučaju su granice određene dužinom niza. Primer:

real, dimension(m, n):: a  ! deklaracija matrice
  
print *, a(:, 2) ! druga kolona
print *, a(m, :) ! poslednji red
print *, a(:10, :10) ! početna 10x10 matrica

1999: D[уреди | уреди извор]

Naveden je sledeći niz:

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

Isečak iz tog niza:

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

sadržaj b će biti [7, 3, 8]. Prvi indeks ovog odsečka je inkluzivan, dok je drugi ekskluzivan.

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

Stoga, dinamički niz c sada sadrži [8, 6] zato što unutar [], $ simbol označava dužinu niza.

Odsečci D niza kopiraju su u originalni niz:

b[2] = 10;

a sada sadrži [2, 5, 7, 3, 10, 6, 4, 1]. U cilju pravljenja kopije podataka niza, umesto originalnog niza:

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

2006: Cobra[уреди | уреди извор]

Cobra podržava odsecanje u sintaksi sličnoj Pajtonu. Navedna je ista:

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

onda su prva tri elementa, središnja tri i poslednja tri:

nums[:3]  # jednako [1, 3, 5]
nums[2:5] # jednako [5, 7, 8]
nums[-3:] # jednako [8, 13, 20]

Cobra podržava i ovakvu sintaksu za numeričke operacije s petljama:

for i in 2 : 5
    print i
# štampa 2, 3, 4

for j in 3
    print j
# štampa 0, 1, 2

2009: Gou[уреди | уреди извор]

Gou podržava sintaksu za odsecanje sličnu kao Pajton, s razlikom da negativno indeksiranje nije podržano. Nizovi i odsečci nizova mogu biti dodatno odsecani. Dat je odsečak:

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

onda će prva tri, središnja tri, poslednja tri i cela kopija odsečka niza biti:

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

2010: Cilk Plus[уреди | уреди извор]

Cilk Plus podržava sintaksu za odsecanje kao dodatak bibliotekama jezika C i C++.

array_base [lower_bound:length[:stride]]*

Izgled odsecanje u Cilk Plusu:

A[:]     // ceo vektor A
B[2:6]   // elementi 2 do 7 vektora B
C[:][5]  // kolona 5 matrice C
D[0:3:2] // elementi 0, 2 i 4 vektora D

Odsecanje niza u Cilk Plusu razlikuje se od odsecanja u Fortranu po sledećem:

drugi parametar je dužina (broj elemenata u odsečku), umesto gornje granice, kako bi se sačuvao standard biblioteke C.
odsecanje nikada ne pravi pomoćni niz tako da nije potrebno alocirati memoriju. Dodele se moraju savršeno poklapati ili ne poklapati uopšte, u ostalim slučajevima rezultat odsecanja nije definisan.

Vidi još[уреди | уреди извор]