Grokking Algorithms — 2

Hızlı Sıralama (Quicksort)

Böl ve yönet, özyinelemeli teknik olarak da bir bilinen bu teknik birçok problemin çözümünde kullanılır.

Yazının birinci bölümünü buradan okuyabilirsiniz.

Bu bölüm, algoritmaların içine gerçekten girdiğimiz yer olacak. Ne de olsa, bir algoritma, yalnızca bir problem türünü çözebiliyorsa, çok da kullanışlı değildir. Böl ve yönet, problemleri çözme konusunda size yeni bir bakış açısı kazandırır. Yeni bir problemle karşı karşıya geldiğinde, “Acaba ben bunu böl ve yönet ile çözebilir miyim?” diye kendi kendine sorman gerekir.

Hızlı sıralama, bir sıralama algoritmasıdır ve daha önce gördüğümüz, seçmeli sıralama(selection sort) algoritmasından çok daha hızlıdır.

Böl ve Yönet

Bunu görsel bir örnekle açıklamaya çalışalım.

Çiftçiyiz ve şöyle bir tarlamız var olsun.

Bu tarlayı, kare tarlalara bölmek istiyoruz ama mümkün olduğunca büyük olacak şekilde.

Şunların hiçbiri çözüm olmaz.

En büyük olacak şekilde bir tarlayı nasıl ayırabiliriz? Bunun için böl ve yönet stratejisini uygulayabiliriz. Böl ve yönet algoritmaları, özyinelemeli algoritmalardır. Bunların iki adımı olur:

1. Temel durumu(base case) belirle. Bu, mümkün olan en basit durum olmalıdır.
2. Problemi böl ve azalt, ta ki temel durumu yakalayıncaya kadar.

Tarla problemi için bunu kullanacak olursak, en büyük karenin boyutu ne olurdu?

İlk önce, temel durumu belirleyelim. Bir kenarı diğerinin katıysa, bu en kolay durum olur.

25 x 50 metrelik bir tarla olsaydı, 25 x 25 metrelik kare tarlalar işimizi görürdü.

Şimdi de algoritmanın özyineleme durumuna bakalım. Burada böl ve yönet işin içine girer. Böl ve yönet tekniğine göre, her bir yineleme çağrısında, problemi azaltmamız gerekir. Problemi nasıl azaltabiliriz? Kullanabileceğimiz en büyük kutulara ayıralım.

640 x 640 kutulara sığdırabiliriz ama bölünecek başka alanlar kaldı. İşte tam burada aklımıza şu soru gelir, kalan kısım içinde aynı bölme yöntemini uygulayabilir miyiz?

Tarlamızın başlangıçtaki büyüklüğü 1680 x 640 idi. Sonra problemi azalttık ve şimdi elimize bölünecek, 640 x 400 metrelik bir tarlamız var.

Aynı algoritmayı uygulamaya devam edersek, 400 x 400 metrelik parçalara ayırırız.

Geriye, ayrılacak 400 x 240 metrelik tarlamız kalır.

Sonra, 240 x 160 metrelik parça kalır.

Sonra, daha küçük parçalar için araştırmaya devam ederiz.

En sonunda, son kalan 80 x 80 metrelik parçamıza, yani temel durumumuza ulaştık. Son kalan parçayı da ayırmaya kalkacak olursak, geriye bir şey kalmaz.

Şimdi, orjinal tarlamıza bakacak olursak, sığdırabileceğimiz en büyük boyutlu kare, 80 x 80 metrelik kareler olmuş oldu.

Böl ve yönetin çalışmasına tekrar bakacak olursak,

1. Temel durum olarak en basit durumu bul.
2. Temel duruma ulaşana kadar, problemi indirgeme yolunu bul.

Böl ve yönet, sadece bir probleme uygulayabileceğin basit bir algoritma değildir. Problem hakkında bir düşünme yöntemidir. Bir örneğe daha bakacak olursak,

Bir dizi sayımız olduğunu düşünelim.

