Bir önceki yazıya kaldığımız yerden devam edelim.

Tüm bu ölçümler sonuçta JVM’ler üzerinde herhangi bir oynama yapmadan elde edildiler. Algoritmanın performansını arttırmak için yapılacak bir şey var mı diye bakınca aslında algoritmanın kodunda zaten ufak bir-iki iyileştirmenin yapıldığı görülmektedir. Yani algoritmada

double distance = Math.sqrt(Math.pow(x, 2) + Math.pow(y,2));

satırı

double distance = x * x + y * y;

satırı ile değiştirilmişti. Bu ise bizi hem Math.sqrt() ile kare kök almaktan hem de her döngüde iki defa Math.pow() çağrısı yapmaktan kurtardı. Yukarıdaki kodu Math.sqrt() ve Math.pow() metot çağrıları yapacak şekilde değiştirince, n=1000000 için örneğin MacBook Pro’daki 41,70 mili second olan süre yaklaşık 46 miliseconda, n=10000000 için de 415,90 mili seconddan 445 mili seconda çıkıyor. Bu demektir ki biz zaten kodumuzda bu iki metot çağrısını yapmayarak yaklaşık %10luk bir performans artışı kazandık.

Bir başka hızlandırma noktası da rastgele sayı üretimi olabilir. Açıkçası JDK ile gelen yapıların o konudaki en hızlı en optimize kodlar olmadığını tecrübemle biliyorum. Örneğin daha önce de java.util.StringTokenizer‘ı kendim geliştirdiğim çok daha hızlı ve amacım açısından optimize edilmiş bir başka tokenizer ile değiştirmiştim. Aynı şeyi java.lang.Math sınıfındaki random() metodu için de yapabiliriz. Bu durumda ilk akla gelen java.util.Random sınıfı oluyor. Bu sınıfın nextDouble() metodunu kullanınca performansta pek bir değişik olmadı. Sebebi de tam tahmin ettiğim gibi, java.lang.Math sınıfının random() metotu zaten java.util.Random sınıfını kullanıyor 🙂

Apache Commons’daki Math kütüphanesinde de bayağı rastgele veri üreten yapılar var. Dolayısıyla buradaki bir kaç yapıyı denedim ve org.apache.commons.math.random paketindeki MersenneTwister sınıfı mükemmel sonuç verdi. Bu sınıfı kullanmak için koddaki sınıfa

private static BitsStreamGenerator randomData = new MersenneTwister();

satırını ekledim ve

double x = Math.random();
double y = Math.random();

satırlarını

double x = randomData.nextDouble();
double y = randomData.nextDouble();

ile değiştirdim. Macbook Pro üzerindeki şu sonuçlara bakın:

Bu tablodan çıkan sonuç şu, n=10.000 için henüz bir performans ilerlemesi yok ama daha yüksek n sayıları için MersenneTwister sınıfı mükemmel bir performans gösteriyor. Örneğin n=10.000.000 için %57lik, n=100.000.000 için %53lük, n=1.000.000.000 için ise benzer şekilde %52lik bir performans ilerlemesi elde ettik. Burada Apache Commons Math kütüphanesinin hem 2.2 hem de 3.3 sürümlerini kullandığımı ama yukarıdaki sonuçları 2.2 ile aldığımı belirtmeliyim. İlginç bir şekilde 3.3 sürümü, 2.2’ye göre yaklaşık %10 daha yavaş çalıştı. Tabi rastgele sayı üretmek zor iştir, üretilen sayıların rastgele olması açısından olabildiğince bağımsız olması önemlidir. Burada kullandığım MersenneTwister sınıfı için bu konuda daha ayrıntılı bilgi almak isteyenler buraya bakabilirler.

Muhtemelen daha hızlı rastgele sayı üreten yapılar bulunup bu performans daha da arttırılabilir.

Bir sonraki yazıda ise JVM tuning ile neler yapabiliriz buna bakalım.

Toplam görüntülenme sayısı: 902

Monte Carlo metodu, algoritmik çözümü zor olan matematiksel ve fiziksel problemleri, rastgele (random) sayılar üreterek, simule ederek çözmeyi amaçlayan yaklaşımlara verilen ortak addır. Monte Carlo’daki gazinolardaki kumar aletlerinin rastgele sonuç üretmesine atıf olarak bu isim verilmiştir. Optimizasyon problemlerinde sıklıkla kullanılır.

