Önceki kaldığımız yerden Shuffle sorusunun cevabı;
-Evet, bu soruda uniform methodumuzda 0 ile N arasında rastgele bir int sayısı (double değil) belirliyoruz.
-Shuffle methoduna baktığımızda, for döngüsünde Nye kadar gidiyoruz ve yeni bir r sayısı belirliyoruz. Bu r sayısı I + ratgele uniform metodu(N-i) olacak şekilde çağırıyoruz ve bununla r sayımız her I değiştiğinde başka ratgele sayı olarak belirleniyor. Sonrada a ile a[r] ninci sayıları birbirleriyle tekrar karıştırıyoruz.
-Böylece önce baştan sona her array elemanına rastgele sayılar belirlemiş olduk(1.olay)
-Belirlenen bu sayıları birbirleriyle tekrar karıştırdık(2.olay)
-------
Soru- Şimdi recursive bir örnek olan Binary Searche bakalım
Bazı önemli algoritmalar searching(arama) ve sorting(sıralama) olarak ayrılmıştır, bunlar programları hızlı çalıştırmada etkindirler, bu methodlar bazen normal for döngüleri gibi linear olarak yazıldığında daha hızlı çalşırken, bazende recursive gibi kendini tekrar tekrar çağırma methoduyla daha hızlı çalışırlar. Bu method tipleri, ileride program yazılacağı zaman verimlilik açısından çok önemlidir çünkü kimse yavaş çalışan program istemez.
Binary Search dedğimiz örnekle bunlara girelim. Elimizde düzenli olarak sıralanmış küçükten büyüğe bir süre sayı olsun ama tüm sayılar olmasın, mesela a[] arrayinde;
1, 2, 5, 7, 8, 9, 14, 15, 18, 21, 25, 30 gibi ve key(bulmak istediğimiz sayı) 21 olsun.
bu sayıların içinden istediğimiz herhangi birini bulmak için en basit haliyle düşünürsek yapacağımız heralde for döngüsü içinde baştan sona kadar ilerleyip o sayıyı bulduğumuzda durmak olur, methodumuzun adı rank olsun;
Burada görüldüğü gibi kullanıcı key adında aramak istediği sayıyı ve a[] içinde aramak istediği arrayi girecek, bizden istenen o sayının dizide kaçıncı sırada olduğu,
For döngüsünde baştan sona tek tek gidecek ve eğer a ninci eleman keye eşitse return i diyerek sırasını dönecek, eğer for bittiğinde bulamazsa return -1 diyerek içinde olmadığını belirleyecek.
Normalde bu yöntem ile kolayca bulduğumuzu düşünsekte ileride büyük projelerde, büyük methodlarda çok fazla CPU harcayacak ve program bu durum için yavaş çalışacak, burada recursive(kendi kendini çağıran) method kullanmak işi kat kat hızlandıracaktır,
Recursive methodlar for döngüsü gibi tekrar tekrar dönerler ancak mantık olarak biraz daha farklı, bu methodlar kendisini çağırabilir, mesela;
Dediğimizde, start, ende eşit olana kadar döngü devam edecek ve her seferinde rank methodunu tekrar çağırdığında start, birdahakine start + 1 den başlayacak, mesela start = 1, end = 5 olsun; start = 1 != 5 = end eşit olmadığı için while devam edecek ve rank methodunu tekrar çağırdığında start = start + 1 olacak ve artık 2 ye 5 oldu, birdahakine 3 e 5, sonra 4 e 5, en sondada 5 = 5 olacağı için return -1 den method bitecek, bu tür methodlara recursive diyoruz,
Şimdi Binary Searhü recursive yazalım;
Binary searchün mantığı sayıyı bulmak için önce onu ortadaki sayıyla kıyaslarız, eğer sayı ortadakinde büyüksa sağ tarafa, küçükse sol tarafa bakarız, bir sonrakindede kalan sayının ortasına bakarız ve böyle en sona kadar gideriz, en sondada bulduğumuz sayıyı yazarız, kodumuz şöyle;
Burada kullanıcı sadece key sırası bulunacak sayıyı ve a[] array dizisini girmişti, ancak bizim işlem yapabilmek için daha fazla parametrelere(girdilere) ihtiyacımız var bunun için aynı isimde yeni bir method yazıyoruz[Not: Aynı isme sahip olup farklı parametrelere sahip olan method yazmaya overloading denir, method isimleri aynıdır ama farklı işlemler yapılır ,buna birbirlerini çağırmak dahil olduğu gibi birinde çarpma diğerinde bölme işlemi yapmak gibi şeylerde dahildir] ve ilk methodta ikincisini çağırıyoruz, ikinci methodtada key, a[] arrayinin yanında ilk pozisyon lo, ve son posizson hi alıyoruz.
-Sonra lo yani son eleman hi yani ilk elemanı geçtiğinde -1 dönecek yani o eleman baştan sona kadar gitti ama bulamadı, bu döngünün son basamağı.(genelde ilk yazılır)
-Yeni bir mid tanımlıyoruz ve ilk ve son eleman arasını buluyoruz
-key eğer a[mid] inci elemandan küçükse birdahakine rankı tekrar çağırdığımızda lo dan başlayacak ama son eleman mid 1 de bitecek, yani döngüyü yarıya böldük.
-benzerini eğer büyükse diyoruz ve bu sefer mid+1 den başlıyoruz ve hi, son elemanına kadar gidecek, ve rank methodu tekrar yukarıdan aşağıya doğru çalışacak ama şartlarım az önce değiştirdiğimiz gibi
-en sonda küçük veya büyük olmadığı durumda tek bir eleman kalmış olacak ve o da mid olacak. Eğer kalmamış ve başlangıç lo > hi sondaki eleman olursa aradığımız key yok demektir ve -1 dönecek, varsa dediğimiz gibi midi dönecek.
Görüldüğü gibi Binary Searchü Recursive ile çözmüş olduk ve bu bize normal for ile çözümden 4-5 kat daha hızlı çözüm sağlıyor ancak bu her durum için olmaz, bazen tam tersi olur onlara sonra bakacağız..
------------------------------
Kod:
public static **** shuffle(double[] a)
{
int N = a.length;
for (int i = 0; i < N; i++)
{
int r = i + StdRandom.uniform(N-i); // 1.olay
double temp = a[i]; //Buradan itibaren 2. olay
a[i] = a[r];
a[r] = temp;
}
}
public static int uniform(int N)
{
return (int) (StdRandom.random() * N);
}-Evet, bu soruda uniform methodumuzda 0 ile N arasında rastgele bir int sayısı (double değil) belirliyoruz.
-Shuffle methoduna baktığımızda, for döngüsünde Nye kadar gidiyoruz ve yeni bir r sayısı belirliyoruz. Bu r sayısı I + ratgele uniform metodu(N-i) olacak şekilde çağırıyoruz ve bununla r sayımız her I değiştiğinde başka ratgele sayı olarak belirleniyor. Sonrada a ile a[r] ninci sayıları birbirleriyle tekrar karıştırıyoruz.
-Böylece önce baştan sona her array elemanına rastgele sayılar belirlemiş olduk(1.olay)
-Belirlenen bu sayıları birbirleriyle tekrar karıştırdık(2.olay)
-------
Soru- Şimdi recursive bir örnek olan Binary Searche bakalım
Bazı önemli algoritmalar searching(arama) ve sorting(sıralama) olarak ayrılmıştır, bunlar programları hızlı çalıştırmada etkindirler, bu methodlar bazen normal for döngüleri gibi linear olarak yazıldığında daha hızlı çalşırken, bazende recursive gibi kendini tekrar tekrar çağırma methoduyla daha hızlı çalışırlar. Bu method tipleri, ileride program yazılacağı zaman verimlilik açısından çok önemlidir çünkü kimse yavaş çalışan program istemez.
Binary Search dedğimiz örnekle bunlara girelim. Elimizde düzenli olarak sıralanmış küçükten büyüğe bir süre sayı olsun ama tüm sayılar olmasın, mesela a[] arrayinde;
1, 2, 5, 7, 8, 9, 14, 15, 18, 21, 25, 30 gibi ve key(bulmak istediğimiz sayı) 21 olsun.
bu sayıların içinden istediğimiz herhangi birini bulmak için en basit haliyle düşünürsek yapacağımız heralde for döngüsü içinde baştan sona kadar ilerleyip o sayıyı bulduğumuzda durmak olur, methodumuzun adı rank olsun;
Kod:
public static int rank(int key, int[] a)
{
for (int i = 0; i < a.length; i++)
if (a[i] == key)
return i;
return -1;
}Burada görüldüğü gibi kullanıcı key adında aramak istediği sayıyı ve a[] içinde aramak istediği arrayi girecek, bizden istenen o sayının dizide kaçıncı sırada olduğu,
For döngüsünde baştan sona tek tek gidecek ve eğer a ninci eleman keye eşitse return i diyerek sırasını dönecek, eğer for bittiğinde bulamazsa return -1 diyerek içinde olmadığını belirleyecek.
Normalde bu yöntem ile kolayca bulduğumuzu düşünsekte ileride büyük projelerde, büyük methodlarda çok fazla CPU harcayacak ve program bu durum için yavaş çalışacak, burada recursive(kendi kendini çağıran) method kullanmak işi kat kat hızlandıracaktır,
Recursive methodlar for döngüsü gibi tekrar tekrar dönerler ancak mantık olarak biraz daha farklı, bu methodlar kendisini çağırabilir, mesela;
Kod:
public static int rank(int start, int end) {
while(start != end)
return rank(start + 1, end);
return -1;
}Dediğimizde, start, ende eşit olana kadar döngü devam edecek ve her seferinde rank methodunu tekrar çağırdığında start, birdahakine start + 1 den başlayacak, mesela start = 1, end = 5 olsun; start = 1 != 5 = end eşit olmadığı için while devam edecek ve rank methodunu tekrar çağırdığında start = start + 1 olacak ve artık 2 ye 5 oldu, birdahakine 3 e 5, sonra 4 e 5, en sondada 5 = 5 olacağı için return -1 den method bitecek, bu tür methodlara recursive diyoruz,
Şimdi Binary Searhü recursive yazalım;
Binary searchün mantığı sayıyı bulmak için önce onu ortadaki sayıyla kıyaslarız, eğer sayı ortadakinde büyüksa sağ tarafa, küçükse sol tarafa bakarız, bir sonrakindede kalan sayının ortasına bakarız ve böyle en sona kadar gideriz, en sondada bulduğumuz sayıyı yazarız, kodumuz şöyle;
Kod:
public static int rank(int key, int[] a)
{
return rank(key, a, 0, a.length - 1);
}
public static int rank(int key, int[] a, int lo, int hi)
{
if (lo > hi)
return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid])
return rank(key, a, lo, mid - 1);
else if (key > a[mid])
return rank(key, a, mid + 1, hi);
else
return mid;
}Burada kullanıcı sadece key sırası bulunacak sayıyı ve a[] array dizisini girmişti, ancak bizim işlem yapabilmek için daha fazla parametrelere(girdilere) ihtiyacımız var bunun için aynı isimde yeni bir method yazıyoruz[Not: Aynı isme sahip olup farklı parametrelere sahip olan method yazmaya overloading denir, method isimleri aynıdır ama farklı işlemler yapılır ,buna birbirlerini çağırmak dahil olduğu gibi birinde çarpma diğerinde bölme işlemi yapmak gibi şeylerde dahildir] ve ilk methodta ikincisini çağırıyoruz, ikinci methodtada key, a[] arrayinin yanında ilk pozisyon lo, ve son posizson hi alıyoruz.
-Sonra lo yani son eleman hi yani ilk elemanı geçtiğinde -1 dönecek yani o eleman baştan sona kadar gitti ama bulamadı, bu döngünün son basamağı.(genelde ilk yazılır)
-Yeni bir mid tanımlıyoruz ve ilk ve son eleman arasını buluyoruz
-key eğer a[mid] inci elemandan küçükse birdahakine rankı tekrar çağırdığımızda lo dan başlayacak ama son eleman mid 1 de bitecek, yani döngüyü yarıya böldük.
-benzerini eğer büyükse diyoruz ve bu sefer mid+1 den başlıyoruz ve hi, son elemanına kadar gidecek, ve rank methodu tekrar yukarıdan aşağıya doğru çalışacak ama şartlarım az önce değiştirdiğimiz gibi
-en sonda küçük veya büyük olmadığı durumda tek bir eleman kalmış olacak ve o da mid olacak. Eğer kalmamış ve başlangıç lo > hi sondaki eleman olursa aradığımız key yok demektir ve -1 dönecek, varsa dediğimiz gibi midi dönecek.
Görüldüğü gibi Binary Searchü Recursive ile çözmüş olduk ve bu bize normal for ile çözümden 4-5 kat daha hızlı çözüm sağlıyor ancak bu her durum için olmaz, bazen tam tersi olur onlara sonra bakacağız..
------------------------------
Son düzenleme:
