Array dasturlash - Array programming

Paradigmalar dasturlash

Yilda Kompyuter fanlari, massivlarni dasturlash operatsiyalarni bir vaqtning o'zida butun qiymatlar to'plamiga qo'llashga imkon beradigan echimlarni nazarda tutadi. Bunday echimlar odatda ishlatiladi ilmiy va muhandislik sozlamalari.

Massiv dasturlashni qo'llab-quvvatlaydigan zamonaviy dasturlash tillari (shuningdek, ular nomi bilan ham tanilgan) vektor yoki ko'p o'lchovli tillar) operatsiyalarni umumlashtirish uchun maxsus ishlab chiqilgan skalar uchun shaffof murojaat qilish vektorlar, matritsalar va yuqori o'lchovli massivlar. Bunga quyidagilar kiradi APL, J, Fortran 90, Mata, MATLAB, Analytica, TK hal qiluvchi (ro'yxatlar sifatida), Oktava, R, Cilk Plus, Yuliya, Perl ma'lumotlar tili (PDL), Wolfram tili, va NumPy ga kengaytirish Python. Ushbu tillarda butun massivlarda ishlaydigan operatsiyani a deb atash mumkin vektorlangan operatsiya,[1] a-da bajarilganligidan qat'iy nazar vektorli protsessor (vektor ko'rsatmalarini amalga oshiradigan) yoki yo'q. Array dasturlash ibtidoiylari ma'lumotlarni manipulyatsiya qilish to'g'risida keng fikrlarni qisqa ifoda etadi. Qisqartirish darajasi ba'zi holatlarda keskin bo'lishi mumkin: massiv dasturlash tilini topish odatiy holdir bitta layner ob'ektga yo'naltirilgan kodning bir nechta sahifasini talab qiladi.

Massiv tushunchalari

Massiv dasturlashning asosiy g'oyasi shundan iboratki, operatsiyalar bir vaqtning o'zida butun qiymatlar to'plamiga taalluqlidir. Bu buni qiladi yuqori darajadagi dasturlash model, chunki u dasturchiga individual skaler operatsiyalarining aniq ko'chadan murojaat qilmasdan, ma'lumotlarning butun yig'indilari ustida ishlashga va ishlashga imkon beradi.

Kennet E. Iverson qator dasturlashning mantiqiy asoslarini tavsifladi (aslida murojaat qilingan) APL ) quyidagicha:[2]

aksariyat dasturlash tillari matematik yozuvlardan qat'iyan kam va fikrlash vositasi sifatida, masalan, amaliy matematik tomonidan muhim deb hisoblanadigan usullardan kam foydalaniladi.

Tezis shundan iboratki, dasturlash tillarida bajariladigan va universallikning afzalliklari, yaxlit yaxlit tilda, matematik yozuvlar tomonidan taqdim etiladigan afzalliklar bilan samarali birlashtirilishi mumkin. biron bir yozuvni tavsiflash va o'rganish qiyinligini uning natijalarini o'zlashtirishning qiyinchiliklaridan farqlash muhimdir. Masalan, matritsali mahsulotni hisoblash qoidalarini o'rganish oson, ammo uning ta'sirini (assotsiativlik, qo'shilish ustidan taqsimlanishi va chiziqli funktsiyalar va geometrik amallarni ifodalash qobiliyati kabi) o'zlashtirish. .

Darhaqiqat, nota yozuvining juda ko'pligi, kashfiyotlar uchun taklif qiladigan ko'plab xususiyatlar tufayli uni o'rganishni qiyinlashtirishi mumkin.

[...]

Kompyuterlar va dasturlash tillari foydalanuvchilari ko'pincha birinchi navbatda algoritmlarni bajarish samaradorligi haqida qayg'uradilar va shuning uchun bu erda keltirilgan algoritmlarning aksariyatini bekor qilishlari mumkin. Bunday ishdan bo'shatish uzoqni nazarda tutadi, chunki algoritmning aniq bayonoti odatda yanada samarali algoritmni olish uchun asos bo'lib xizmat qilishi mumkin.

Massiv dasturlash va fikrlashning asosi ma'lumotlar elementlarining bir-biriga o'xshash yoki qo'shni bo'lgan xususiyatlarini topish va ulardan foydalanishdir. Ma'lumotlarni uning tarkibiy qismlariga (yoki) bilvosita buzadigan ob'ekt yo'nalishidan farqli o'laroq skalar miqdorlar), massiv yo'nalishi ma'lumotlarni guruhlash va bir xil ishlov berishni qo'llashga qaraydi.