Monte Carlo metodunu, pi sayısını bulmak için de kullanabiliriz. Bakın şöyle: Kartezyen koordinat sisteminde merkezi (0,0) noktasında olan ve yarı çapı 1 birim olan bir çember çizin ile bu çembere teğet geçen bir de kare çizin. Çemberin ve karenin alanlarının oranı pi/4 yapar. Bu şu demektir: Bu çizime rastgele bir nokta atarsanız, bu noktanın, çemberin içine düşmesi ihtimali pi/4 eder.

Bu gerçeği tersten okuyalım şimdi de: Eğer bu çizime sonsuz tane nokta atılırsa, bu şekli tamamen kapsamış oluruz. Yani bu şekile n tane nokta atalım ve bu noktaların r tanesinin çemberin içine düştüğünü varsayalım. n sonsuza giderken, 4r/n oranının pi‘ye yaklaştığını görürsünüz. n‘yi 1 yaparsanız, yani 1 nokta atarsanız bu oran ya 0 ya da 4 olacaktır. n sayısını arttırdıkça bu oranın gittikçe pi sayısına yakınsadığını, ne kadar çok nokta atarsanız, pi‘nin gerçek değerine (ki böyle bir şey yok! dolayısıyla daha doğru tabirle, virgülden sonraki rakamları doğru bir şekilde bulmaya başlarsınız) yakınsarsınız. Bu durumu şuradaki ya da şuradaki applet ile görebilirsiniz ya da Youtube’taki pek çok videodan birini seyredebilirsiniz.

Bu algoritmayı Java ile şöyle gerçekleştirebiliriz:

import java.util.Scanner;

public class MonteCarloPI {
	public static void main(String[] args) {
		int dotsInCircle = 0;
		System.out.print("Number of points: ");
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		
		double start = System.currentTimeMillis();
		for(int i = 0; i<n; i++){
			double x = Math.random();
			double y = Math.random();
//			double distance = Math.sqrt(Math.pow(x, 2) + Math.pow(y,2));
			double distance = x*x + y*y;
			if(distance <= 1.0)
				dotsInCircle++;
		}
		double finish = System.currentTimeMillis();
		
		double seconds = (finish-start)/1000;
		double myPI = (double) 4*dotsInCircle/n;
		System.out.println("My PI is: " + myPI + " and Java's PI is: " + Math.PI);
		System.out.println("Time is: " + seconds);
	}
}

Yukarıdaki program, girilen sayı kadar rasgele (x, y) noktası üreterek, her bir noktanın (0, 0) merkez noktasına uzaklığı hesaplanır ve bu uzaklığın 1’e eşit ya da ondan küçük olup olmadığı kontrol edilir, eğer eşit ya da küçük ise, bu demektir ki nokta çemberin içine düşmüştür ve yukarıdaki algoritmanın anlatımında r dediğimiz ve programda dotsInCircle ile temsil ettiğimiz değişkenin değeri arttırılır.

Yukarıdaki kodu n=1 için çalıştırırsanız sonuç ya 0 ya da 4 çıkacaktır. Çünkü o tek nokta ya dairenin içine ya da dışına düşecektir. Dolayısıyla salınım 0 ile 4 arasında gerçekleşecektir. Ama örneğin n=10 yaparsanız gelebilecek sonuçlardan birisi şöyle olabilir: Hesaplanan pi = 2.800000  ve hata yüzdesi %10.873232. Yani yaklaşık %11 hatayla Java’nın Math sınıfındaki PI’ye (3.141592653589793) yakınsanmış demektir. Ama n sayısını 1.000.000.000 yapınca pi = 3.141536  ve hata yüzdesi % 0.001809 olarak elde ettim.

Tabi sağlıklı ortalama değerler için, aynı n sayısı için olarak olabildiğince çok çalıştırma yapılmalıdır. Ben de bu amaçla yukarıdaki algoritmayı aşağıdaki gibi değiştirdim.