Tüm sayıları toplayıp, sonucu dönmek istiyoruz. Bunu döngü ile yapmak çok kolay olur.

Toplam işini özyinelemeli olarak nasıl yapabiliriz?

Adım 1: Temel durumu keşfet. Alabileceğimiz en basit dizi ne olurdu? Eğer 0 veya 1 elemanlı bir dizi alacak olsaydık, toplamını bulmak çok kolay olurdu.

Temel durumumuz bu olsun.

Adım 2: Her yineleme çağrısında boş diziye doğru yaklaşmamız gerekiyor. Bunu nasıl yapabiliriz?

Üsttekini hesaplamak ile alttakini hesaplamak aynı olur.

İkinci yöntemde, daha az sayıdaki diziyi fonksiyon tekrar parametre olarak veriyoruz. İşte bu, problemin boyutunun azaltılmasıdır.

sum fonksiyonumuz, şöyle çalışır.

Aksiyon halinde bakalım.

Fonksiyonel Programlama’nın Zirvesi

“Döngüler(loops) ile kolaylıkla yapabiliyorsam, neden yinelemeli bir şekilde yapayım?” diye düşünüyor olabilirsiniz. Haskell gibi bir fonksiyonel programlama dilinde, döngüler yoktur. Bu yüzden, mecburen yinelemeli olarak bu fonksiyonu yazmak zorundasınız. Yinelemenin mantığını iyi anlarsanız, fonksiyonel dilleri öğrenmesi çok kolaydır. Örneğin, Haskell dilinde sum fonksiyonunu şöyle yazabiliriz:

Fonksiyon için iki tane tanım yaptığınıza dikkat edin. İlki temel durumu, ikincisi ise yineleme durumunu gösteriyor. if koşullu ifadesi ile de aynı fonksiyonu şöyle yazabiliriz.

Ama ilk çözümün okunması daha kolaydır. Haskell her türlü yineleme işlerini yoğun olarak kullandığı için, bunu kolaylaştıracak her türlü şeyi kullanır.

Hızlı Sıralama

Hızlı sıralama, bir sıralama algoritmasıdır. Seçmeli sıralama algoritmasından çok daha hızlıdır ve gerçek hayatta sıklıkla kullanılır. Örneğin, standart C dili kütüphanesi qsort adında bir fonksiyon, bu iş için vardır. Hızlı sıralama da Böl ve Yönet tekniğini kullanır.

Bir diziyi sıralamak için hızlı sıralama kullanalım. Sıralama algoritmasının başa çıkabileceği en basit dizi nedir? Bazı dizilerin sıralanma ihtiyacı yoktur.

Boş diziler ve tek elemanlı diziler, burada temel durumlardır. Bu dizileri aynı şekilde dönebiliriz, sıralanmasına ihtiyacı yoktur.

Daha büyük dizilere bakacak olursak, iki elemanlı bir dizinin de sıralanması çok kolaydır.

3 elemanlı bir dizi olsaydı?

Böl ve Yönet tekniğini kullandığımızı unutmayın. Temel durumu buluncaya kadar, bu diziyi bölmek isteriz. Hızlı sıralama böyle çalışır. Diziden bir eleman seç, buna pivot deriz.

İyi pivot seçmekle ilgili daha sonra bahsedeceğiz. Şimdilik, ilk elemanı pivot olarak seçelim.

Şimdi de, pivottan daha küçük elemanlar ile daha büyük elemanları bulalım.

Buna, bölümleme(partitioning) deriz. Şimdi, şunlarımız olur.

• Pivottan küçük elemanlardan oluşan bir alt-dizimiz,
• Pivot,
• Pivottan büyük elemanlardan oluşan bir alt-dizimiz.

İki tane alt-dizi de sıralanmamıştır. Sadece bölümlere ayrılmıştır. Eğer sıralanmış olsaydı, bütün diziyi sıralamak çok kolay olurdu.

Eğer alt-diziler sıralanmış olsaydı, tüm diziyi birleştirmek, sol-dizi + pivot + sağ-dizi gibi basit bir işlem olacaktı.

