Sunday, April 26, 2015

Java'da Diziler


Java'da değişkenleri çeşitli biçimlerde sınıflandırabiliriz:
  • Yerel değişken Bir metod bloğunda ya da metodun parametre listesinde tanımlanan değişkenler, yerel değişken olarak adlandırılırlar. Yığında saklanırlar. Bu nedenle bazen yığın değişkeni olarak da adlandırılır. Otomatik olarak yaratılır ve yine erimi dışına çıkınca otomatik olarak yok edilirler. Bu nedenle de bazen otomatik değişken olarak da isimlendirildiği de olur. Okumadan önce mutlaka ilklendirmek gerekir. Derleyici bu durumun takipçisidir!
  • Durum değişkeni Sınıf için tanımladığımız öznitelikler durum değişkeni olarak adlandırılır. Nesnenin durumunu oluştururlar. Bir sınıftan, her nesne yaratıldığında durum değişkenleri için prosesin Heap alanında yer ayrılır:
public class Circle {
    private double x;
    private double y;
    private double radius;
    private byte thickness;  
    private String color;

    . 
    . 
    .
}
Durum değişkenlerinin bellekte nasıl sıralanacaklarına Java Sanal Makinası (JSM) karar verir. Örneğin Circle sınıfı için CompressedOops özelliğinin açık olduğu 64-bitlik bir JSM'de aşağıdaki gibi bir dizilim gerçekleşir:
offset  size   type description
      0    12        (assumed to be the object header + first field alignment)
     12     1   byte Circle.tickness
     13     3        (alignment/padding gap)
     16     8 double Circle.x
     24     8 double Circle.y
     32     8 double Circle.radius
     40     4 String Circle.color
     44    20        (loss due to the next object alignment)
     64              (object boundary, size estimate)
Durum değişkenleri otomatik olarak ilklendirilir. İlklendirme değeri tamsayı ve kayan noktalı sayılar için 0, boolean için false ve tipi sınıf olan tüm değişkenler için ise null değeridir:
Veri Tipi
Varsayılan Değeri
boolean
false
char
\u0000
int,short,byte / long
0 / 0L
float /double
0.0f / 0.0d
Tüm referans tipler
null
  • Değer tipli değişken Tipi Java'daki temel tiplerden seçilmiş olan değişkenlerdir. Değişkenleri bellekte bir kutu olarak düşünebiliriz. Değer saklayan değişkenlerde, kutuyu açtığımızda, içinden tanımlandığı tipte bir değer ile karşılaşırız. Kutunun boyu, temel tipin tanımladığı uzunluktadır. Örneğin byte için bir sekizlik (1-Byte), long için 8 sekizlik (8-Byte), char için ise iki sekizlik olacaktır.
  • Referans değişkeni Temel tipler dışında, tipi bir sınıf olan değişkenler referans değişkenidir. Bu değişkenler için kutuyu açtığımızda içinden referans ettiği nesnenin adresi çıkar. 32-bit JSM için 32-bit ve 64-bit JSM için ise Heap alanının boyuna göre 32-bitten 64-bite kadar değişken uzunlukta olabilir.
  • Skalar değişken Skalar değişkenler sadece tek bir değer ya da nesnenin referansını saklayabilen değişkenlerdir:
int x= 42;
String name= "Jack";
double pi= 3.1415;
Circle blueUnitCircle= new Circle(0.,0.,1.,"Blue");
  • Dizi değişkeni Bazen bir değişkende birden fazla değer ya da nesne saklamak isteriz. Bu durumda dizilerden yararlanılır. Dizi tanımlamak kolaydır. Tek boyutlu bir dizi köşeli parantez çifti kullanılarak tanımlanabilir:

int lost[];
int []array;
Köşeli parantez çifti ([]) değişkenin önünde ya da arkasında kullanılabilir. Dizinin tanımını yaptık ama henüz bellek gözleri için yer almadık. Dizinin gözlerini yaratmak için farklı yöntemler kullanılabilir:
int lost[] = { 4, 8, 15, 16, 23, 42 };
int[] array;
int []dizi;
array = new int[] { 4, 8, 15, 16, 23, 42 };
dizi= new int[6];
dizi[0]= 4;
dizi[1]= 8;
dizi[2]= 15;
dizi[3]= 16;
dizi[4]= 23;
dizi[5]= 42;
int []lottery;
lottery= new Random().ints(1,49).distinct().limit(6).sorted().toArray();
int []sequence;
sequence= IntStream.range(1, 100).toArray();
Dizi elemanları bellekte ardışıl gözlerde saklanırlar. Dizi eleman sayısını bilir:
Şekil-1 Java'da diziler
Dizi gözlerine, gözün indisini köşeli parantez içerisinde vererek erişiyoruz. Dizi indisleri sıfırdan başlayarak adreslenir. Tamsayı değerler ile dolu bir dizinin elemanlarının toplamı için aşağıdaki çözümleri kullanabiliriz:
int[] sequence = IntStream.range(1, 100).toArray();
long sum = 0;
for (int i = 0; i < sequence.length; ++i) {
    sum += sequence[i];
}