package org.javaturk.oop.ch05;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class MonteCarloPITiming {
	private static int runCount = 100;
	private static int n;
	
	private static List<Double> pis = new ArrayList<Double>();
	private static List<Double> times = new ArrayList<Double>();
	private static List<Double> percentages = new ArrayList<Double>();
	
	public static void main(String[] args) {
		System.out.print("Number of points: ");
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		for(int i = 0; i < runCount; i++){
			calculatePI();
		}
		printResults();
	}

	private static void printResults() {
		double meanTime = 0;
		double meanError = 0;
		System.out.printf("%10s %10s %10s\n", "Time  ", "Calculated PI", "Error %  ");
		for(int i = 0; i < runCount; i++){
			meanTime += times.get(i).doubleValue();
			meanError += percentages.get(i).doubleValue();
			System.out.printf("%10f %10f %10f\n", times.get(i).doubleValue(), pis.get(i).doubleValue(), percentages.get(i).doubleValue());
		}
		meanTime /= runCount;
		meanError /= runCount;
		System.out.printf("Mean time: %10f\n", meanTime);
		System.out.printf("Mean error: %10f", meanError);
	}

	public static void calculatePI() {
		int dotsInCircle = 0;
		double start = System.currentTimeMillis();
		for (int i = 0; i < n; i++) {
			double x = Math.random();
			double y = Math.random();
			// double distance = Math.sqrt(Math.pow(x, 2) + Math.pow(y,2));
			double distance = x * x + y * y;
			if (distance <= 1.0)
				dotsInCircle++;
		}
		double finish = System.currentTimeMillis();
		double seconds = (finish - start);
		times.add(seconds);
		double myPI = (double) 4 * dotsInCircle / n;
		pis.add(myPI);
		double diff = Math.abs((Math.PI - myPI)); 
		double percentage = diff * 100 / Math.PI;
		percentages.add(percentage);
	}

}

Yani programın başındaki runCount (ki değeri 100) kadar aynı n sayısı için algoritmayı çalıştırıyorum ve her çalışmanın sonuçlarını List nesnelerine koyuyorum. runCount defa çalışma bitince de hem sürenin hem de hata yüzdesinin ortalamasını alıyorum. Beklentim şu: n arttıkça süre de artacak çünkü daha çok nokta atacağım ama tabi olarak hata yüzdesi azalacak çünkü pi‘ye daha çok yakınsayacağım. Örneğin farklı n sayıları için aşağıdaki ortalama ölçümleri elde ettim:

MacBook Pro i7 2,5 GHz. 16 GB RAM, MacOS 10.10.1 Yosemite konfigürasyonunda:

Toshiba Satellite i7 2,4 GHz. 8 GB RAM, Windows 8.1 konfigürasyonunda:

Her iki konfigürasyonda da Java 1.8.0_25 HotSpot 64-bit server JVM çalışıyordu.

Yukarıdaki sonuçlardan şunları söyleyebiliriz:

• Algoritmada n tane for döngüsünün her birinde iki defa Math.random() çağrısı, iki defa çarpma işlemi, bir tane kıyas (<=), bir tane de artım yapılıyor. Dolayısıyla algoritmanın karmaşıklığı 0(n) (bigO(n)) görünüyor. Yani algoritmanın zaman ihtiyacı doğrusal olarak artacaktır. Zaten sonuçlar da bunu gösteriyor. n sayısı 10 katına çıkınca, gerekli süre de yaklaşık 10 katına çıkıyor.
• İkincisi konfigürasyonları çok yakın, JVMleri aynı sürüm olmasına rağmen MacBook Pro, Toshiba’dan yaklaşık %10 civarında daha hızlı çalıştı. Bu durum MacBookPro’daki CPU’nun biraz daha hızlı olması yanında envai çeşit farklı faktörler üzerinden açıklanabilir. Çok önemli bir fark değil açıkçası.

Bu algoritma o kadar basit ki, anlaşılması, kodlanması vs. çok kolay. Ama bu algoritma bir o kadar da güzel, güzel ötesi, neffiiisss. Matematiğin ve sayıların güzelliğini ortaya koyuyor, herkesin anlayacağı basitlikte.

Toplam görüntülenme sayısı: 1124