Одсецање низа

У програмирању, одсецање низа је операција која извлачи одређене елементе из једног низа и смешта их у други, уз измене у димензији низа и у распону индекса. Два школска примера у којима се овакав метод користи су извлачење подниске из низа карактера (нпр: „грам” из „програмирање”) или вађење реда или колоне из правоугаон матрице ради коришћења исте као вектор.

У зависности од програмског језика који се користи, елементи новонасталог низа могу бити адресирани на одређен начин тако да деле меморију са елементима почетног низа.

Опис[уреди | уреди извор]

У једнодимензионалним низовима као што су вектори, редови и ниске, одсецање се углавном се врши тако што се ваде узастопни елементи у низу. На пример, када особа из низа бројева 2, 5, 7, 3, 8, 6, 4, 1 жели да одсече од 3. до 6. члана, добија бројеве 7, 3, 8, 6. У програмским језицима који индексирају од 0, одсецање би се вршило од индекса "2" до "5".

Смањивање опсега индекса на јединствену вредност с лакоћом одстрањује тај индекс. Ово се користи у случајевима када особа треба извадити векторе или матрице из тродимензионалних низова. Меутим, будући да се опсег индекса може дефинисати при покретању, типизирани језици могу да захтевају експлицитно обележје да би елиминисали тривијалне индексе.

Општи алгоритам за одсецање низа може бити имплементиран референцирањем сваког низа преко вектора допе, у коме би се складиштиле информације о низу или помоћу дескриптора, који садржи адресу почетка низа, растојање сваког индекса од почетка и одговарајући коефицијент за индексирање. Овај метод омогућава веома брзо транспоновање (премештање) низа, његово обртање, субсемпловање, итд. У језицима где индексирање почиње од нуле, као што је случај са програмским језиком C, вектор допе низа који садржи д индекса има најмање 1+2д параметра. У језицима који дозвољавају коришћење нижих вредности, као што је случај с Паскалом, вектор допе има 1 + 3д параметра.

Историјат[уреди | уреди извор]

Одсецање низа је постојало и пре откривања компилатора. У програмским језицима као функција овај метод почео је да се користи с Фортраном, више као последица непостојећег типа и провере опсега, него као сам алгоритам. Овај алгоритам је имплементиран у више програмских језика, као што су: Ада, Алгол, Басиц, Фортран, Гоу, Матлаб, Пајтон, Перл и Р.

У различитим програмским језицима кроз историју[уреди | уреди извор]

1968: Алгол[уреди | уреди извор]

 [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-е: МАТЛАБ[уреди | уреди извор]

 > 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: Р[уреди | уреди извор]

У програмском језику ГНУ Р индексирање увек почиње бројем 1 и, на основу тога, нови одсечци увек почињу индексом 1 за сваку димензију без обзира на претходне индексе. Димензије дужине 1 се испуштају (осим у случају декларације 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: Бејсик (ЗX80/81/Спектрум)[уреди | уреди извор]

Стандардни РОМ рачунара ЗX80/81/Спектрум подржава операције за одсецање низова и спајање ниски у Бејсику:

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

Резултат:

BCD

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

Резултат:

DEBCA

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

Наведен је низ:

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

прва три елемента, средишња три и последња три елемента биће:

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

Перл подржава негативно индексирање. Индекс -1 је индекс последњег елемента, -2 је индекс претпоследњег, итд.

@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: Пајтон[уреди | уреди извор]

Ако постоји следећа листа:

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

Онда се може узети одсечак коришћењем нотације сличне операцији узимања елемента из низа:

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]

Пајтон подржава негативно индексирање. Индекс -1 је индекс последњег елемента, -2 је индекс претпоследњег итд. Такође подржава и доделу додатних колона и вредности, пример:

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: Фортран[уреди | уреди извор]

У програмском језику Фортран одсечци су одређени следећом формом:

lower_bound:upper_bound[:stride]

Обе границе су инклузивне и могу бити изостављене. У том случају су границе одређене дужином низа. Пример:

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[уреди | уреди извор]

Наведен је следећи низ:

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

Исечак из тог низа:

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

садржај b ће бити [7, 3, 8]. Први индекс овог одсечка је инклузиван, док је други ексклузиван.

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

Стога, динамички низ c сада садржи [8, 6] зато што унутар [], $ симбол означава дужину низа.

Одсечци D низа копирају су у оригинални низ:

b[2] = 10;

a сада садржи [2, 5, 7, 3, 10, 6, 4, 1]. У циљу прављења копије података низа, уместо оригиналног низа:

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

2006: Цобра[уреди | уреди извор]

Цобра подржава одсецање у синтакси сличној Пајтону. Наведна је иста:

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

онда су прва три елемента, средишња три и последња три:

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

Цобра подржава и овакву синтаксу за нумеричке операције с петљама:

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

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

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

Гоу подржава синтаксу за одсецање сличну као Пајтон, с разликом да негативно индексирање није подржано. Низови и одсечци низова могу бити додатно одсецани. Дат је одсечак:

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

онда ће прва три, средишња три, последња три и цела копија одсечка низа бити:

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: Цилк Плус[уреди | уреди извор]

Цилк Плус подржава синтаксу за одсецање као додатак библиотекама језика C и C++.

array_base [lower_bound:length[:stride]]*

Изглед одсецање у Цилк Плусу:

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

Одсецање низа у Цилк Плусу разликује се од одсецања у Фортрану по следећем:

други параметар је дужина (број елемената у одсечку), уместо горње границе, како би се сачувао стандард библиотеке C.
одсецање никада не прави помоћни низ тако да није потребно алоцирати меморију. Доделе се морају савршено поклапати или не поклапати уопште, у осталим случајевима резултат одсецања није дефинисан.

Види још[уреди | уреди извор]