int[] sequence = IntStream.range(1, 100).toArray();
long sum = 0;
for (int cell : sequence)
    sum += cell;

int[] sequence = IntStream.range(1, 100).toArray();
long sum = Arrays.stream(sequence).sum();
Dizinin gözlerine erişirken indisin sınırlar dışına çıkmadığından emin olun. Aksi halde yürütme zamanında IndexOutOfBoundsException hatası ile karşılaşırsınız. Neden böyle oldu? sorusunun yanıtını bulup, kodun bu hatayı üretmemesini sağlamalısınız! for-each (for (int cell : sequence)) yapısını kullanırsanız, zaten bu hata ile hiçbir zaman karşılaşmazsınız. Ancak bu yapının salt okunur olduğuna dikkat etmelisiniz: Mevcut dizide bir değişiklik yapamazsınız!
Circle[] circles = new Circle[10];
for (Circle circle: circles){
    circle= new Circle(0.,0.,1.,"Blue");
}
for (Circle circle: circles){
    System.err.println(circle.area());
}
Yukarıdaki kodu çalıştırırsanız, java.lang.NullPointerException hatasını alırsınız! Dizi gözlerinde değişiklik yapmak için her zaman indis üzerinde dönen bir döngü kurmanız gerekir:
Circle[] circles = new Circle[10];
for (int i=0;i<circles.length;++i){
    circles[i] = new Circle(0.,0.,1.,"Blue");
}
for (Circle circle: circles){
    System.err.println(circle.area());
}
Eğer temel tipler üzerinde aritmetik işlem yapmak üzere bir dizi oluşturacaksanız, diziyi mutlaka temel tipten tanımlayın, sakın sarmal sınıftan tanımlamayın! 
Şekil-2 Integer tipinden bir dizinin bellekteki yerleşimi
Şekil-3 int tipinden bir dizinin bellekteki yerleşimi

Hem bellekte hem de çalışma süresinde kaybedersiniz:
package com.example.test;

public class TestWrapperPrimitiveArrays {
 private static final int LOOP_COUNT = 50;
 private static Integer[] bigIntegerArray = new Integer[1_000_000];
 private static int[] bigIntArray = new int[1_000_000];
 static {
  for (int i = 0; i < bigIntegerArray.length; ++i)
      bigIntegerArray[i] = new Integer(1);
  for (int i = 0; i < bigIntegerArray.length; ++i)
      bigIntArray[i] = 1;
 }

 public static void main(String[] args) {
  System.err.println("Wrapper");
  for (int i = 0; i < LOOP_COUNT; ++i)
      runWrapper();
  System.err.println("Primitive");
  for (int i = 0; i < LOOP_COUNT; ++i)
      runPrimitive();
 }

 public static void runWrapper() {
  long startTime = System.nanoTime();
  long sum = 0;
  for (Integer x : bigIntegerArray)
      sum += x;
  long stopTime = System.nanoTime();
  System.err.println("Sum: " + sum + " @ " + (stopTime - startTime));
 }

