Dizi programlama

Bilgisayar biliminde dizi programlama, işlemlerin bir kerede tüm değerler kümesine uygulanmasına izin veren çözümleri ifade eder. Bu tür çözümler, bilimsel ve mühendislik ortamlarında yaygın olarak kullanılmaktadır.

Dizi programlamayı destekleyen modern programlama dilleri (vektör veya çok boyutlu diller olarak da bilinir), vektörlere, matrislere ve daha yüksek boyutlu dizilere şeffaf bir şekilde uygulamak için skaler üzerindeki işlemleri genelleştirmek için özel olarak tasarlanmıştır. Bunlar arasında APL, J, Fortran 90, MATLAB, Analytica, TK Çözücü (listeler olarak), Octave, R, Cilk Plus, Julia, Perl Data Language (PDL) ve Python'a NumPy uzantısı dahildir. Bu dillerde, tüm diziler üzerinde çalışan bir işlem, vektör komutlarını uygulayan bir vektör işlemcisinde yürütülüp yürütülmediğine bakılmaksızın vektörleştirilmiş bir işlem olarak adlandırılabilir. Dizi programlama ilkelleri, veri işleme hakkında geniş fikirleri kısaca ifade eder. Kesinlik düzeyi bazı durumlarda dramatik olabilir, örneğin: dizi programlama dilindeki tek satırlık ifadelerin birkaç sayfalık nesne yönelimli koda karşılık gelmesi sıkça kaşılaşılan bir durumdur.

Dizi kavramları

Dizi programlamanın arkasındaki temel fikir, işlemlerin bir kerede tüm değerler kümesine uygulanmasıdır. Bu, programcının bireysel skaler işlemlerin açık döngülerine başvurmak zorunda kalmadan tüm veri kümeleri üzerinde düşünmesine ve çalışmasına izin verdiği için onu üst düzey bir programlama modeli yapar.