Peki, alt-dizileri nasıl sıralarız? Hızlı sıralamanın temel durumu, iki veya daha az elemanı nasıl sıralayabileceğini biliyor. Alt-diziler ile tekrar hızlı sıralama fonksiyonumuzu çağırıp, onların sonuçlarını birleştirirsek, sıralanmış dizimizi elde edebiliriz.

quicksort([15, 10]) + [33] + quicksort([])
> [10, 15, 33]

Bu, her türlü pivotla işe yarar. 15 sayısını pivot olarak seçtiğimizi düşünelim.

Her iki alt-dizi de tek bir elemanı olduğundan, bunları nasıl sıralayacağımızı biliyoruz.

Dört elemanlı bir dizi olsaydı?

33 sayısını pivot olarak seçelim.

Sol-dizinin 3 elemanı olur. 3 elemanlı diziyi nasıl sıralayacağımızı biliyoruz, quicksort fonksiyonunu yinelemeli olarak çağırırız.

4 elemanlı bir diziyi sıralayabiliyorsak, 5 elemanlı bir diziyi de sıralayabiliriz. 5 elemanlı bir dizimiz olsun.

Diziyi bölümlemenin bütün adımlarına bakacak olursak, hangi sayıyı pivot olarak seçtiğimize göre şöyle olur.

Hangi pivotu seçtiğiniz fark etmez, 2 alt-dizi için hızlı sıralama algoritmasını özyinelemeli olarak çağırırız.

3 sayısını seçtiğimizi düşünelim. quicksort fonksiyonunu alt-diziler için çağırırız.

5 sayısını seçsek bile, algoritma aynı şekilde çalışır.

quicksort fonksiyonunun, Python dilindeki koduna bakacak olursak,

Revize Edilmiş Big-O Notasyonu

Hızlı sıralamanın hızı seçtiğiniz pivota bağlıdır. Daha önce Big-O çalışma zamanlarından bahsetmiştik.

Bu grafikteki örnek zamanlar, yaklaşık olarak saniyede 10 operasyona göre hazırlanmıştır. O yüzden, kesin değildir. Genel yapıyı görebilmeniz içindir. Gerçekte, bilgisayarlar saniyede 10 işlemden çok daha fazlasını yaparlar.

Birleştirmeli sıralama (Merge Sort) adında başka bir sıralama algoritması daha var, onun çalışma zamanı da O(n*logn)’dir. Hızlı sıralama algoritması en kötü senaryoda, O(n ^ 2) sürmektedir. Ortalama durumda, O(n*logn) sürer.

Madem, birleştirmeli sıralama her zaman O(n*logn) sürüyor, neden onu kullanmıyoruz?

Birleştirmeli(Merge) Sıralama ve Hızlı(Quick) Sıralama

Listedeki her elemanı yazdıran basit bir fonksiyonumuz olsun.

Bu fonksiyon, O(n) zamanda çalışır. Bu fonksiyonu her adımda 1 saniye uyutacak şekilde değiştirelim.

Beş elemanlı bir listeyi parametre olarak verirsek, bu fonksiyonlar şöyle çalışır.

Her iki fonksiyon da bir kere çalışır, o zaman her ikisi de O(n) zamanlıdır. Pratikte hangisinin daha hızlı çalıştığını düşünürüz? Açıkça görülüyor ki, print_items çok daha hızlı çalışır. Big-O notasyonunu O(n) olarak yazdığımızda, burada şunu kastederiz.

c değeri, algoritmamızın aldığı sabit bir süredir. Önceki örneğimizden, print_items fonksiyonu için 10milisaniye * n, print_items2 fonksiyonu için 1saniye * n.

Genelde bu sabit ihmal edilir. Eğer algoritmaların farklı Big-O zamanları var ise, bu sabitin bir önemi olmaz. İkili arama ile basit arama yöntemini kıyaslayalım. İki algoritmanın da şu sabitleri olduğunu düşünelim.