 public static void runPrimitive() {
  long startTime = System.nanoTime();
  long sum = 0;
  for (int x : bigIntArray)
      sum += x;
  long stopTime = System.nanoTime();
  System.err.println("Sum: " + sum + " @ " + (stopTime - startTime));
 }

}
Bir Integer tipinde nesne bellekte 16 Byte yer kaplar, buna karşılık olarak int tipi ise sadece 4 Byte! 1 milyon elemanlı dizi için toplam harcanan bellek miktarı, referanslar da dahil olmak üzere, Integer tercihi (Şekil-2) için 20 milyon Byte ve int tercihi (Şekil-3) için ise 4 milyon Byte olacaktır. int tipini tercih ederseniz kapladığı alan beşte birine düşüyor! Çalışma zamanları karşılaştırıldığında ise int tipi dizi üzerinde elemanları toplamak için geçen süre, Integer tipindeki dizinin elemanlarını toplamak için geçen sürenin  üçte biri kadardır. Kazanan yine temel tip: int!
İki Boyutlu Diziler 
İki boyutlu dizileri matris olarak adlandırıyoruz. Matris tanımlamak, tek boyutlu dizi tanımlamaktan çok farklı değil. İki boyutlu olduğunu belirtmek için köşeli parantez çiftinden iki tane kullanıyoruz: 
int [][]unitMatrix= {
 {1, 0, 0}, 
 {0, 1, 0}, 
 {0, 0, 1} 
};
Genel olarak n-boyutlu bir dizi tanımlamak için n adet köşeli parantez çifti kullanılır. Çok boyutlu diziler bellekte satır düzeninde yerleşirler. Bu nedenle, unitMatrix[0] birinci satırı, unitMatrix[1] ikinci satırı ve elbette unitMatrix[2] üçüncü satırı tanımlar. unitMatrix.length matrisin satır sayısını verir. Matris kare matris ise satır sayısı sütun sayısına eşit olacaktır. Bu durumda, unitMatrix.lengthunitMatrix[0].lengthunitMatrix[1].lengthunitMatrix[2].length değerlerinin hepsi biri birine eşit olacaktır. Java'da matrisin satırlarında farklı sayılarda eleman bulunabilir. Matrisi farklı şekillerde tarayabiliriz:
int[][] unitMatrix = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
for (int i=0;i<unitMatrix.length;++i){
   int []row= unitMatrix[i];
   System.err.println(Arrays.toString(row));
}

int[][] unitMatrix = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
for (int[] row : unitMatrix) {
    System.err.println(Arrays.toString(row));
}

int[][] unitMatrix = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
Arrays.stream(unitMatrix)
      .map(Arrays::toString)
      .forEach(System.err::println);
Yukarıdaki her üç kod parçası için de ekran çıktısı aşağıdaki gibi gerçekleşir:
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
Diziler Üzerinde Paralel İşlemler
Java 8 ile çok çekirdekli platformlar üzerinde paralel koşan uygulamalar geliştirebiliyoruz. Bu bölümde, büyük veriler işlenirken sıklıkla kullanılan temel vektör ve matris işlemlerinin, Stream API ve Lambda ifadeleri kullanılarak, nasıl gerçekleştirildiğini çalışacağız. Önce vektör iç çarpımını ele alalım.
Vektör İç Çarpımı
u ve v gibi iki vektörün iç çarpımı aynı indisli elemanlarının çarpımının toplamı olarak tanımlanır:
$$\langle u , v \rangle = \sum_{i=1}^{n}u_i v_i$$. Bu tanım hem seri olarak hem de Java 8'de gelen paralel stream kullanılarak gerçeklenebilir:

package com.example.test;

import java.util.Random;
import java.util.function.BiFunction;
import java.util.stream.IntStream;

public class DotProductExample {
 private static final int ARRAY_SIZE = 300_000_000;
 private static final int LOOP_COUNT = 50;
 static int[] u;
 static int[] v;
 static {
  System.err.print("Populating u...");
  u = new Random().ints(0, 2).limit(ARRAY_SIZE).toArray();
  System.err.print("Done.\nPopulating v...");
  v = new Random().ints(0, 2).limit(ARRAY_SIZE).toArray();
  System.err.print("Done.\n");
 }

 public static void main(String[] args) {
  for (int i = 1; i <= LOOP_COUNT; ++i) {
   run(i, "Serial", DotProductExample::dotProductSerial);
  }
  for (int i = 1; i <= LOOP_COUNT; ++i) {
   run(i, "Stream", DotProductExample::dotProductStream);
  }
 }

 private static void run(int runNo, String method,
   BiFunction<int[], int[], Integer> productFunction) {
  long startTime = System.nanoTime();
  int product = productFunction.apply(u, v);
  long stopTime = System.nanoTime();
  System.err.println(String.format("[%-8s][%3d]:[%10d]@[%10d]", method,
    runNo, product, stopTime - startTime));
 }

 private static Integer dotProductSerial(int[] u, int[] v) {
  int sum = 0;
  for (int i = 0; i < u.length; ++i)
   sum += u[i] * v[i];
  return sum;
 }