Kenneth E. Iverson, dizi programlamanın (aslında APL'ye atıfta bulunarak) arkasındaki mantığı şu şekilde açıkladı:

Çoğu programlama dili, matematiksel gösterimden kesinlikle daha düşüktür ve bir uygulamalı matematikçi tarafından önemli sayılacak şekilde düşünce aracı olarak çok az kullanılır.

Tez, programlama dillerinde bulunan uygulanabilirliğin ve evrenselliğin avantajlarının, matematiksel gösterimin sunduğu avantajlarla tek bir tutarlı dilde etkili bir şekilde birleştirilebileceğidir. Bir gösterim parçasını tanımlamanın ve öğrenmenin zorluğunu, etkilerine hakim olmanın zorluğundan ayırt etmek önemlidir. Örneğin, bir matris çarpımını hesaplama kurallarını öğrenmek kolaydır, ancak etkilerinin ustalığı (ilişkiselliği, toplama üzerindeki dağılımı ve doğrusal fonksiyonlar ve geometrik işlemleri temsil etme yeteneği gibi) farklı ve çok daha zor bir konudur.

Gerçekten de, bir gösterimin önerilebilirliği, keşifler için önerdiği birçok özellik nedeniyle öğrenmeyi zorlaştırabilir.

[...]

Bilgisayar ve programlama dillerinin kullanıcıları genellikle, öncelikli olarak algoritmaların yürütülmesinin verimliliği ile ilgilenir ve bu nedenle burada sunulan algoritmaların çoğunu özetle reddedebilir. Böyle bir reddetme dar görüşlü olacaktır, çünkü bir algoritmanın açık bir ifadesi genellikle daha verimli bir algoritmanın kolayca türetilebileceği bir temel olarak kullanılabilir.

Dizi programlamanın ve düşünmenin arkasındaki temel, tek tek öğelerin benzer veya bitişik olduğu verilerin özelliklerini bulmak ve kullanmaktır. Verileri dolaylı olarak bileşenlerine (veya skaler miktarlara) ayıran nesne yöneliminden farklı olarak, dizi yönelimi, verileri gruplandırmaya ve tek tip bir işleme uygulamaya bakar.

Fonksiyon derecesi, genel olarak dizi programlama dilleri için matematikteki tensör sıralamasına benzer şekilde önemli bir kavramdır: veriler üzerinde çalışan fonksiyonlar, üzerinde hareket ettikleri boyutların sayısına göre derecelendirilir. Örneğin sıradan çarpma, sıfır boyutlu veriler (tek tek sayılar) üzerinde çalıştığı için skaler sıralı bir işlevdir. Çapraz çarpım işlemi, skaler değil vektörler üzerinde çalıştığı için vektör dereceli fonksiyona bir örnektir. Matris çarpımı, 2 boyutlu nesneler (matrisler) üzerinde çalıştığı için ikinci dereceden bir işlev örneğidir. Daraltma işleçleri, bir girdi veri dizisinin boyutsallığını bir veya daha fazla boyut azaltır. Örneğin, öğelerin toplanması, giriş dizisini 1 boyut daraltır.

Kullanımlar

Dizi programlama, örtük paralelleştirme için çok uygundur; günümüzde popüler bir araştırma konusu. Ayrıca, 1997'den sonra geliştirilen ve üretilen Intel ve uyumlu işlemciler, mmx'ten başlayıp SSSE3 ve 3DNow! ile devam eden çeşitli komut seti uzantıları içeriyordu. temel SIMD dizi yeteneklerini içerir. Dizi işleme, paralel işlemeden farklıdır, çünkü bir fiziksel işlemci aynı anda bir grup öğe üzerinde işlem gerçekleştirirken, paralel işlem, daha büyük bir sorunu çok sayıda işlemci tarafından parça parça çözülecek daha küçük işlemlere (MIMD) bölmeyi amaçlar. Günümüzde iki veya daha fazla çekirdeğe sahip işlemciler yaygınlaşmıştır.

Diller

Dizi programlama dillerinin kurallı örnekleri Fortran, APL ve J'dir. Diğerleri şunlardır: A+, Analytica, Chapel, IDL, Julia, K, Klong, Q, MATLAB, NumPy, GNU Octave, PDL, R, S-Lang, SAC, Nial, ZPL ve TI-BASIC.

Skaler diller

C ve Pascal gibi skaler dillerde, işlemler yalnızca tek değer için geçerlidir, bu nedenle a + b iki sayının toplanmasını ifade eder. Bu tür dillerde, bir diziyi diğerine eklemek, kodlaması sıkıcı olan indeksleme ve döngüleme gerektirir.

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

Dizi tabanlı dillerde, örneğin Fortran'da, yukarıdaki iç içe geçmiş for döngüsü dizi biçiminde tek bir satırda yazılabilir,

a = a + b

veya alternatif olarak, nesnelerin dizi yapısını vurgulamak için,

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

C gibi skaler diller, dilin bir parçası olarak yerel dizi programlama öğelerine sahip olmasa da, bu, bu dillerde yazılmış programların temel vektörizasyon tekniklerinden asla yararlanmadığı anlamına gelmez (örneğin, bir CPU eğer vektör tabanlı talimatlarına sahipse onları kullanarak veya birden fazla işlemci çekirdeği kullanarak). Bazı optimizasyon seviyelerinde GCC gibi bazı C derleyicileri, buluşsal özelliklerinin bundan faydalanacağını belirlediği kod bölümlerini algılar ve vektörize eder. Başka bir yaklaşım, birden çok CPU çekirdeğinden yararlanarak kodun uygulanabilir bölümlerini paralelleştirmeye izin veren OpenMP UPA'sı tarafından verilir.

Dizi dilleri

Dizi dillerinde, işlemler hem skalerlere hem de dizilere uygulanacak şekilde genelleştirilmiştir. Bu nedenle, a + b, a ve b skaler ise iki skalerin toplamını veya diziler ise iki dizinin toplamını ifade eder.

Bir dizi dili programlamayı basitleştirir, ancak muhtemelen soyutlama handikapı olarak bilinen bir maliyetle. Eklemeler kodlamanın geri kalanından ayrı olarak gerçekleştirildiğinden, en uygun şekilde en verimli kodu üretemeyebilirler. (Örneğin, aynı dizinin diğer öğelerinin eklenmesi daha sonra aynı yürütme sırasında karşılaşılabilir ve gereksiz tekrarlanan aramalara neden olabilir) En gelişmiş optimizasyon derleyicisi bile, bir programcının bunu kolayca yapabilmesine rağmen, yükü en aza indirmek için dizi üzerinden aynı geçişte toplamları ele almasına rağmen, farklı program bölümlerinde veya alt yordamlarda görünebilecek iki veya daha fazla görünüşte farklı işlevi birleştirmekte son derece zorlanacaktır.

Ada

Ada dilinde, dizi programlama sözdizimini destekleyen önceki C kodu aşağıdaki gibi olacaktır.

A := A + B;

APL

APL, sözdizimsel şekerlemesiz, tek karakterli Unicode sembolleri kullanır.

A ← A + B

Bu işlem, herhangi bir derecedeki dizilerde (0 derece dahil) ve bir skaler üzerinde çalışır. Dyalog APL, orijinal dili artırılmış atamalarla genişletir:

A +← BA +← B

Analytica

Analytica, Ada ile aynı ifade yapısını sağlar.

A := A + B;

BASIC

Dartmouth BASİC, üçüncü baskısında (1966) matris ve dizi manipülasyonu için MAT ifadelerine sahipti.

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

Mata

Stata'nın matris programlama dili Mata, dizi programlamayı destekler. Aşağıda toplama, çarpma, matris ve skaler ekleme, eleman eleman çarpma, abonelik ve Mata'nın birçok ters matris fonksiyonundan birini gösteriyoruz.

. 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'e 2 matris

: 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'den bir alt matris almak için

:                         // satır 1 ve 2'yi değiştir
: H
        1    2
    +-----------+
  1 |   4   10  |
  2 |   2    6  |
    +-----------+

: I = invsym(F'*F)        // A'nın genelleştirilmiş tersi (F * F ^ (-1) F = F)

:                         // simetrik pozitif yarı-kesin matris
: I
[symmetric]
                 1             2             3
    +-------------------------------------------+
  1 |            0                              |
  2 |            0          3.25                |
  3 |            0         -1.75   .9444444444  |
    +-------------------------------------------+

: end

MATLAB

Matlab'daki uygulama, Fortran dilindeki aynı yapının kullanımına izin verir.

A = A + B;

MATLAB dilinin bir çeşidi, orijinal dili artırılmış atamalarla genişleten GNU Octave dilidir:

A += B;

Hem MATLAB hem de GNU Octave, Moore–Penrose sözdetersi kullanarak bile, matris çarpımı, matris inversiyonu ve doğrusal denklem sisteminin sayısal çözümü gibi doğrusal cebir işlemlerini doğal olarak desteklemektedir.

İki dizinin iç çarpımının Nial örneği, yerel matris çarpma işleci kullanılarak uygulanabilir. a, [1 n] boyutunda bir satır vektörüyse ve b, [n 1] boyutunda karşılık gelen bir sütun vektörüyse.

a * b;

Aynı sayıda elemana sahip iki matris arasındaki iç çarpım, belirli bir matrisi bir sütun vektörüne yeniden şekillendiren yardımcı işleç (:) ve tersçapraz işleci ' ile uygulanabilir:

A(:)' * B(:);

rasql

Rasdaman sorgu dili, veritabanı yönelimli bir dizi programlama dilidir. Örneğin, iki dizi aşağıdaki sorgu ile eklenebilir:

SELECT A + B
FROM   A, B

R

R dili varsayılan olarak dizi paradigmasını destekler. Aşağıdaki örnek, iki matrisin çarpma işlemini ve ardından bir skaler (aslında tek elemanlı bir vektördür) ve bir vektörün eklenmesini göstermektedir:

> A <- matrix(1:6, nrow=2)                              # !! Burada, satır sayısı (nrow=)2'dir ve A'nın iki satırı vardır.
> A
     [,1] [,2] [,3]
[1,]    1    3    5
[2,]    2    4    6
> B <- t( matrix(6:1, nrow=2) )  # t() tersçarpraz işlecidir. !! Burada, satır sayısı (nrow=)2'dir ve B'nin 3 satırı var --- A tanımına açık bir çelişkidir.
> 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() bir vektör oluşturur
     [,1] [,2]
[1,]   30   21
[2,]   42   30

Matematiksel muhakeme ve dil gösterimi

Matris sol-bölmeli operatörü, matrislerin bazı anlamsal özelliklerini özlü bir şekilde ifade eder. Skaler eşdeğerde olduğu gibi, A katsayısının (matrisinin) belirleyicisi boş değilse, A * x = b (vektörel) denklemini, her iki tarafı da A:A-1'in tersi ile çarparak çözmek mümkündür (hem MATLAB hem de GNU Octave dillerinde: A^-1). Aşağıdaki matematiksel ifadeler, A tam sıralı bir kare matris olduğunda geçerlidir:

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

(A^-1 * A)* x ==A^-1 * b       (matris-çarpım ilişkiselliği)

x = A^-1 * b

burada == denklik ilişkisel işlecidir. Üçüncüsü diğerlerinden önce yürütülürse önceki ifadeler de geçerli MATLAB ifadeleridir (yuvarlama hataları nedeniyle sayısal karşılaştırmalar yanlış olabilir).

Sistem aşırı tanımlanmışsa – A'nın sütunlardan daha fazla satıra sahipse − sözdeters A+ (MATLAB ve GNU Octave dillerinde: pinv(A)), ters A-1'in yerini aşağıdaki gibi alabilir:

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

(pinv(A) * A)* x ==pinv(A) * b       (matris-çarpım ilişkiselliği)

x = pinv(A) * b

Bununla birlikte, bu çözümler ne en özlü çözümlerdir (örneğin, aşırı tanımlanmış sistemleri notasyonel olarak ayırt etme ihtiyacı hala devam etmektedir) ne de hesaplama açısından en verimli çözümlerdir. x = a^-1 * b çözümünün x = b / a yerine iki işlem gerektireceği a * x = b skaler eşdeğeri yeniden göz önüne alındığında anlamak kolaydır. Sorun, skaler çözümün matris durumuna genişletilmesinin gerektireceğinden, genellikle matris çarpımlarının değişmeli olmamasıdır:

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

(x * a)/ a ==b / a       (değişebilirlik, matrisler için geçerli değildir!)

x * (a / a)==b / a       (ilişkisellik, matrisler için de geçerlidir)

x = b / a

MATLAB dili, skalar durumla analojinin temel kısmını korumak için sol-bölme operatörünü \ tanıtır, bu nedenle matematiksel muhakemeyi basitleştirir ve özlülüğü korur:

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

(A \ A)* x ==A \ b       (ilişkisellik matrisler için de geçerlidir, değişebilirlik artık gerekli değildir)

x = A \ b

Bu sadece kodlama açısından değil, aynı zamanda çeşitli dizi programlama dillerinde ATLAS veya LAPACK gibi oldukça verimli doğrusal cebir kütüphanelerinden yararlanan hesaplama verimliliği açısından da dizi programlamanın bir örneğidir.

Iverson'un önceki ifadesine dönersek, arkasındaki mantık şimdi açık olmalıdır:

“ Bir gösterim parçasını tanımlamanın ve öğrenmenin zorluğunu, etkilerine hakim olmanın zorluğundan ayırt etmek önemlidir. Örneğin, bir matris çarpımını hesaplama kurallarını öğrenmek kolaydır, ancak etkilerinin ustalığı (ilişkiselliği, toplama üzerindeki dağılımı ve doğrusal işlevleri ve geometrik işlemleri temsil etme yeteneği gibi) farklı ve çok daha zor bir konudur.

Gerçekten de, bir gösterimin önerilebilirliği, keşifler için önerdiği birçok özellik nedeniyle öğrenmeyi zorlaştırabilir.

”

Üçüncü taraf kütüphaneleri

Daha özlü soyutlamalar sağlamak için özel ve verimli kitaplıkların kullanımı, diğer programlama dillerinde de yaygındır. C++'da birkaç lineer cebir kitaplığı, dilin, operatörleri aşırı yükleme yeteneğinden yararlanır. Bazı durumlarda, Armadillo ve Blitz++ kitaplıklarının yaptığı gibi, bu dillerdeki yüzeysel soyutlama, dizi programlama paradigmasından açıkça etkilenir.

Ayrıca bakınız

• Dizi dilimleme
• Dizi programlama dillerinin listesi

Dış bağlantılar

• "Kokmuş döngü yok" programlama 13 Nisan 2020 tarihinde Wayback Machine sitesinde arşivlendi.
• Dizi Dillerini Keşfetmek