Basit aramanın 10milisaniye sabiti var, ikili aramanın ise 1saniye sabiti var. Buna bakarak, basit aramanın ikili aramadan daha hızlı olduğunu söyleyebilir miyiz? 4 milyar eleman üzerinde arama yaptığımızı düşünelim.

Görüldüğü gibi, ikili arama hâlâ çok daha hızlıdır. Yani, bu sabit çok bir şey fark ettirmiyor.

Ama bazen, bu sabit fark yaratabilir. Hızlı sıralama ile birleştirmeli sıralama arasında bu sabit bir fark yaratıyor. İkisi de O(n*logn) zamanlı olmasına rağmen, hızlı sıralama algoritmasının daha küçük c sabiti vardır. Hızlı sıralama pratikte daha hızlıdır, çünkü ortalama durumu yakalaması, en kötü durumu yakalamasından daha olasıdır.

Ortalama Durum ve En Kötü Durum

Hızlı sıralamanın performansı seçtiğiniz pivota çok bağlıdır. Her zaman ilk elemanı pivot olarak seçtiğinizi ve sıralanmış bir diziyi tekrar sıralamaya çalıştığımızı düşünelim. Hızlı sıralama, elemanlar sıralanmış mı diye kontrol etmez ve yine de sıralamaya çalışır.

Alt-dizilerin nasıl ayrıştırıldığına bakacak olursak, bir tanesinin her zaman boş olduğunu görürüz. Çağrı yığını(call stack) çok uzun olur. Şimdi de ortadaki elemanı pivot olarak seçtiğimizi düşünelim.

Her seferinde diziyi ikiye bölmüş olduk. Özyineleme çağrıları daha azalmış oldu.

Yukarıdaki ilk örnek, en kötü durum senaryosudur ve ikinci örnek de en iyi durum senaryosudur. En kötü durum senaryosunda, yığın boyutu O(n) olur ve en iyi durum senaryosunda ise O(logn) olur.

Şimdi de yığındaki ilk seviyeye bakalım. Pivot için bir eleman seç ve geri kalan elemanları alt-dizilere böl. Dizideki sekiz elemana da dokunmak zorundasınızdır. İlk operasyon O(n) zaman alır. Aslında, yığının her bir seviyesinde yine O(n) elemana dokunmak zorunda kalırsınız.

Farklı bir pivot seçip, alt-dizileri farklı şekillerde oluştursak bile, yine de her seferinde O(n) elemana dokunuruz.

Kısaca, her seviyenin tamamlanması O(n) zaman alır.

Yığın O(logn) seviyede gerçekleşir ve her seviyede O(n) işlem yapılacağından, algoritmanın tamamı O(n) * O(logn) = O(n*logn) sürer. Bu, en iyi durum senaryosudur.

En kötü durumda ise yığın, O(n) seviye olur. Bu durumda algoritma O(n) * O(n) = O(n ^ 2) zamanlı çalışır.

Hızlı sıralama algoritması için en iyi durum, aynı zamanda ortalama durum demektir. Dizide her zaman rastgele olarak pivotu seçerseniz, hızlı sıralama yine de O(n*logn) ortalama zamanında çalışır. Hızlı sıralama, en hızlı sıralama algoritmalarından biridir ve Böl ve Yönet tekniğinin iyi bir örneğidir.

Bölüm 5: Hash Tabloları

Markette çalıştığımızı düşünelim. Müşteri bir ürün aldığında, rehberden fiyatına bakarız. Rehber, alfabetik sıralanmamışsa, elma kelimesini rehber içinde aramamız uzunca bir zaman alabilir. Bunun gerçekleşmesi, daha önce anlattığımız gibi O(n) zamanda olur. Eğer sıralanmış ise ikili arama ile O(logn) zamanında bunu bulabiliriz.

