Array programming

در علوم کامپیوتر ، برنامه نویسی آرایه به راه حلهایی اطلاق می شود که اجازه می دهد اعمال را برای یک مجموعه کامل از مقادیر همزمان انجام دهید. اینگونه راه حلها معمولاً در محیطهای علمی و مهندسی مورد استفاده قرار می گیرند.

زبانهای برنامه نویسی مدرنی که از برنامه نویسی آرایه پشتیبانی می کنند (همچنین به زبانهای برداری یا چند بعدی نیز معروف هستند) به طور خاص مهندسی شده اند تا عملیات روی مقیاس ها را تعمیم دهند تا به طور شفاف بردارها ، ماتریس ها و آرایه های بعدی بالاتر اعمال شوند. این موارد شامل (به صورت لیست ها) APL ، J ، Fortran 90 ، Mata ، MATLAB ، Analytica ، TK Solver ای پی ال، Octave ، R ، Cilk Plus ، Julia ، Perl Data Language (PDL) و پسوند NumPy به پایتون است. در این زبان ها ، عملیاتی که روی کل آرایه ها عمل می کند را می توان یک عمل بردار نامید ، بدون توجه به اینکه روی پردازنده برداری اجرا می شود که دستورالعمل های برداری را اجرا می کند. برنامه نویسی آرایه به طور خلاصه ایده های گسترده ای را درباره دستکاری داده بیان می کند. سطح جمع بندی در موارد خاص می تواند چشمگیر باشد: یافتن زبان برنامه نویسی آرایه یک خطی که به چندین صفحه کد شی گرا نیاز دارد ، غیرمعمول نیست.

مفهوم آرایه ها

The fundamental idea behind array programming is that operations apply at once to an entire set of values. This makes it a high-level programming model as it allows the programmer to think and operate on whole aggregates of data, without having to resort to explicit loops of individual scalar operations.

Kenneth E. Iverson described the rationale behind array programming (actually referring to APL) as follows:

ایده اساسی در پشت برنامه نویسی آرایه این است که عملیات به یک باره برای کل مجموعه مقادیر اعمال می شود. این امر آن را به یک مدل برنامه نویسی سطح بالا تبدیل می کند زیرا به برنامه نویس اجازه می دهد تا روی کل جمع آوری داده ها فکر کند و کار کند ، بدون اینکه به حلقه های صریح عملیات اسکالر جداگانه متوسل شود.Kenneth E. Iverson دلیل اصلی برنامه نویسی آرایه (در واقع اشاره به APL) را به شرح زیر شرح داد:

اکثر زبانهای برنامه نویسی نسبت به نت ریاضی فراتر هستند و از آنها به عنوان ابزاری برای اندیشه استفاده نمی کنند ، مثلاً یک ریاضیدان کاربردی آنها را قابل توجه می داند.

تز این است که مزایای قابلیت اجرا و جهانی بودن در زبان های برنامه نویسی را می توان به طور موثر ، در یک زبان منسجم واحد با مزایای ارائه شده توسط نت ریاضی ترکیب کرد. مهم است که دشواری توصیف و یادگیری قطعه ای از نت را از دشواری تسلط بر پیامدهای آن تشخیص دهیم. به عنوان مثال ، یادگیری قوانین محاسبه یک محصول ماتریس آسان است ، اما تسلط بر پیامدهای آن (مانند ارتباط آن ، توزیع آن بر روی جمع ، و توانایی آن در نمایش توابع خطی و عملیات هندسی) یک مسئله متفاوت و بسیار دشوارتر است .

در واقع ، خود پیشنهادی بودن یک نت به دلیل خواص زیادی که برای اکتشافات به شما پیشنهاد می دهد ، یادگیری آن را دشوارتر نشان می دهد.

[...]