 private static Integer dotProductStream(int[] u, int[] v) {
  return IntStream.range(0, u.length).parallel().map(i -> u[i] * v[i])
    .sum();
 }

}
Matris Çarpımı
A ve B gibi iki matrisin çarpımı,
$$
C_{m,n} = A_{m,s} \times B_{s,n}
$$
$$
A_{m,s} =
\begin{pmatrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,s} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,s} \\
\vdots & \vdots & \ddots & \vdots \\
a_{m,1} & a_{m,2} & \cdots & a_{m,s}
\end{pmatrix},
B_{s,n} =
\begin{pmatrix}
b_{1,1} & b_{1,2} & \cdots & b_{1,n} \\
b_{2,1} & b_{2,2} & \cdots & b_{2,n} \\
\vdots & \vdots & \ddots & \vdots \\
b_{s,1} & b_{s,2} & \cdots & b_{s,n}
\end{pmatrix},
C_{m,n} =
\begin{pmatrix}
c_{1,1} & c_{1,2} & \cdots & c_{1,n} \\
c_{2,1} & c_{2,2} & \cdots & c_{2,n} \\
\vdots & \vdots & \ddots & \vdots \\
c_{m,1} & c_{m,2} & \cdots & c_{m,n}
\end{pmatrix}
$$
$$
c_{i,j} = \sum_{k=1}^{k=s} a_{i,k} b_{k,j}
$$
biçiminde tanımlanır. Bu tanıma uygun olarak çarpımı hem seri olarak hem de Stream API kullanarak hesaplayan kodu aşağıda bulabilirsiniz.
package com.example.test;

import java.util.Arrays;
import java.util.stream.IntStream;

public class MatrixProductExample {
 private static final int LOOP_COUNT = 25;
 private static final int A_ROW_SIZE = 3000;
 private static final int A_COL_SIZE = 400;
 private static final int B_ROW_SIZE = 400;
 private static final int B_COL_SIZE = 5000;
 private static final int C_ROW_SIZE = 3000;
 private static final int C_COL_SIZE = 5000;
 private static final int[][] A;
 private static final int[][] B;
 private static final int[][] C;

 static {
  A = new int[A_ROW_SIZE][A_COL_SIZE];
  B = new int[B_ROW_SIZE][B_COL_SIZE];
  C = new int[C_ROW_SIZE][C_COL_SIZE];
  System.err.print("Populating A...");
  populateMatrix(A);
  System.err.print("Done.\nPopulating B...");
  populateMatrix(B);
  System.err.print("Done.\n");
 }

 private static void populateMatrix(int[][] A) {
  int rowSize = A.length;
  int colSize = A[0].length;
  IntStream.range(0, rowSize * colSize)
           .map(i -> {
                int row = i / colSize;
                int col = i % colSize;
                A[row][col] = row + col;
                return 0;
             }).sum();
 }

 public static void main(String[] args) {
  System.err.println("Matrix multiplication using Stream API.");
  for (int i = 1; i <= LOOP_COUNT; ++i)
      runStream();
  System.err.println("Matrix multiplication using 3x \"for\" loops.");
  for (int i = 1; i <= LOOP_COUNT; ++i)
      runStream();
 }

 public static void runSerial() {
  long startTime = System.nanoTime();
  productSerial(A, B, C);
  long stopTime = System.nanoTime();
  System.err.println(stopTime - startTime);
 }

 public static void runStream() {
  long startTime = System.nanoTime();
  productStream(A, B, C);
  long stopTime = System.nanoTime();
  System.err.println(stopTime - startTime);
 }

 public static void productStream(int[][] A, int[][] B, int[][] C) {
  int rowSizeA = A.length;
  int colSizeA = A[0].length;
  int colSizeB = B[0].length;
  IntStream.range(0, rowSizeA * colSizeB)
           .parallel()
           .map(i -> {
                  int row = i / colSizeB;
                  int col = i % colSizeB;
                  C[row][col] = 0;
                  for (int j = 0; j < colSizeA; ++j)
                      C[row][col] += A[row][j] * B[j][col];
                  return 0;
            }).sum();
 }

 public static void productSerial(int[][] A, int[][] B, int[][] C) {
  int rowSizeA = A.length;
  int colSizeA = A[0].length;
  int colSizeB = B[0].length;
  for (int i = 0; i < rowSizeA; ++i) {
      for (int j = 0; j < colSizeB; ++j) {
          C[i][j] = 0;
          for (int k = 0; k < colSizeA; ++k)
              C[i][j] += A[i][k] * B[k][j];
      } 
   }
 }