İkili arama çok hızlı olduğunu biliyoruz. Rehberdeki liste sıralı bile olsa, bir şeyleri araştırmak sorun olabilir. Siz rehberden araştırırken, müşterinin gözlerini size dikmesi, sizi kızdırabilir. İhtiyacınız olan şey, bütün ürün isimlerinin ve fiyatlarını ezberlemiş bir arkadaş. Ona sorarsınız ve o da hemencecik size cevap verir.

Arkadaşınız Maggie size O(1) zamanında, istediğiniz ürünün fiyatını söyleyebilir. Maggie, ikili aramadan bile daha hızlıdır.

Veri yapıları şapkamızı takarak düşünelim. Diziler ve listeler veri yapılarını daha önceden görmüştük. Bu rehberi, bir dizi olarak düşünebiliriz.

Dizinin her elemanında, iki şey olur: biri ürünün ismi ve diğeri ürünün fiyatı. Sıralayıp, ikili arama ile arasanız bile O(logn) zamanda çalışır. Sizin ihtiyacınız olan Maggie’nin bildiği gibi bir veri yapısıdır. Hash(özet de diyebiliriz ama yaygın diye hash olarak kullanacağım) fonksiyonları burada devreye girer.

Hash Fonksiyonları

String(karakter dizileri) olarak girdi alıp, sayı olarak çıktı veren bir fonksiyona, hash fonksiyonu deriz.

Teknik terminolojide, hash fonksiyonu, stringleri sayılara adresleme işini yapar. Basit gibi gözükse de, hash fonksiyonu olmayı sağlayan bazı gereksinimler vardır.

• Tutarlı olmalıdır. Her zaman, aynı string değeri için aynı sayıyı dönmelidir.
• Farklı kelimeleri farklı sayılara adreslemelidir. Her zaman 1 sayısını dönen bir fonksiyon, hash fonksiyon olamaz.

Hash fonksiyonları ile kendi Maggie arkadaşımızı yapabiliriz.

Boş bir dizi ile başlayalım.

Elmanın(apple) fiyatını bu diziye ekleyelim. Hash fonksiyonunu elma ile beslemiş oluruz.

Hash fonksiyonu sonucu, 3 olsun. Elmanın fiyatını 3 no’lu indekste saklayalım.

Süt(milk) ekleyelim. Hash fonksiyonunu süt ile besleyelim.

Hash fonksiyonu 0 desin. Sütün fiyatını da, 0 no’lu indekste saklayalım.

Böyle devam edersek, tüm diziyi fiyatlarla doldurmuş oluruz.

Şimdi, “Avokadonun fiyatı nedir?” diye soracak olursak, dizi üzerinden gezinmeye gerek kalmaz, hash fonksiyonu bize hemen sonucu döner.

Size fiyat bilgisinin 4 no’lu indekste olduğunu söyler.

Hash fonksiyonu fiyatın yer aldığı yeri tam olarak söyler, bu yüzden hepsini taramanız gerekmez. Bu, şu sebeplerden dolayı işe yarar.

• Hash fonksiyonu tutarlı bir şekilde, aynı ismi aynı indekse adresler.
• Hash fonksiyonu, farklı stringleri farklı indekslere adresler.
• Hash fonksiyonu, dizinin ne kadar büyük olduğunu bilir ve ona göre, geçerli bir indeks döner.

Hash fonksiyonu ve diziyi beraber kullanarak, hash tablo denilen veri yapılarını tasarlamış olduk. Diziler ve listeler, belleği direk olarak kullanırlardı ama hash tabloları, daha akıllıdır. Saklanan elemanların nerede olduğunu bulabilmek için, hash fonksiyonunu akıllıca kullanırlar.

Hash tabloları, ayrıca hash haritaları(maps), haritalar, sözlükler(dictionaries) veya ilişkisel diziler olarak da bilinirler. Hash tabloları hızlıdır. Diziden bir elemanı hemencecik alırsınız. Hash tabloları da buna benzer hızda çalışır.

Daha önce, büyük ihtimalle kendi hash tablolarınızı hiç yapmadınız. Hemen hemen tüm dillerde, hash tablo uygulaması vardır. Python dilinde hash tablolara, sözlükler denir. dict fonksiyonu ile boş bir hash tablo oluşturabilirsiniz.