کاربران رایانه ها و زبان های برنامه نویسی غالباً در درجه اول به کارآیی اجرای الگوریتم ها توجه دارند و بنابراین ، ممکن است به طور خلاصه بسیاری از الگوریتم های ارائه شده در اینجا را کنار بگذارند. چنین اخراجی کوته بینانه خواهد بود زیرا معمولاً می توان از بیان صحیح الگوریتم به عنوان مبنایی استفاده کرد که می توان به راحتی الگوریتمی کارآمدتر از آن استخراج کرد.

اساس برنامه نویسی و تفکر آرایه یافتن و بهره برداری از خصوصیات داده ها در جایی است که عناصر منفرد مشابه یا مجاور هستند. برخلاف جهت گیری شی object که به طور ضمنی داده ها را به قسمت های تشکیل دهنده آن تقسیم می کند (یا مقیاس های مقیاس دار) ، جهت گیری آرایه به دنبال گروه بندی داده ها و اعمال یک دست زدن به یکنواخت است.

رتبه تابع یک مفهوم مهم برای زبانهای برنامه نویسی آرایه به طور کلی ، به قیاس با رتبه تانسور در ریاضیات است: توابع که بر روی داده کار می کنند ، ممکن است براساس تعداد ابعادی که عمل می کنند ، طبقه بندی شوند. به عنوان مثال ضرب معمولی یک تابع دارای رتبه بندی مقیاسی است زیرا با داده های بعد صفر (اعداد منفرد) کار می کند. عملکرد ضرب خارجی نمونه ای از یک تابع مرتبه برداری است زیرا از طریق بردارها عمل می کند نه مقیاس پذیرها. ضرب ماتریس مثالی از یک تابع 2 درجه ای است ، زیرا روی اجسام 2 بعدی (ماتریس) عمل می کند. عملگرهای جمع آوری ابعاد آرایه داده ورودی را با یک یا چند بعد کاهش می دهند. به عنوان مثال ، جمع کردن عناصر ، آرایه ورودی را با 1 بعد جمع می کند.

موارد استفاده

برنامه نویسی آرایه برای موازی سازی ضمنی بسیار مناسب است. امروزه موضوع بسیاری از تحقیقات است بعلاوه ، اینتل و پردازنده های سازگار پس از 1997 تولید و تولید شدند که حاوی پسوندهای مختلف مجموعه دستورالعمل ها بودند ، از MMX شروع می شوند و از طریق SSSE3 و 3DNow ادامه می یابند! که شامل قابلیت های اولیه آرایه SIMD هستند. پردازش آرایه از پردازش موازی متمایز است به این دلیل که یک پردازنده فیزیکی به طور همزمان بر روی گروهی از موارد کار می کند در حالی که پردازش موازی با هدف تقسیم یک مسئله بزرگتر به مشکلات کوچکتر (MIMD) انجام می شود تا توسط پردازنده های متعدد به صورت قطعه ای حل شود. پردازنده های دارای دو یا چند هسته امروزه به طور فزاینده ای رایج شده اند.

زبان ها

مثالهای متعارف زبانهای برنامه نویسی آرایه عبارتند از: Fortran ، APL و J. سایر موارد شامل: A +، Analytica، Chapel، IDL، Julia، K، Klong، Q، Mata، MATLAB، MOLSF، NumPy، PDL، R، S -Lang ، SAC ، Nial ، ZPL ، TI-BASIC, GNU Octave

زبان های نرده ای (اسکالر)

در زبانهای اسکالر مانند C و Pascal ، اعمال فقط برای مقادیر منفرد اعمال می شوند ، بنابراین a + b بیانگر جمع دو عدد است. در چنین زبان هایی ، افزودن یک آرایه به دیگری به نمایه سازی و حلقه نیاز دارد ، کدگذاری آن خسته کننده است.

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
        a[i][j] += b[i][j];

در زبانهای مبتنی بر آرایه ، به عنوان مثال در Fortran ، حلقه تو در تو در بالا می تواند به صورت آرایه در یک خط نوشته شود.

a = a + b

یا به جای آن ، برای تأکید بر ماهیت آرایه اشیا

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