Funktsiya darajasi o'xshashligi bo'yicha umuman dasturlash tillarini massivlash uchun muhim tushuncha tensor matematikadagi daraja: ma'lumotlar ustida ishlaydigan funktsiyalar ular bajaradigan o'lchovlar soni bo'yicha tasniflanishi mumkin. Oddiy ko'paytirish, masalan, nol o'lchovli ma'lumotlarda (individual raqamlar) ishlaydiganligi sababli skaler darajali funktsiya. The o'zaro faoliyat mahsulot operatsiya vektor daraja funktsiyasining misoli, chunki u skalar bilan emas, balki vektorlarda ishlaydi. Matritsani ko'paytirish 2 darajali funktsiyaga misol, chunki u 2 o'lchovli ob'ektlarda (matritsalarda) ishlaydi. Operatorlarni yig'ish kirish ma'lumotlari massivining o'lchovliligini bir yoki bir nechta o'lchamlarga kamaytirish. Masalan, elementlarni yig'ish kirish massivini 1 o'lchov bilan yiqitadi.

Foydalanadi

Array dasturlash juda mos keladi yashirin parallellashtirish; hozirgi kunda juda ko'p tadqiqotlar mavzusi. Bundan tashqari, Intel 1997 yildan keyin ishlab chiqilgan va ishlab chiqarilgan mos protsessorlarda turli xil ko'rsatmalar to'plamining kengaytmalari mavjud edi MMX va davom ettirish SSSE3 va 3DNow!, ularga ibtidoiy kiradi SIMD qator imkoniyatlari. Massivni qayta ishlash farqlanadi parallel ishlov berish bunda bitta fizik protsessor bir vaqtning o'zida bir guruh elementlar bo'yicha operatsiyalarni bajaradi, parallel ishlov berish esa kattaroq muammoni kichiklarga ajratishga qaratilgan (MIMD ) ko'plab protsessorlar tomonidan qismlarga bo'lingan holda hal qilinishi kerak. Ikki yoki undan ortiq yadroli protsessorlar bugungi kunda tobora keng tarqalgan.

Tillar

Massiv dasturlash tillarining kanonik misollari Fortran, APL va J. Boshqalarga quyidagilar kiradi: A +, Analytica, Chapel, IDL, Yuliya, K, Klong, Q, Mata, Wolfram tili, MATLAB, MOLSF, NumPy, GNU oktavi, PDL, R, S-Lang, SAC, Nial, ZPL va TI-BASIC.

Skalar tillari

Kabi skalar tillarida C va Paskal, operatsiyalar faqat bitta qiymatlarga tegishli, shuning uchun a+b ikkita raqamning qo'shilishini ifodalaydi. Bunday tillarda bitta massivni boshqasiga qo'shish uchun indekslash va ko'chirish kerak, kodlash zerikarli.

uchun (men = 0; men < n; men++)    uchun (j = 0; j < n; j++)        a[men][j] += b[men][j];

Massivga asoslangan tillarda, masalan Fortran, yuqoridagi ichki for-loop bir qatorda massiv formatida yozilishi mumkin,

a = a + b

yoki muqobil ravishda ob'ektlarning massiv xususiyatini ta'kidlash uchun,

a(:,:) = a(:,:) + b(:,:)

Array tillari

Massiv tillarida operatsiyalar ikkala skalar va massivlarga tatbiq qilish uchun umumlashtiriladi. Shunday qilib, a+b agar ikkita skalerning yig'indisini ifoda etsa, agar a va b skalar yoki agar ular massiv bo'lsa, ikkita massivning yig'indisi.

Massiv tili dasturlashni soddalashtiradi, lekin, ehtimol, taniqli xarajatlarga mavhumlik uchun jazo.[3][4][5] Qo'shimchalar kodlashning qolgan qismidan ajratilgan holda amalga oshirilganligi sababli, ular eng maqbul darajada ishlab chiqarmasligi mumkin samarali kod. (Masalan, bir xil massivning boshqa elementlarining qo'shimchalari keyinchalik bir xil ijro paytida yuz berishi mumkin, bu esa keraksiz takroriy qidiruvlarni keltirib chiqaradi.) Hatto eng murakkab optimallashtiruvchi kompilyator Dasturchi buni osonlikcha bajarishi mumkin bo'lsa ham, dasturning turli bo'limlarida yoki pastki tartiblarida paydo bo'lishi mumkin bo'lgan ikkita yoki undan ortiq farqli funktsiyalarni birlashtirishda juda qiyin bo'lishi mumkin edi tepada ).