>>> book = dict() # Boş bir hash tablo oluşturur

Tabloya, birkaç değer eklersek,

Avokadonun fiyatı nedir diye merak edersek,

>>> print book[“avocado”]
1.49

Hash tablonun, anahtarları ve değerleri olur. book hash tablomuzda, ürün isimleri anahtarlar, ürün fiyatları ise değerler oluyor.

Hash Tablo Kullanım Senaryoları

Hash tabloları her yerde kullanılır.

Telefonlarda: Telefonlarımızda her bir isme karşılık bir numara denk gelir.

Bu şekilde bir telefon rehberi yapmak istiyoruz. Şu işlevselliğe ihtiyacımız var:

• Bir kişiyle ilişkili olarak, kişinin ismi ve telefon numarası ekleriz.
• Kişinin ismini girip, sahip olduğu numarayı öğreniriz.

Hash tabloları için mükemmel bir kullanım senaryosu.

DNS Çözümlemede: Hash tabloları daha büyük bir ölçekte de kullanılır. Her gün uğradığımız websitelerini düşünelim, mesela http://adit.io. Bilgisayarımız, adit.io adresini IP adresine çevirmesi gerekir.

Uğradığımız her websitesi için isim adreslerinin IP adreslerine çevrilmesi gerekir.

Web adreslerinin IP adreslerine haritalanması, hash tablolarının kullanımı için güzel bir örnektir. Buna da DNS çözümlemesi denir.

Çoklu Kayıtların Önlenmesi

Oylama kabini çalıştırdığımızı düşünelim. Doğal olarak, her kişi sadece 1 kere oy kullanır. Daha önce oy kullanmadığından emin olmamız gerekir. Oy kullanacak kişinin adını öğreniriz ve daha önce oy kullanmış mı diye kontrol ederiz.

İsmi zaten listedeyse, onu dışarı atarız, izin vermeyiz.

Diğer türlü, listeye ekleriz ve oy kullanmasına izin veririz. Şimdi, çok fazla insanın oy kullanmaya geldiğini düşünelim. İnsan listesi uzadıkça uzar.

Yeni birinin geldiği her seferinde bu devasa listeyi tarar ve oy kullanıp kullanmayacaklarına bakarız. Bunun daha iyi bir yolu: hash kullanmaktır.

Önce, insanları takip edebileceğimiz bir hash oluşturalım.

>>> voted = {}

Oy kullanmaya biri gelirse, oy kullanmış mı diye kontrol edelim.

>>> value = voted.get(“tom”)

get fonksiyonu, “tom” kişisinin hash tablosunda değeri var mı diye kontrol eder. Diğer türlü, None döner.

Kodumuza bakacak olursak,

Birkaç test yapalım.

Eğer bunu bir listede tutacak olsaydık, bu fonksiyon daha sonra çok yavaş çalışmaya başlardı. Ancak, isimlerini hash tablosunda tutarsak, fonksiyon çok hızlı bir şekilde size geri dönüş yapar.

Hash Tablolarını Önbellek Olarak Kullanmak

Son bir kullanım senaryosu olarak, önbellekleri verebiliriz. Önbellekleme şöyle çalışır. facebook.com’u ziyaret ettiğimizi düşünelim.

1. Facebook sunucularına 1 istek yaparız.
2. Sunucu size göstereceği sayfayı hesaplar ve gösterir.
3. Bir sayfanız olur.

Örneğin, Facebook sunucuları, arkadaşlarınızın faaliyetlerini toplayabilir. Bunları toplayıp size göstermek birkaç saniye sürebilir. Bu birkaç saniye kullanıcıya uzun zaman gibi gelebilir. Facebook’u daha hızlı yapabilecek bir yol var mı?

