Grokking Algorithms
Bölüm 1: Algoritmalara Giriş
Size güzel bulduğum bir kitabın daha tanıtımını yapmak istiyorum. Bu kitap diğer algoritma kitaplarına göre çok daha fazla görsel ile anlatmaya odaklandığı için, okuması daha kolay ve zevkli geldi. 256 sayfası olan bu kitap, algoritmaları çok ileri seviyeye kadar olmasa bile, iyi bir noktaya getirecek kadar anlatmış. Bol kitaplı günler geçirmeniz dileğiyle. İbrahim Kürce
Kitabın orjinalini şu adresten bulabilirsiniz.
Bir görevi tamamlamak için gerekli talimatlara algoritma denir.
İkili Arama
Telefon defterinizden bir kişiyi aradığınızı düşünün. İsmi K harfi ile başlıyor olsun. Büyük ihtimalle, defterin ortasından aramaya başlarsınız, çünkü K harfinin ortalarda bir yerde olduğunu bilirsiniz.
Ya da bir sözlükten, O harfi ile başlayan bir kelime aradığınızı düşünün. Yine, orta bir yerden başlarsınız.
Bu bir arama problemidir ve bu durumlar, sorunu çözmek için aynı algoritmayı kullanırlar: ikili arama algoritması.
İkili aramanın girdileri elemanları sıralanmış bir listedir. Aradığınız eleman bu listenin içindeyse, ikili arama elemanın bulunduğu yerin pozisyonunu döner, değilse null döner.
İkili aramanın nasıl çalıştığına bakarsak, 1 ile 100 arası bir sayı tutuyorum ve sizden bu sayıyı tahmin etmeye çalışmanızı istiyorum.
En az sayıda tahminle tuttuğum sayıyı bulmaya çalışacaksınız. Her tahmin ettiğinizde, söylediğiniz sayının daha az, daha çok veya doğru değer olduğunu söyleyeceğim.
Eğer, baştan itibaren 1, 2, 3, 4 … gibi tahmin edecek olsaydınız, şöyle olurdu.
Bu en ilkel tahmin etme yöntemidir. Eğer tuttuğum sayı 99 olsaydı, 99. tahminde bunu bilmiş olurdunuz ama bunu yapmanın daha iyi yolları var.
Arama Yapmak için Daha İyi Bir Yol
Önce 50 ile başlayın.
Çok düşük bir tahmin, demek ki numaraların yarısını elemiş oldunuz. Bir sonraki tahmin 75.
Çok yüksek oldu, yine de kalan numaraların yarısını elemiş oldunuz. İkili arama ile, ortadaki sayıyı tahmin edersiniz ve her seferinde kalan sayıların yarısını elemiş olursunuz. Bir sonraki sayı 63 yani 50 ile 75 sayılarının orta noktası.
Her tahminde elediğiniz sayılara bakacak olursak,
240.000 sözcüklük bir sözlük içinde arama yapacak olsaydınız,
18 adımda aramayı bitirmiş olacaktınız. İkili aramanın çalışacağı adım en kötü senaryoda, log2n(logaritma 2 tabanında n) adım olacaktır.
Logaritmalar
Logaritmaların ne olduğuna kısaca bakacak olursak, log10(100), log 10 tabanında 100 değerini bulmak için, 10 sayısının kaçıncı kuvveti 100 sayısına eşit olduğuna bakarız. 10 sayısının 2. kuvveti 100 olduğu için, log10(100) = 2 olur. Genel olarak, logn dediğimiz vakit, bu log2n, yani logaritma 2 tabanında n demek olur.
İkili aramanın Python dilinde nasıl yazılacağına bakarsak, kod örneği dizileri kullanır. Dizileri, belirli indeks değerleriyle erişebileceğimiz bellekte art arda yerleşmiş veriler olarak düşünebiliriz. İlk değerlerini almak için 0. indeksi kullanmamız gerekir.
binary_search fonksiyonu sıralanmış bir dizi ile aranan elemanı parametre olarak alır. Aranan eleman dizi içindeyse, fonksiyon onun pozisyonunu döner. Dizinin hangi kısımlarında arama yaptığınızı takip etmeniz gerekiyor. İlk başta bu, dizinin tamamı demektir.
low = 0
high = len(list) — 1
Her seferinde, ortadaki elemanı kontrol edersiniz.
mid = (low + high) / 2
guess = list[mid]Tahmininiz düşükse, düşük indeksi ona göre güncellersiniz,
if guess < item:
low = mid + 1
Tahmininiz yüksekse, yüksek indeksi tekrar hesaplarsınız. Kodun tamamına bakacak olursak,
Orta indeksi bul, eğer o indeksteki değer aradığımız değer ise onun pozisyonunu dön, değilse ona göre yeni üst ve alt pozisyonları tekrar hesapla.
Çalışmasına bakacak olursak,
Çalışma Zamanı
Algoritma hakkında ne zaman konuşsak, çalışma zamanından bahsederiz. İkili arama algoritmasını kullanarak, ne kadar zaman kazanabiliriz? İlk ilkel aramaya bakacak olursak, 100 elemanlık bir listede, 100 tahmin yapmamız gerekeceği anlamına gelir. 4 milyar elemanlı bir listede, 4 milyar tahmin demektir. Maksimum tahmin sayısı, listenin boyutuyla aynı olur. Buna lineer zamanlı çalışma denir.
İkili aramada bu farklıdır. Listede 100 eleman varsa, en fazla 7 tahminde bulunur. 4 milyar eleman olsaydı, en fazla 32 tahminde bulacaktık. İkili arama algoritması logaritmik zamanda çalışır. Karşılaştırmasına bakacak olursak,
Big-O Notasyonu
Big-O notasyonu, algoritmanın ne kadar hızlı olduğunu söyler. Big-O notasyonu, operasyonların sayısını karşılaştırmanızı sağlar. Algoritmaların ne hızla büyüdüğünü söyler. İkili arama n elemanlı bir liste üzerinde logn operasyona ihtiyaç duyar, bu da onun çalışma zamanını O(logn) yapar. Genel olarak, Big-O notasyonu şöyle yazılır.
Farklı Big-O Çalışma Zamanlarını Görselleştirme
16 kutudan oluşan bir grid çizmek istiyorsunuz.
Algoritma 1
Bunu yapmanın bir yolu, her seferinde 1 kutu olacak şekilde çizmektir. Big-O notasyonunun operasyon sayısını hesapladığı unutmayın. Her seferinde bir kutu çizmek bir operasyon demektir.
16 adımda 16 kutu çizeriz. Çalışma zamanı ne olur? Tabii ki, O(n)
Algoritma 2
Bunun yerine, kağıdı katladığımızı düşünelim.
Bu durumda, kağıdı katlamak bir operasyon olur. Tekrar tekrar katlarsak, sonuç olarak şunu elde ederiz.
Tekrar kağıdı açarsak, 16 kutuyu 4 operasyon ile yapmış olduk.
Bunun çalışma zamanı ise O(logn) olur.
Big-O notasyonu en kötü senaryoda çalışma zamanını ölçer. A ile başlayan bir kelimeyi sözlükte ararken, ilk bir kaç denemede onu bulmanız, Big-O notasyonunun değerini değiştirmez. Bu bir güvencedir, algoritmanız hiçbir zaman Big-O çalışma zamanından daha kötü çalışmayacağı anlamına gelir.
Bazı Yaygın Big-O Çalışma Zamanları
- O(logn): Logaritmik zaman. Örnek: İkili arama.
- O(n): Lineer zaman. Örnek: İlkel arama.
- O(n*logn): En hızlı sıralama algoritması. Örnek: hızlı arama(quicksort).
- O(n ^ 2): Yavaş sıralama algoritması. Örnek: seçmeli sıralama(selection sort) algoritması.
- O(n!), n faktoriyel: Çok yavaş bir algoritma. Örnek: gezgin satıcı problemi(traveling salesperson)
Bu algoritmaların zamana göre grafiklerine bakacak olursak,
Sonuç olarak, algoritmaların hızı saniyeler ile ölçülmez, operasyon sayılarının büyümesine göre ölçülür.
Gezgin Satıcı Problemi(The Traveling Salesperson)
Az önce bu algoritmadan bahsederken, nasıl olur da bir algoritmanın çalışma zamanı O(n!) yani n faktoriyel olabileceğini şaşırmışsınızdır. Bu bilgisayar biliminde meşhur bir problemdir. Onun büyüme grafiğinin korkunç olduğu için birçok akıllı insan, bu algoritmanın iyileştirilemeyeceğini söylerler. Bunun adı gezgin satıcı problemidir.
Bir satıcının gideceği 5 şehir olsun.
Bu satıcı, bu 5 şehire de uğramak ister ama en kısa mesafeyi baz alarak. Bunun bir yolu, seyahat edeceği şehirlerin farklı olarak tüm gezme ihtimallerini hesaplamak olur.
Toplam mesafeyi hesaplar ve en az olan mesafeyi seçer. 5 şehir için 120 ihtimal demektir, yani 5!. Eğer 6 şehir olsaydı, 720 operasyon demek olacaktı.
Genel olarak, n şehir için n! (n faktoriyel) operasyon demek oluyor. Çalışma zamanı O(n!) oluyor, yani faktoriyel zamanlı bir algoritma. 100 şehirden sonra hesaplaması imkansız sayılara ulaşıyoruz. Bu yüzden, kötü bir algoritmadır. Satıcının başka bir algoritma bulması lazım ama yok. Bu, bilgisayar biliminde çözülemeyen problemlerden biridir.
Bölüm 2: Seçmeli Sıralama Algoritması
Bellek Nasıl Çalışır?
Bir çekmeceli dolabı hayal edin.
Her çekmecede bir eleman bulunur. İki şey saklamak istediğinizde, iki çekmece istersiniz.
İki şeyinizi de, bu çekmecelerde saklarsınız.
Basit olarak bilgisayar belleğinin çalışma prensibi böyledir. Bilgisayarınız kocaman bir çekmece kümesidir ve her çekmecenin bir adresi vardır.
fe0ffeeb, bellekteki bir boşluğun adresidir.
Ne zaman bellekte bir şey saklamak istesek, bilgisayardan boşluk için biraz alan isteriz. Bilgisayar ise bize boşluğun adresini döner ve istediğimiz şeyleri saklarız. Eğer birden çok şey saklamak istiyorsak, bunun iki yolu vardır: diziler veya listeler. Bu ikisi arasındaki farklılıkları bilmek önemlidir.
Diziler ve Bağlı Listeler
Bazen, elemanların listesinin bellekte saklamak istersin. Yapılması gerekenleri tuttuğunuz bir uygulama yazdığınızı düşünün. Dizi mi kullanmalısınız, yoksa bağlı liste mi? Önce dizi kullandığımızı düşünelim. Dizide bütün elemanlar birbirine bitişik olarak yer alırlar.
Yeni bir tane görev eklemek istediğinizde, bir sonraki boşluğun başkası tarafından kullandığını görebilirsiniz.
Bir arkadaşınızla sinemaya gittiğinizi ve başka bir arkadaşınızın sonradan size katılmak istediğini ama onun için yer kalmadığı gibi bir olaya benzer. Bunun sonucunda bilgisayardan, yeni görevinin de sığdığı yeni bir bellek kümesi istersin. Sonra da, bütün görevlerini buraya taşırsın.
Diğer bir arkadaşın daha gelirse ve ona da yer kalmazsa, bu işlemleri ikinci defa tekrarlamak zorunda kalırsınız. Çok zahmetli bir iş. Bunu düzeltmenin bir yolu bazı koltukların önceden tutulması olabilir. Yapacağız görev 3 olsa bile, bilgisayardan 10 tane boşluk isteyebilirsiniz. 10 tane göreve kadar sorunsuz bir şekilde ekleyebilirsiniz. Bu, iyi bir geçici çözüm olsa bile, bazı olumsuzlukları vardır:
- İstediğiniz ekstra boşluklara ihtiyacınız olmayabilir ve belleği boşa harcamış olursunuz. Sizin kullanmadığınız yeri, başkası da kullanamaz.
- 10'dan fazla görev eklemek istediğinizde ise, yine diziyi taşıma işlemini yapmanız gerekir.
İyi bir geçici çözüm olsa bile mükemmel çözüm değildir. Bağlı listeler(linked lists) bu ekleme problemini çözerler.
Bağlı Listeler
Bağlı listeler ile elemanlarınız bellekte herhangi bir yerde olabilir.
Her bir eleman kendisinden sonra gelecek olan elemanın adresini tutar. Rastgele bellek adresleri birbirine bağlanmış olur.
Hazine avcılığı gibidir. İlk adrese gidersin ve o, sana der, “bir sonraki elemanı 123 no’lu adreste bulacaksın.” 123 no’lu adrese gidersin o da sana başka bir adres söyler ve böyle devam eder. Bağlı listeye yeni bir eleman eklemek çok kolaydır, bellekte bir yere istediğin elemanı koy ve en son elemana bunun adresini ver.
Bağlı listelerle, elemanlarınızı taşımak zorunda kalmazsınız. Bağlı listeler ekleme konusunda bu kadar iyilerse, o zaman diziler hangi konularda iyidir?
Diziler
Top-10 listede yer alan bazı web siteleri, daha fazla sayfa görüntülenmesi için kötü bir yol kullanırlar. Haber listesini tek sayfada gösterme yerine, listenin her elemanını ayrı sayfaya koyar ve İleri tıklatarak bir sonraki elemana geçmesini sağlar. Bağlı listelerin de benzer bir problemi vardır. Bağlı listedeki son elemanı okumak istediğinizde, direk okuyamazsınız. Önce birinci elemanı okursunuz, onun üzerinden ikinci elemana ve öyle devam ederek son elemana kadar ilerlersiniz. Bağlı listeler ile elemanların hepsini tek seferde okuyamazsınız.
Diziler farklıdır. Dizideki her elemanın adresini biliriz. Örneğin, diziniz 5 eleman içeriyorsa, birinci elemanın adresinin 00 ile başladığını bilirsiniz. Diğerlerinin adresleri ise 1 artırılmış olarak bulabilirsiniz.
Diziler, değerlerini rastgele okuma konusunda çok iyidir. Dizinin birinci elemanına 0. indeksle, ikinci elemanına 1. indeksle vb. erişebiliriz.
Örneğin;
Dizilerin pozisyonu 0. indeksten başlar. Programcılığa yeni başlayanlar bunu ilk başlarda garipser ama zamanla alışırlar. Hemen hemen bütün programlama dilleri bu yöntemi kullanır.
Diziler ve listelerin yaygın operasyonlarının çalışma zamanlarına bakacak olursak,
Listenin Ortasına Ekleme Yapmak
Yapılacaklar listeni daha çok bir takvim gibi yönetmek istediğinizi düşünün. Önceki halinde, yeni eklenecek şeyleri listenin sonuna ekliyordunuz.
Şimdi ise, yapılması gerekenlere göre listeye eklemek istiyorsunuz.
Listeler ile araya bir eleman eklemek daha kolaydır.
Diziler içinse, eklenecek pozisyon sonrasındaki bütün elemanları kaydırmanız gerekir.
Eğer bellekte yer kalmadıysa, bu seferde tüm diziyi başka bir pozisyona taşımanız gerekir. Listeler, araya bir eleman konusunda daha iyidir.
Silmeler
Ya silme işlemi yapmak isteseydik? Yine, listeler bu konuda daha iyidir. Sadece bir önceki elemanın işaret ettiği adresin değiştirilmesi yeterdir. Dizilerde ise, bir elemanı sildiğiniz zaman, diğer elemanları tekrar hizalamanız gerekir.
Çalışma zamanlarına bakacak olursak,
Bu noktada şunu demek gerekir, listede silme ve ekleme işlemleri, sadece elemanlara direk olarak erişilirse O(1) zamanında icra olur.
Diziler veya listelerden hangisi daha çok kullanılır? Açıkça, bu duruma göre değişen bir şeydir ama rastgele erişime izin verdiği için dizilerin kullanımını daha çok görürüz. Diziler ve listeler, birleşerek veri yapılarının uygulanmasında kullanılırlar.
Seçmeli Sıralama Algoritması
Önceki anlatılanlardan sonra şimdi, ikinci algoritmamızı incelemeye başlayalım.
Bilgisayarınızda bazı müziklerin olduğunu düşünün. Her artist için, çalma sayısı tutulmuş olsun.
En çok dinlenenden en az dinlenene doğru bunları sıralamak isteyelim, ki böylece favori artistlerimizi bulabileceğiz.
Bunu yapmanın bir yolu, liste üzerinde dönüp, en çok dinlenen artisti bulmak olur. Sonra bunu yeni listeye ekleriz.
Sonra, bir sonraki en çok dinlenen artisti bulur ve yeni listeye ekleriz.
Buna devam edersek, sıralı listeyi bulmuş oluruz.
Bilgisayar bilimi şapkamızı takalım ve bunun çalışma zamanını hesaplayalım. O(n) zamanının, listedeki her elemana bir kere dokunmak olduğunu unutmayalım. Örneğin, listedeki her artisti bir kere taramak demek listenin boyutu kadar işlem yapmak demektir.
En çok dinlenen artisti bulmak, listedeki her elemanı kontrol etmek demektir. Bu O(n) zaman alır. Bu işlemi de listenin sonuna kadar yapmak demek, n işlem yapmak demektir.
Bu işlemlerin çarpılmasıyla, O(n * n) yani O(n ^ 2) çalışma zamanı olur.
Her Seferinde Daha Az Eleman Kontrol Etmiyor muyuz?
Belki dikkat etmişsinizdir, her seferinde kontrol edilecek eleman sayısı azalıyor. En sonunda, sadece 1 elemanı kontrol ediyoruz. Çalışma zamanı hala nasıl O(n^2) oluyor o zaman?
Aslında bu konuda haklısınız, her seferinde n eleman kontrolü yapmayız. Eleman sayısı gittikçe şöyle azalır: n-1, n-2, n-3 … , 1. Ortalama olarak 1/2 * n eleman kontrol etmiş oluruz. Çalışma zamanı O(n * 1/2 * n) olur. Big-O notasyonunda 1/2 gibi sabitler ihmal edildiği için geriye O(n ^ 2) değeri kalır.
Seçmeli sıralama düzenli bir algoritmadır ama çok hızlı değildir. Hızlı Sıralama(Quicksort) daha hızlı bir algoritmadır ve O(nlogn) çalışma zamanına sahiptir.
Seçmeli sıralama algoritmasının koduna bakacak olursak, önce işimize lazım olacak olan dizideki en küçük elemanı bulan fonksiyonu yazalım.
Şimdi seçmeli sıralama algoritmamızı yazabiliriz.
Bölüm 3: Özyinelemeler (Recursions)
Ninenizin gizemli bavulunu açmaya çalıştığınızı düşünün.
Nineniz size, bavulun anahtarının diğer kutulardan birinde olduğunu söyledi.
Bu kutu da, diğer başka kutuları içeriyor. Anahtar kutunun içinde bir yerlerde. Anahtarı aramak için kullanacağın algoritma ne olurdu?
Bir yaklaşım şöyle olur:
- Bakmak için kutulardan bir yığın yap.
- Bir tanesini al ve içine bak.
- Eğer bir kutu bulduysan, sonra bakmak için tekrar yığına koy.
- Anahtarı bulduysan, iş tamamdır.
- Tekrarla.
Bu da alternatif bir yaklaşım.
- Kutuya bak.
- Kutu bulursan, adım 1'e dön.
- Anahtar bulursan, iş tamamdır.
Hangisi daha kolay geldi? İlk yaklaşım, while döngüsü kullanır. Bunun sözde kodunu(pseudocode, kodun anlaşılması için konuşma diline yakın yazılan kod) yazarsak,
İkinci yol ise özyinelemeleri kullanır. Özyineleme, fonksiyonun kendi kendisini çağırmasıdır. Bunun sözde koduna bakarsak,
Her iki yöntemde aynı işi yapıyor ama ikinci yöntem çok daha açık. Özyinelemeler, çözümü daha anlaşılır yaptığı zaman tercih edilir. Özyinelemeler performansı döngülere göre daha kötü diyebiliriz ama bununla ilgili şöyle söylenir: “Döngüler belki program için performans artışı sağlayabilir ama özyinelemeler, programcılar için performans artışı sağlarlar. Duruma göre hangisi önemliyse, onu seçin.”
Yineleme Durumu ve Temel Durumu
Özyinelemeli fonksiyonlar, kendi kendilerini çağırdıkları için dikkat edilmediği takdirde, sonsuz döngüye girmek çok olasıdır.
Geriye doğru sayan bir fonksiyon yazmak istiyorsunuz,
Bu kodu derleyip, çalıştırırsak o da ne, fonksiyon sürekli çalışıyor!
> 3…2…1…0…-1…-2…
Özyinelemeli fonksiyon yazdığınız zaman, ne zaman duracağını söylemek zorundasınız. Bunun için özyineleme durumunun yanında, temel durumu da belirlemelisiniz. Bu sayede sonsuz döngüye girmez.
Şimdi fonksiyon beklendiği gibi çalışır.
Yığın (Stack)
Çağrı yığını (call stack) kavramı programlamada önemli bir kavramdır.
Daha önce diziler ve listeler ile yapılacakların listesini tuttuğumuzu hatırlayalım. Listede istediğin yere bir şey ekleyebiliyordun ve istediğin yerden silme yapabiliyordun. Yığında ise sadece en üste ekleme yapabiliyorsun ve sadece en üstten okuma yapabiliyorsun. Yapılacaklar listen sadece iki aksiyona izin verir: push(ekle) ve pop(oku ve çıkar).
Aksiyonları görecek olursak,
Bu veri yapısına yığın deriz. Bunca zamandır, farkında olmadan yığın veri yapısını kullandınız.
Çağrı Yığını (Call Stack)
Bilgisayarınızın kullandığı iç yığına, çağrı yığını denir. Basit bir örnekle bakacak olursak,
Bu fonksiyon sizi selamlıyor ve ayrıca 2 fonksiyon çağırıyor. Diğer fonksiyonlar ise şunlar
print fonksiyonu da Python’da bir fonksiyondur. Şimdilik işleri basitleştirmek adına onu görmezden geleceğiz. greet(“maggie”) fonksiyonunu çağırdığımızda neler olacak bir bakalım.
İlk önce, fonksiyon çağrımı için bilgisayarınız bir kutu bellek ayırması yapar.
Sonra, name değişkenine “maggie” set eder. Bunun bellekte saklanması gerekir.
Fonksiyon çağrımı yaptığın her zaman, bilgisayarınız bütün değişken değerlerini bellekte saklamaya devam eder. Sonra greet2(“maggie”) fonksiyonunu çağırır.
Bilgisayarınız, bu kutular için yığın kullanır. İkinci kutu, birinci kutunun üstüne yerleştirilir. Daha sonra bu fonksiyonlardan dönmeye başlanır ve fonksiyonlar tek tek pop edilmeye başlanır.
Bir fonksiyondan diğer fonksiyon çağrıldığı zaman, çağıran fonksiyon kısmen tamamlanmış bir durumda, duraklatılmış olur. Tüm değişkenlerin değerleri, hala bellekte saklanmaktadır. Sonra, bye fonksiyonu çağrılır.
Bu fonksiyon için bir kutu, yığının en tepesine eklenir. Sonra da o fonksiyondan da dönüş sağlanır.
En sonunda, tekrar greet fonksiyonuna döneriz. Yapılacak bir şey kalmadığında, greet fonksiyonundan da döneriz. Birçok fonksiyon için değişkenleri saklayan bu yığına, çağrı yığını denir.
Özyinelemeler için Çağrı Yığını
Özyinelemeli fonksiyonlar da yığın kullanır. Faktoriyel hesaplama için bunun nasıl kullanıldığna bakalım. Bir sayının faktoriyelini hesaplamak, kendinden başlayarak 1'e kadar azaltarak çarpmak demektir. Örneğin, 5 sayısının faktoriyeli 5*4*3*2*1 = 120 olur.
fact(3) olarak çağırdığımız zaman, yığının nasıl değiştiğine satır satır bakalım.
