Bu konuyla ilgili üçüncü yazıyı yazdığıma göre artık bir seriden bahsedebiliriz :)
Serinin ilk iki yazısına aşağıdaki linklerden ulaşabilirsiniz:
Yeni sorumuz ise şöyle:
Bir fibonacci serisinde verilen sıradaki sayıyı dönen fonksiyonu yazınız.
Fibonacci serisi ya da sekansı, ilk iki elemanı hariç bir sayı dizisinde her elemanın kendisinden önceki iki elemanın toplamından oluştuğu seriyi ifade eder. Serinin ilk iki elemanı 0 ve 1 'dir.
İlk akla gelen çözüm bir for döngüsü kullanmak olabilir:
function fib(n) { const fibonacci = [0, 1]; for (let i = 2; i <= n; i++) { fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]; } return fibonacci[n]; }
Bu çözümde fibonacci serisinin ilk iki elemanını 0 ve 1 olarak yazıp; istenen elemana kadar serinin tüm elemanlarını teker teker oluşturuyoruz. Bu nedenle de for döngüsü serinin 3. elemanına denk gelecek şekilde 2'den başlayıp n'de yani istenen elemanda bitiyor. Döngünün içinde her bir elemanı kendisinden önceki iki elemanı toplayarak bulup seriye ekliyoruz. döngüden çıktıktan sonra da istenen sıradaki elemanı dönerek (return) fonksiyonu tamamlıyoruz.
Beklenen çözüm bu olmakla birlikte takiben 1-2 soruyla karşılaşabilirsiniz. Örneğin yazdığınız bu çözümün "Runtime Complexity"'si nedir diye sorulabilir. Time complexity ya da Runtime Complexity geniş bir konu. Burada detayına girmeyeceğim ancak sorulan şey aslında yazdığınız bu kodun çalışacağı sürenin, verdiğiniz parametreler değiştikçe nasıl değişeceği. Yazdığımız çözüm için time complexity'si linear'dir diyebiliriz. Yani verdiğimiz n değeri arttıkça yaptığımız işlem sayısı aynı miktarda artmakta. For döngüsünün içindeki hesaplama işlemine dikkat ederseniz her dönüş için bir hesaplama yaptığımızı ve parametre olarak verilen n sayısı kadar dönüş yaptığımızı görürsünüz.
Diğer bir soru recursive bir çözüm üretilip üretilemeyeceği olabilir. Aşağıdaki çok basit kod parçacığı sorunun recursive çözümünü oluşturuyor:
function fib(n) { if (n < 2) { return n; } return fib(n - 1) + fib(n - 2); }
Bu yazması çok kolay çözümü kendi başınıza bulduysanız, sizi tebrik ederim. :) Çünkü ilk denediğimde ben bulamamış ve çözümü araştırmak zorunda kalmıştım. Çok basit bu kod bloğu, o kadar da kolay akla gelmeyebiliyor. Peki nasıl bir çözüm uyguluyoruz: Öncelikle sabit olarak belirlediğimiz ilk iki elemandan biri soruluyorsa hemen cevabı girilen parametre olarak dönüyoruz. Daha sonraki elmanlardan biri soruluyorsa: Sorulandan bir ve iki önceki elemanlar için fonksiyonu kendi içinde yeniden çağırıyoruz (recursive) ve sonuçları toplayarak return ediyoruz.
Peki neler oluyor?
n=0 ve n=1 değerleri için tekrar fonksiyon çağırmadan 0 ve 1 değerlerini dönüyoruz. Diğer değerler için ise fib fonksiyonunu çağırmaya devam ediyoruz. Görselleştirmeye çalışırsak n=5 değeri için aşağıdaki gibi bir durum ortaya çıkıyor.
Bu çözüm özellikle sorulduğu için sunulmalı ve yaratacağı performans sorunlarının olabileceği mutlaka belirtilmeli. Recursive bir çözüm özellikle istenmediği sürece döngüsel çözümü kullanmak gerekli diye düşünüyorum.
Diyelim ki recursive bir çözüm istendi. Çözümü yazdık. Time Complexity'sini söyledik. Oluşturabileceği performans sorunlarını işaret ettik. Ardından hemen şu soru gelebilir: Bu çözümü nasıl iyileştirebiliriz? Açıkçası sizden recursive çözüm isteniyorsa ulaşılmak istenen sonuç da muhtemelen budur.
Memoization denen bir kavram var. Basitçe bir cache oluşturmak olarak düşünebiliriz. Fonksiyonun çağırıldığı argümanlar için döndüğü sonucu bir yerde saklıyor ve tekrar çağrıldığında hesaplama yapmak yerine bu sonucu dönüyoruz. Aynı fonksiyonun, aynı parametrelerle tekrar tekrar çağrılması durumunda işlem zamanını bu şekilde azaltabiliriz. Şemada da görebileceğiniz gibi fib(2) ve fib(3) pek çok yerde çağrılıyor. İkinci ve sonraki çağrılarda hesaplama yapmadan sonucu dönüyor olacağız.
function memoize(fn) { const cache = {}; return function (...args) { if (cache[args]) return cache[args]; cache[args] = fn.apply(this, args); return cache[args]; }; } function slowFib(n) { if (n < 2) { return n; } return fib(n - 1) + fib(n - 2); } const fib = memoize(slowFib);
İlk önce memoize isimli bir fonksiyon tanımlıyoruz. Bu fonksiyon ile cache'imizi oluşturuyoruz. slowFib fonksiyonu ise daha önce yazmış olduğumuz recursive çözüm. Son olarak da slowFib fonksiyonunu memoize fonksiyonuna parametre olarak geçip cache'e alınmasını sağlıyoruz.
memoize fonksiyonu cache olarak kullanılmak üzere boş bir obje oluşturuyor. Kendisine parametre olarak geçilen fonksiyonu ve parametrelerini bu obje içerisinde sonucu ile birlikte saklıyor. Eğer daha önce cache'e bu parametreler ile bir çağrı atılmışsa, sonucu fonksiyonu yeniden çağırmadan dönüyor aksi halde fonksiyonu istenen parametreler ile çağırıyor ve yine sonucu dönüyor.
Pek çok konuya değindiğim bir yazı oldu. Hem Fibonacci serilerinden, hem Time Complexity'den hem de Memoization'dan bahsetmiş olduk. Yazılan kodun performansının tahmin edilmesi ve gerekli görüldüğü halde iyileştirmelerin yapılması yazılım geliştiriciliği açısından göz önünde bulundurulması gereken konular. Umarım faydalı olmuştur.
Esen kalın. :)