Google’da sürekli şu aramaları yaparız, “Dünya, Mars’tan ne kadar uzaktır?”, “Ay ne kadar uzaktır?”, “Jüpiter ne kadar uzaktır?”. Sürekli sorulan bu sorular sonucu, bir süre sonra siz de sonuçları ezberlersiniz, Ay’ın uzaklığı 384.400 km’dir. Bunun için Google’da araştırma yapmak zorunda kalmazsınız, hatırlar ve cevabı bilirsiniz. Önbelleklemenin çalışma mekanizması bu şekildedir. Websiteler de bu verileri tekrar hesaplamaktansa, onları hatırlar ve kullanıcılara gösterir.

Facebook’ta oturum açtığınızda, bütün içeriğin size göre uyarlandığını görürsünüz. Oturum açmadığınız takdirde ise, oturum açma sayfasını görürsünüz. Herkes aynı oturum açma sayfasını görür. Oturum açma sayfası için o kadar çok istekte bulunulur ki, Facebook sunucuları her seferinde bunu hesaplamak yerine ezberler ve kullanıcıya bunu gösterir.

Buna önbellekleme(caching) denir. İki faydası vardır.

• Bir web sayfasını çok daha hızlı yüklersiniz.
• Siteler önbellekleme sayesinde daha az iş yapar.

Önbellekleme, bir şeyleri hızlandırmak için yaygın bir yöntemdir. Bütün büyük web siteler bu yöntemi kullanır ve bu veriler hash içinde önbelleklenir.

Facebook sadece, anasayfası değil, birçok sayfası önbelleğine alır. Bunun için, URL’den sayfa verisine doğru bir adresleme gerekir.

Bir web sayfaya sorgu yapıldığı zaman, sayfanın hash içinde olup olmadığı kontrol edilir. Kodu şöyle olur.

Sunucu, sayfa URL önbellekte yoksa o zaman hesaplaması gereken işleri yapar.

Çakışmalar(Collisions)

Birçok dilin kendi hash tablolarının olduğunu söylemiştik. Hash tablolarının tasarım detayına çok girmesek de, performansından söz edebiliriz. Hash tablolarının performansından söz etmek için, çakışmaların ne demek olduğunu anlamanız gerekir.

Daha önce, hash fonksiyonun farklı anahtarlar için her zaman farklı değerler ürettiğini söylemiştik, bu tam olarak doğru bir ifade değildi.

Gerçekte ise, bunu yapan bir hash fonksiyonu yazmak neredeyse imkansız. Basit bir örnek ele alalım. 26 elemanlı bir dizimiz olduğunu düşünelim.

Hash fonksiyonumuz ise gayet basit olsun. Fonksiyon, dizinin boşluklarına alfabetik olarak atama yapsın.

Buradaki problem şu olur. Apples(elma) A ile başladığı için ilk boşluğa atanır. Daha sonra, babanas(muz) B ile başladığı için ikinci boşluğa atanır.

İşler şimdilik yolunda ama Avokado da listeye eklenmek istenirse ne olur?

Apples(elma) zaten birinci boşluğu doldurmuştu, şimdi de Avokado geldi. İşte buna çakışma denir ve çakışmada, iki anahtar aynı boşluğa atanır. Bu bir problemdir ve bir şekilde çözülmesi gerekir. Çakışmalarla başa çıkmak için birçok yöntem vardır. En basit olanı, birden fazla anahtar olan boşlukta bir bağlı liste tutmak.

Bu durumda, B ile başlayan ürünlerin fiyatını öğrenmek istersek yine hızlı olur ama A ile başlayan ürünlerin fiyatını yavaş öğreniriz. Eğer bağlı listeniz küçükse, çok sorun çıkarmaz. Büyük bir marketi düşünün, A ile başlayan bir sürü ürün olur.

Tüm hash tablomuz sanki bağlı bir liste haline geldi. Bu hash tablomuzu çok yavaşlatır.

Burada alınacak iki ders var:

• Hash fonksiyonumuz çok önemlidir. Hash fonksiyonu mümkün olduğunca, tüm anahtarları boş alanlara atamalıdır.
• Bağlı liste çok uzun olursa, bu hash tablomuzu çok yavaşlatır. İyi bir hash fonksiyonu seçersek, bağlı liste o kadar uzun olmaz.