Ada

Oldingi C kodi quyidagilarga aylanadi Ada til,[6] qator-dasturlash sintaksisini qo'llab-quvvatlaydi.

A := A + B;

APL

APL sintaktik shakarsiz yagona belgili Unikod belgilaridan foydalanadi.

A ← A + B

Ushbu operatsiya har qanday darajadagi (0 darajani o'z ichiga olgan) massivlarda, skalyar va massivda ishlaydi. Dyalog APL asl tilini kengaytiradi kengaytirilgan topshiriqlar:

A +← B

Analytica

Analytica Ada bilan bir xil ifoda iqtisodiyotini ta'minlaydi.

A: = A + B;

ASOSIY

Dartmut BASIC uchinchi nashrida matritsa va qatorlarni manipulyatsiya qilish uchun MAT bayonotlariga ega edi (1966).

DIMA(4),B(4),C(4)MATA=1MATB=2*AMATC=A+BMATPRINTA,B,C

Mata

Stata Matritsali dasturlash tili Mata massiv dasturlashni qo'llab-quvvatlaydi. Quyida biz matritsani va skalyarni qo'shishni, ko'paytirishni, elementni ko'paytirish, obuna qilish va Matoning ko'p teskari matritsa funktsiyalaridan birini qo'shishni tasvirlaymiz.

. mata:: A = (1,2,3) \(4,5,6): A 1   2   3    +-------------+  1 |  1   2   3  |  2 |  4   5   6  |    +-------------+: B = (2..4) \(1..3): B 1   2   3    +-------------+  1 |  2   3   4  |  2 |  1   2   3  |    +-------------+: C = J(3,2,1)           // Bittadan 3 dan 2 gacha matritsa: C 1   2    +---------+  1 |  1   1  |  2 |  1   1  |  3 |  1   1  |    +---------+: D = A + B: D. 1   2   3    +-------------+  1 |  3   5   7  |  2 |  5   7   9  |    +-------------+: E = A*C: E 1    2    +-----------+  1 |   6    6  |  2 |  15   15  |    +-----------+: F = A:*B: F 1    2    3    +----------------+  1 |   2    6   12  |  2 |   4   10   18  |    +----------------+: G = E:+ 3: G 1    2    +-----------+  1 |   9    9  |  2 |  18   18  |    +-----------+: H = F [(2\1), (1, 2)]    // F va ning submatrisasini olish uchun obuna bo'lish:                         // 1 va 2 qatorlarni almashtirish: H 1    2    +-----------+  1 |   4   10  |  2 |   2    6  |    +-----------+: I = invsym(F ')*F) // a-ning umumiy teskari (F * F ^ (- 1) F = F):                         // nosimmetrik ijobiy yarim aniq matritsa: Men [nosimmetrik] 1             2             3    +-------------------------------------------+  1 |            0                              |  2 |            0          3.25                |  3 |            0         -1.75   .9444444444  |    +-------------------------------------------+: oxiri

MATLAB

Amalga oshirish MATLAB dan foydalangan holda bir xil iqtisodga imkon beradi Fortran til.

A = A + B;

MATLAB tilining varianti bu GNU oktavi bilan asl tilni kengaytiradigan til kengaytirilgan topshiriqlar:

A += B;

Ikkala MATLAB va GNU Octave matritsalarni ko'paytirish kabi chiziqli algebra operatsiyalarini tabiiy ravishda qo'llab-quvvatlaydi, matritsa inversiyasi va ning sonli echimi chiziqli tenglamalar tizimi, hatto Mur-Penrose pseudoinverse.[7][8]

The Nial ikkita massivning ichki mahsuloti misoli mahalliy matritsalarni ko'paytirish operatori yordamida amalga oshirilishi mumkin. Agar a [1 n] va o'lchamdagi qatorli vektor b mos keladigan ustunli vektor [n 1].

a * b;

Bir xil miqdordagi elementlarga ega bo'lgan ikkita matritsa orasidagi ichki mahsulot yordamchi operator bilan amalga oshirilishi mumkin (:), bu berilgan matritsani ustun vektoriga o'zgartiradigan va ko'chirish operator ':

A (:) '* B (:);

rasql

The rasdaman so'rovlar tili ma'lumotlar bazasiga yo'naltirilgan massiv-dasturlash tili. Masalan, quyidagi so'rov bilan ikkita massiv qo'shilishi mumkin:

A + BFROM A, B ni tanlang

R

The R tilni qo'llab-quvvatlaydi massiv paradigmasi avvalboshdan. Quyidagi misolda ikkita matritsani ko'paytirish jarayoni, so'ngra skalar (aslida bitta elementli vektor) va vektor qo'shilishi tasvirlangan:

> A <- matritsa(1:6, Nrow=2)                              !!bu bor Nrow=2 ... va A bor 2 qatorlar> A     [,1] [,2] [,3][1,]    1    3    5[2,]    2    4    6> B <- t( matritsa(6:1, Nrow=2) )  # t () bu transpozitsiya operatori !! bu nrow = 2 ... va B 3 qatorga ega --- A ta'rifiga aniq zid> B     [,1] [,2][1,]    6    5[2,]    4    3[3,]    2    1> C <- A %*% B> C     [,1] [,2][1,]   28   19[2,]   40   28> D. <- C + 1> D.     [,1] [,2][1,]   29   20[2,]   41   29> D. + v(1, 1)  # c () vektor hosil qiladi     [,1] [,2][1,]   30   21[2,]   42   30

Matematik fikrlash va til yozuvlari

Matritsaning chapga bo'linish operatori matritsalarning ba'zi bir semantik xususiyatlarini qisqacha ifodalaydi. Skalyar ekvivalenti kabi, agar (aniqlovchi ning) koeffitsienti (matritsa) A null emas, keyin (vektorli) tenglamani echish mumkin A * x = b ikkala tomonni chapga ko'paytirib teskari ning A: A−1 (ikkala MATLAB va GNU oktav tillarida: A ^ -1). Quyidagi matematik bayonotlar qachon bo'ladi A a to'liq daraja kvadrat matritsa:

A ^ -1 * (A * x) == A ^ -1 * (b)
(A ^ -1 * A) * x == A ^ -1 * b (matritsani ko'paytirish assotsiativlik )
x = A ^ -1 * b

qayerda == ekvivalentlikdir munosabat operatori.Agar oldingi bayonotlar MATLAB iboralari hisoblanadi, agar uchinchisi boshqalardan oldin bajarilgan bo'lsa (raqamli taqqoslash xatolar sababli noto'g'ri bo'lishi mumkin).

Agar tizim haddan tashqari aniqlangan bo'lsa - demak A ustunlardan ko'ra ko'proq qatorlarga ega - psevdoinverse A+ (MATLAB va GNU oktav tillarida: pinv (A)) teskari o'rnini bosishi mumkin A−1, quyidagicha:

pinv (A) * (A * x) == pinv (A) * (b)
(pinv (A) * A) * x == pinv (A) * b (matritsani ko'paytirish assotsiativligi)
x = pinv (A) * b

Biroq, bu echimlar eng ixcham echimlar emas (masalan, hali belgilab qo'yilgan tizimlarni notatsional ravishda farqlash zarurati bo'lib qolmoqda) ham, hisoblash samaradorligi ham yuqori emas. Skaler ekvivalentini qayta ko'rib chiqishda oxirgi fikrni tushunish oson a * x = b, buning uchun echim x = a ^ -1 * b yanada samarali o'rniga ikkita operatsiyani talab qiladi x = b / a.Muammo shundaki, odatda matritsani ko'paytirish emas kommutativ chunki skalar echimini matritsa holatiga kengaytirish quyidagilarni talab qiladi:

(a * x) / a == b / a
(x * a) / a == b / a (komutativlik matritsalarga mos kelmaydi!)
x * (a / a) == b / a (assotsiativlik matritsalar uchun ham amal qiladi)
x = b / a

MATLAB tili chap bo'linish operatorini taqdim etadi \ o'xshashlikning muhim qismini skalar ishi bilan saqlab qolish, shuning uchun matematik fikrlashni soddalashtirish va ixchamlikni saqlash:

A (A * x) == A b
(A A) * x == A b (assotsiativlik matritsalar uchun ham amal qiladi, komutativlik endi talab qilinmaydi)
x = A b

Bu nafaqat kodlash nuqtai nazaridan tersli qator dasturlashning misoli, balki hisoblash samaradorligi nuqtai nazaridan ham bir qator qator dasturlash tillarida juda samarali chiziqli algebra kutubxonalari kabi foyda keltiradi. ATLAS yoki LAPACK.[9][10]

Iversonning avvalgi iqtibosiga qaytsak, uning asoslari endi aniq bo'lishi kerak:

biron bir yozuvni tavsiflash va o'rganish qiyinligini uning natijalarini o'zlashtirishning qiyinchiliklaridan farqlash muhimdir. Masalan, matritsali mahsulotni hisoblash qoidalarini o'rganish oson, ammo uning ta'sirini (assotsiativlik, qo'shilish ustidan taqsimlanishi va chiziqli funktsiyalar va geometrik amallarni ifodalash qobiliyati kabi) o'zlashtirish. .Haqiqatan ham, nota belgilarining juda ko'pligi, kashfiyotlar uchun taklif qiladigan ko'plab xususiyatlar tufayli o'rganishni qiyinlashtirishi mumkin.

Uchinchi tomon kutubxonalari

Ko'proq abstraktsiyalarni taqdim etish uchun ixtisoslashgan va samarali kutubxonalardan foydalanish boshqa dasturlash tillarida ham keng tarqalgan. Yilda C ++ bir nechta chiziqli algebra kutubxonalari til qobiliyatidan foydalanadi ortiqcha yuk operatorlari. Ba'zi hollarda, ushbu tillarda juda mavhum mavhumlikka, masalan, qator dasturlash paradigmasi aniq ta'sir qiladi. Armadillo va Blits ++ kutubxonalar qiladi.[11][12]

Shuningdek qarang

Adabiyotlar

  1. ^ Stefan van der Valt; S. Kris Kolbert va Gael Varoquaux (2011). "NumPy qatori: raqamli hisoblash uchun tuzilma". Fan va muhandislik sohasida hisoblash. IEEE. 13 (2): 22–30. arXiv:1102.1523. Bibcode:2011CSE .... 13b..22V. doi:10.1109 / mcse.2011.37.
  2. ^ Iverson, K. E. (1980). "Notations fikr vositasi sifatida". ACM aloqalari. 23 (8): 444–465. doi:10.1145/358896.358899. Arxivlandi asl nusxasi 2013-09-20. Olingan 2011-03-22.
  3. ^ Surana P (2006). "Til abstraktsiyalarining meta-kompilyatsiyasi" (PDF). Arxivlandi asl nusxasi (PDF) 2015-02-17. Olingan 2008-03-17. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
  4. ^ Kuketayev. "Java-dagi kichik ob'ektlar uchun ma'lumot olish uchun penalti (DAP) ko'rsatkichi". Arxivlandi asl nusxasi 2009-01-11. Olingan 2008-03-17.
  5. ^ Chatzigeorgiou; Stefanidlar (2002). "Ob'ektga yo'naltirilgan va protsessual dasturlash tillarining samaradorligi va kuchini baholash". Bliebergerda; Strohmayer (tahrir). Ishlar - ishonchli dasturiy ta'minot texnologiyalari bo'yicha 7-xalqaro konferentsiya - Ada-Europe'2002. Springer. p. 367. ISBN  978-3-540-43784-0.
  6. ^ Ada ma'lumotnomasi: G.3.1 Haqiqiy vektorlar va matritsalar
  7. ^ "GNU oktav qo'llanmasi. Arifmetik operatorlar". Olingan 2011-03-19.
  8. ^ "MATLAB hujjatlari. Arifmetik operatorlar". Olingan 2011-03-19.
  9. ^ "GNU oktav qo'llanmasi. G ilova oktavni o'rnatish". Olingan 2011-03-19.
  10. ^ "Mathematica 5.2 Hujjatlar. Dasturlarga havolalar".. Olingan 2011-03-19.
  11. ^ "Armadillo 1.1.8 uchun ma'lumotnoma. Matlab / Octave sintaksisiga misollar va Armadillo sintaksisiga mos keladigan".. Olingan 2011-03-19.
  12. ^ "Blits ++ foydalanuvchi qo'llanmasi. 3. Array ifodalar". Arxivlandi asl nusxasi 2011-03-23. Olingan 2011-03-19.

Tashqi havolalar