در حالی که زبانهای اسکالر مانند C از عناصر برنامه نویسی آرایه بومی بعنوان بخشی از زبان مناسب برخوردار نیستند ، اما این بدان معنا نیست که برنامه های نوشته شده در این زبانها هرگز از تکنیک های اساسی بردارسازی (به عنوان مثال استفاده از دستورالعمل های مبتنی بر بردار CPU در صورت استفاده از آن) استفاده نمی کنند. یا با استفاده از چندین هسته پردازنده). برخی از کامپایلرهای C مانند GCC در برخی از سطوح بهینه سازی ، بخشهایی از کد را که از نظر ابتکار عمل تعیین می کند ، شناسایی و بردار می کنند. روش دیگری توسط OpenMP API ارائه شده است ، که به شما امکان می دهد با استفاده از چندین هسته پردازنده ، بخشهای قابل اجرا از کد را موازی سازی کند.

زبان های آرایه ای

در زبان های آرایه ، عملکردها تعمیم داده می شوند که هم در مقیاس کش ها و هم در آرایه ها اعمال شوند. بنابراین ، a + b مجموع دو مقیاس دهنده را نشان می دهد اگر a و b مقیاس پذیر باشند ، یا مجموع دو آرایه اگر آرایه ای باشند.

زبان آرایه برنامه نویسی را ساده می کند اما احتمالاً با هزینه ای است که به عنوان جریمه انتزاع شناخته می شود. از آنجا که اضافات جدا از بقیه برنامه نویسی انجام می شود ، ممکن است کارآمدترین کد را تولید نکند. (بعنوان مثال ، اضافه شدن عناصر دیگر از همان آرایه ممکن است متعاقباً در طی همان اجرا مشاهده شود ، که باعث جستجوهای مکرر غیرضروری می شود.) بخشهای مختلف برنامه یا روال فرعی ، حتی اگر یک برنامه نویس بتواند این کار را به راحتی انجام دهد ، مبالغی را در همان عبور از آرایه جمع می کند تا هزینه سربار را به حداقل برساند.

Ada (آدا)

کد C قبلی در زبان Ada به صورت زیر در می آید که از نحو برنامه نویسی آرایه پشتیبانی می کند.

A := A + B;

APL (ای پی ال)

APL از نمادهای Unicode تک کاراکتر و بدون قند نحوی استفاده می کند.

A ← A + B

This operation works on arrays of any rank (including rank 0), and on a scalar and an array. Dyalog APL extends the original language with augmented assignments:

این عملیات روی آرایه های با هر درجه (از جمله رتبه 0) و روی مقیاس و آرایه کار می کند. Dyalog APL زبان اصلی را با مقدار دهی افزوده گسترش می دهد:

A +← B

Analytica(آنالیتیکا)

Analytica همان اقتصاد بیان Ada را فراهم می کند.

A := A + B;

BASIC(بیسیک)

دارتموث BASIC در ویرایش سوم (1966) عبارات MAT برای دستکاری ماتریس و آرایه داشت.

DIM A(4),B(4),C(4)
MAT A = 1
MAT B = 2 * A
MAT C = A + B
MAT PRINT A,B,C

Mata(ماتا)

زبان برنامه نویسی ماتریس استاتا Mata از برنامه نویسی آرایه پشتیبانی می کند. در زیر ، جمع ، ضرب ، جمع ماتریس و مقیاس ، ضرب عنصر به عنصر ، اشتراک و یکی از بسیاری از توابع ماتریس معکوس ماتا را نشان می دهیم.

. 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)           // یک ماتریس 3 در 2 از 1 ها

: 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 و

:                         // تعویض سطر یک و دو
: H
        1    2
    +-----------+
  1 |   4   10  |
  2 |   2    6  |
    +-----------+