Performans

Ücretleri anlık olarak getiren bir sistem nasıl diye sorarak buralara gelmiştik. Hash tabloları çok hızlıdır.

Ortalama durumda, hash tabloları O(1) zaman alır. Bu sabit zaman demektir. Hemen demek değildir. Hash tabloları ne kadar büyük de olsa, aynı zamanda getirecek demektir. Basit aramanın, lineer zamanlı olduğunu söylemiştik.

İkili arama ise logaritmik zamanlıdır.

Hash tablo içinde bir şey aramaksa, sabit zamanlıdır.

Hash tablon 1 elemanlı da olsa, 1 milyar elemanlı da olsa, bir değer okumak için farketmeyeceği anlamına gelir.

En kötü durumda ise, hash tablo O(n), lineer zamanda çalışır. Bu çok yavaş olacak demektir. Hash tabloları, diziler ve listelerin karşılaştırılmasına bakacak olursak.

Arama işleminde, hash tabloları ortalama durumda, diziler kadar hızlıdır. Ekleme ve silme işleminde ise, bağlı listeler kadar hızlıdır. En kötü olduğu durumlarda ise, diğerleri kadar kötüdür. Kötü performanstan sakınmak için, çakışmalardan kaçınmak lazım. Çakışmalardan kaçınmak içinse, şunlara ihtiyacımız var.

• Düşük yük faktörüne(load factor),
• İyi bir hash fonksiyonuna.

Yük Faktörü(Load Factor)

Bir hash tablosunun yük faktörünü hesaplamak kolaydır.

Örneğin, aşağıdaki hash tablosunun yük faktörü, 2 / 5 = 0.4 olur.

100 ürünün olduğu ve 100 elemanlık bir dizimizin olduğunu düşünelim. En iyi durumda, her eleman kendi boşluğuna gider.

Bu hash tablosunun yük faktörü 1 olur. Hash tablomuzda 50 boşluk olsaydı, yük faktörümüz 2 olurdu. Yük faktörünün 1'den fazla olduğu durumlar, bir boşlukta birden fazla eleman vardır demektir. Yük faktörü büyümeye başlarsa, hash tablonuza daha fazla boşluk eklemeniz gerekir. Buna da, yeniden boyutlandırmak denir. Neredeyse doluya yakın bir hash tablomuz olduğunu düşünelim.

Bu hash tablosunu, tekrar boyutlandırmamız gerekir. Yeni bir dizi oluşturup, örnek olarak mesela boyutunu 2 katına çıkarıp, önceki elemanları yeni diziye kopyalarız. Tablonun yeni hali şöyle olur.

Yeni tablomuzun yük faktörünü küçültmüş olduk. Daha küçük yük faktörüyle, daha az çakışma yaşarız. Daha az çakışma olursa, tablo daha iyi performans gösterir. Temel kural olarak, yükleme faktörü 0.7 değerinin üzerine çıktığında, tabloyu tekrar boyutlandırmak gerekir.

Yeniden boyutlandırma masraflı bir iştir. Çok fazla bu işi yapmak istemeyiz. Yeniden boyutlandırma olsa bile, hash tabloları ortalama olarak yine O(1) zamanlı çalışır.

İyi Bir Hash Fonksiyonu

İyi bir hash fonksiyonu, değerleri dizi üzerinde eşit olarak dağıtır.

Kötü bir hash fonksiyonu ise değerleri gruplar ve çok fazla çakışmaya neden olur.

İyi bir hash fonksiyonu nedir? Tüm programlarda dillerinde hash yapısı kurulmuştur. Yine de merak ederseniz, SHA fonksiyonuna bakabilirsiniz. Bunu kendi hash fonksiyonunuz olarak kullanabilirsiniz.

Bölüm 6: Genişlik Öncelikli Arama (Breadth-First Search)

Yazının devamını okumak için tıklayınız.