 private static void print(int[][] A) {
  Arrays.stream(A).map(Arrays::toString).forEach(System.err::println);
 }
}
i7 işlemcili dizüstü bilgisayarımda yukarıdaki uygulamayı çalıştırdığımda, seri çözüm ortalama 80 saniyede, Stream API tabanlı çözüm ise 25 saniyede tamamlandı. Çekirdek sayısına yakın bir hızlanmaya işaret ediyor. Yaşasın yeni kral: Java 8!
Metod Parametresi Olarak Diziler
Dizileri metotlara parametre olarak geçebiliriz. Bunun için metod parametresini dizi türünden tanıtmamız yeterli olacaktır:
public static long sumIf(int[] values, Predicate<Integer> constraint) {
 long sum = 0;
 for (int value : values) {
  if (constraint.test(value))
   sum += value;
 }
 return sum;
}
Stream API kullanarak bu çözümü daha yalın olarak tanımlayabiliriz:
public static long sumIf(int[] values, IntPredicate constraint) {
 return Arrays.stream(values).filter(constraint).sum();
}
sumIf fonksiyonunu çağırmak için önce bir dizi yaratmamız gerekiyor:
public static void main(String[] args) {
 int[] bigData = new Random().ints(1, 10000)
                       .limit(SIZE)
                       .toArray();
 sumIf(bigData, i -> i > 0 && i < 100);
}
Fonksiyona dizi türünde parametre geçmek için Java SE 5 ile bir diğer gösterim daha bulunuyor. Üç nokta (...) gösterimini, C programlama dilinden de biliyoruz. Metodun değişken sayıda parametre alacağını ifade ediyor. Gerçekte, fonksiyona verdiğimiz parametreler, derleyici tarafından diziye dönüştürülür ve dizi olarak çağrılır. Dizi oluşturmak için kod yazmakla gereksiz vakit kaybedilmemiş olur. Bu özellik, sadece gösterim kolaylığı sağlar. Üç nokta ile tanımlanan parametreyi dizi ile de doğrudan çağırabilirsiniz.
private static final int SIZE = 5000;

public static long sumIf(IntPredicate constraint, int... values) {
 return Arrays.stream(values).filter(constraint).sum();
}

public static void main(String[] args) {
 int[] bigData = new Random().ints(1, 10000).limit(SIZE).toArray();
 sumIf(i -> i > 0 && i < 100, bigData);
 sumIf(i -> i / 2 != 0, 4, 8, 15, 16, 23, 42);

}
Uymanız gereken iki basit temel kural var:
1. Üç nokta mutlaka metodun parametre listesinde sonda yer almalıdır
2. Birden fazla üç nokta tanımlaması yer alamaz.
Java 9+'da Diziler ile İlgili Yenilikler
Java 9 ve sonrasında diziler ile ilgili bizi bekleyen önemli iki gelişme bulunuyor. Bunlardan ilki sadece değer taşıyan durumu değiştirilemez (=Immutable) nesnelerin belleğe etkin yerleşimi ile ilgilidir. Örneğin, görüntüyü oluşturan benekleri Pixel adlı bir sınıfta modelleyelim:
public class Pixel {
    int red;
    int green;
    int blue; 
    double alpha; // 0 <= alpha <= 1
}
Pixel tipinden bir dizi tanımlarsak, belleğe Şekil-4'deki gibi yerleşecektir ve bu yerleşimin hiç verimli olmadığı açıktır. Hem kapladığı alan gereğinden fazladır hem de bellekte ardışıl gözlere yerleşmedikleri için cep bellekte çok sayıda ıskalama yapacaktır.
Şekil-4 Pixel tipinden bir dizinin bellekteki yerleşimi
Bu problemleri çözmek için Pixel sınıfını "value class" olarak tanımlıyoruz:
value public class Pixel {
    final int red;
    final int green;
    final int blue; 
    final double alpha;
    . . . 
}
Şimdi yerleşim bir öncekinden farklı olarak ardışıl olacaktır:
Şekil-5 Pixel tipinden bir dizinin "value class" olarak bellekteki yerleşimi
Elbette "value class"'larda hala çok şekillilik çalışmaya devam ediyor! Generics çatısında buna paralel bir değişiklik bekliyoruz:
new ArrayList<int>()
Evet, artık tip parametresi olarak temel tip verebiliyoruz! Burada JSM, yürütme zamanında yeni bir sınıf yaratıyor: ArrayList${T=int}.class. Bu durum bana hiç yabancı gelmedi: C++'da üretken programlama zaten bu şekilde çalışıyor!
Bu konudaki gelişmeleri aşağıdaki bağlantılardan takip edebilirsiniz:

No comments:

Post a Comment