: I = invsym(F'*F)        // معکوس تعمیم یافته (F * F ^ (- 1) F = F) از a

:                         // متقارن ماتریس مثبت نیمه قطعی
: I
[symmetric]
                 1             2             3
    +-------------------------------------------+
  1 |            0                              |
  2 |            0          3.25                |
  3 |            0         -1.75   .9444444444  |
    +-------------------------------------------+

: end

MATLAB(متلب)

پیاده سازی در MATLAB همان اقتصاد مجاز را با استفاده از زبان Fortran فراهم می کند.

A = A + B;

نوع زبان MATLAB زبان GNU Octave است که زبان اصلی را با تکالیف افزوده گسترش می دهد:

A += B;

هر دو MATLAB و GNU Octave بومی عمل جبر خطی مانند ضرب ماتریس ، وارونگی ماتریس و حل عددی سیستم معادلات خطی را پشتیبانی می کنند ، حتی با استفاده از شبه مقبره مور-پنروز.

نمونه Nial از محصول داخلی دو آرایه را می توان با استفاده از عملگر ضرب ماتریس بومی پیاده سازی کرد. اگر a بردار ردیفی به اندازه [1 n] و b باشد یک بردار ستونی مربوط به اندازه [n 1] است.

a * b;

محصول داخلی بین دو ماتریس که تعداد عناصر یکسانی دارند را می توان با عملگر کمکی (:) ، که یک ماتریس داده شده را به بردار ستون تغییر شکل می دهد ، و عملگر انتقال را پیاده سازی کرد ' :

A(:)' * B(:);

rasql

زبان پرس و جو rasdaman یک زبان برنامه نویسی آرایه ای پایگاه داده است. به عنوان مثال ، می توان دو آرایه را با درخواست زیر اضافه کرد:

SELECT A + B
FROM   A, B

R

زبان R به طور پیش فرض از الگوی آرایه پشتیبانی می کند. مثال زیر فرایند ضرب دو ماتریس و به دنبال آن اضافه کردن یک اسکالر (که در واقع یک بردار یک عنصر است) و یک بردار را نشان می دهد:

> A <- matrix(1:6, nrow=2)                              !!این دارای nrow = 2 ... و A دارای 2 ردیف است
> A
     [,1] [,2] [,3]
[1,]    1    3    5
[2,]    2    4    6
> B <- t( matrix(6:1, nrow=2) )  # t() عملگر انتقال است                       !!thisدارای nrow = 2 ... و B دارای 3 ردیف است - این یک تناقض آشکار با تعریف A است
> 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 + c(1, 1)  # c() یک بردار میسازد
     [,1] [,2]
[1,]   30   21
[2,]   42   30

استدلال ریاضی و علامت گذاری زبان

The matrix left-division operator concisely expresses some semantic properties of matrices. As in the scalar equivalent, if the (determinant of the) coefficient (matrix) A is not null then it is possible to solve the (vectorial) equation A * x = b by left-multiplying both sides by the inverse of A: A−1 (in both MATLAB and GNU Octave languages: A^-1). The following mathematical statements hold when A is a full rank square matrix:

عملگر تقسیم چپ ماتریس به طور خلاصه برخی از خصوصیات معنایی ماتریس ها را بیان می کند. همانند معادل اسکالر ، اگر ضریب (تعیین کننده) ضریب (ماتریس) A صفر نباشد ، می توان معادله (بردار) A * x = b را با ضرب چپ هر دو طرف برعکس A حل کرد: A −1 (به دو زبان MATLAB و GNU Octave: A ^ -1). عبارات ریاضی زیر هنگامی که A یک ماتریس مربع درجه کامل است ، نگهداری می شوند:

A^-1 *(A * x)==A^-1 * (b)

(A^-1 * A)* x ==A^-1 * b       (تداعی ماتریس ضرب)

x = A^-1 * b

جایی که == عملگر رابطه ای معادل است. عبارات قبلی همچنین عبارات معتبر MATLAB هستند اگر عبارت سوم قبل از سایر موارد اجرا شود (مقایسه عددی ممکن است نادرست باشد به دلیل خطاهای دور زدن).

اگر سیستم بیش از حد تعیین شده باشد - به طوری که ردیف های A بیشتر از ستون ها باشد - شبه معکوس A + (به زبان MATLAB و GNU Octave: pinv (A)) می تواند معکوس A − 1 را جایگزین کند ، به شرح زیر:

pinv(A) *(A * x)==pinv(A) * (b)

(pinv(A) * A)* x ==pinv(A) * b       (تداعی ماتریس ضرب)

x = pinv(A) * b

با این حال ، این راه حل ها نه مختصر ترین راه حل ها هستند (به عنوان مثال هنوز نیاز به تمایز نمایی سیستم های بیش از حد تعیین شده وجود دارد) و نه کارآمدترین محاسبات. درک آخرین نکته در هنگام بررسی مجدد معادل اسکالر a * x = b آسان است ، که برای آن x = a ^ -1 * b راه حل به جای کارآمدتر x = b / a به دو عمل نیاز دارد. مسئله این است که به طور کلی ضربات ماتریس عوض نمی شوند زیرا گسترش محلول مقیاسی به حالت ماتریس نیاز دارد:

(a * x)/ a ==b / a

(x * a)/ a ==b / a       (اشتراکی برای ماتریس برقرار نیست!)

x * (a / a)==b / a       (تداعی گرایی برای ماتریس ها نیز وجود دارد)

x = b / a

زبان MATLAB عملگر تقسیم چپ را معرفی می کند تا قسمت اصلی تشبیه را با مورد مقیاس حفظ کند ، بنابراین استدلال ریاضی را ساده می کند و خلاصه را حفظ می کند:

A \ (A * x)==A \ b

(A \ A)* x ==A \ b       (انجمنی برای ماتریس ها نیز وجود دارد ، دیگر نیازی به اشتراکی نیست)

x = A \ b

این نه تنها نمونه ای از برنامه نویسی آرایه مختصر از نظر کدگذاری بلکه از منظر کارایی محاسباتی نیز می باشد ، که در چندین زبان برنامه نویسی آرایه از کتابخانه های جبر خطی کاملاً کارآمد مانند ATLAS یا LAPACK سود می برد

با بازگشت به نقل قبلی از ایورسون ، منطق موجود در آن اکنون باید مشهود باشد:

مهم است که دشواری توصیف و یادگیری قطعه ای از نت را از دشواری تسلط بر پیامدهای آن تشخیص دهیم. به عنوان مثال ، یادگیری قوانین محاسبه یک محصول ماتریس آسان است ، اما تسلط بر پیامدهای آن (مانند ارتباط آن ، توزیع آن بر روی جمع ، و توانایی آن در نمایش توابع خطی و عملیات هندسی) یک مسئله متفاوت و بسیار دشوارتر است . در واقع ، خود پیشنهادی بودن یک نت به دلیل خواص زیادی که برای اکتشافات به شما پیشنهاد می دهد ، یادگیری آن را دشوارتر نشان می دهد.

کتابخانه های شخص ثالث

The use of specialized and efficient libraries to provide more terse abstractions is also common in other programming languages. In C++ several linear algebra libraries exploit the language's ability to overload operators. In some cases a very terse abstraction in those languages is explicitly influenced by the array programming paradigm, as the Armadillo and Blitz++ libraries do.

استفاده از کتابخانه های تخصصی و کارآمد برای ارائه تجریدات مختصر در زبانهای برنامه نویسی نیز معمول است. در C ++ چندین کتابخانه جبر خطی از توانایی زبان در اضافه بار اپراتورها سو استفاده می کنند. در بعضی موارد ، انتزاع بسیار مختصر در آن زبانها به صراحت تحت تأثیر الگوی برنامه نویسی آرایه قرار می گیرد ، همانطور که کتابخانه های Armadillo و ++Blitz این کار را می کنند..

همچنین ببینید

• برش آرایه ها
• لیست زبان های آرایه ای

External links

• "No stinking loops" programming
• Discovering Array Languages