İkinci Dereceden Sondalama (Quadratic Probing)

Yazan : Şadi Evren ŞEKER

Özellikle özetleme fonksiyonlarının (hashing functions) bilgileri sınıflandırması sırasında kullanılan formülün ikinci dereceden olması durumudur.

Özetleme fonksiyonlarında, sık kullanılan doğrusal sondalama (linear probing) yönteminin tersine, bir bilgiyi tasnif ederken, ardışık olarak veriler üzerinde hareket etmez, bunun yerine her defasında baktığı uzaklığı ikinci dereceden bir denklem ile arttırır.

Konuyu anlamaya öncelikle doğrusal fonksiyonları hatırlayarak başlayalım.

Bilindiği üzere doğrusal fonksiyonlar :

y = ax + b şeklinde yazılabilen birinci dereceden fonksiyonlardır. Bu durumda özetleme fonksiyonu veriyi sınıflandırırken bir çakışma (collision) olması durumunda bir sonraki veri hücresine bakar, ve bu şekilde aranan veriye ulaşana kadar devam eder. Örneğin 10 hücreli bir sınıflama için mod 10 fonksiyonunu kullanacağımızı düşünelim.

Bu durumda ilk başta aşağıdaki şekilde boş olan veri yapımıza sırasıyla 21,31,41,51 sayılarının geldiğini kabul edelim.

0
1
2
3
4
5
6
7
8
9

Dikkat edileceği üzere bu sayılar özellikle çakışma olsun diye mod 10 fonksiyonuna konulduğunda hep 1 olarak çıkan sayılardan seçilmiştir.

Şimdi bu sayıları yerleştirecek olursak ilk gelen sayı 21 mod 10 = 1 olduğu için 1. Hücreye yerleştirilecektir.

0
1	21
2
3
4
5
6
7
8
9

Ardından gelen 31 sayısı yine 1. Hücreye yerleştirilmek istenecek ancak burası dolu olduğu için doğrusal sondalama kullanarak bir sonraki hücreye yerleştirme yapılıyor:

0
1	21
2	31
3
4
5
6
7
8
9

Diğer sayılar için durum değişmiyor ve aynı yaklaşım izlenmeye devam ediliyor:

0
1	21
2	31
3	41
4	51
5
6
7
8
9

Görüldüğü üzere elimizdeki sayıların tamamı başarılı bir şekilde yerleştirilmiştir. Konuyu daha iyi anlayabilmek için farklı bir örnek olarak 33 sayısını yerleştirmek istediğimizi düşünelim. Bu durumda 33 mod 10 = 3 hücresi dolu olduğu için işlem değişmeden yukarıda olduğu gibi uygulanacaktır:

0
1	21
2	31
3	41
4	51
5	33
6
7
8
9

İkinci dereceden sondalama (quadratic probing)

Doğrusal sondalamayı anladıktan (hatırladıktan) sonra ikinci dereceden sondalamadan bahsedebiliriz. Buradaki yaklaşımda kullanılan formül bir özetleme fonksiyonunda geçildikten sonra çakışma olması durumunda (collision) sürekli olarak bir sonraki hücreye bakmak yerine, her defasında üssel fonksiyon değeri kadar ilerlemektir.

Örneğin yukarıdaki sayılar için aynı veri yapısına ikinci dereceden sondalama ile ekleme işlemi yapalım:

0
1	21
2
3
4
5
6
7
8
9

İlk gelen sayı, bir çakışma olmadığı için doğal hücresine yerleştiriliyor. Ardından gelen 31 sayısı için çakışma oluyor. Bu durumda sonraki bakılacak olan hücrenin karesi alınıyor, şu anda ilk çakışma yaşandığı için 1² = 1 yani doğal hücreden bir sonraki hücreye bakıyoruz:

0
1	21
2	31
3
4
5
6
7
8
9

Bu hücre boş olduğu için yerleştirme işlemi tamamlanıyor ve sıradaki sayıya geçiliyor.

Sayımız 41 ve doğal hücresi olan 1. Adreste çakışma yaşanıyor,

ardından 1² = 1 sonraki hücrede de (yani 2. Hücre) çakışma yaşanıyor,

ardından gelen 2² = 4 sonraki hücreye bakılıyor. Dolayısıyla doğrusal sondalamada olduğu gibi 3. Hücreye bakmak yerine 5. Hücreye bakıyoruz:

0
1	21
2	31
3
4
5	41
6
7
8
9

Sırada 51 bulunuyor ve benzer şekilde doğal hücresi dolu, 1² = 1 sonraki hücre dolu, 2² = 4 sonraki hücre dolu ve nihayet 3² = 9 sonraki hücre boş bulunup yerleştiriliyor.

0	51
1	21
2	31
3
4
5	41
6
7
8
9

Yukarıdaki yerleştirme işlemi sırasında mod10 kullanıldığı unutulmamalıdır, bu yüzden 0. Hücreye yerleştirme işlemi yapılmıştır.

Doğrusal sondalama örneğinde olduğu gibi, 33 sayısını da eklemek istediğimizde doğal hücresi boş olduğu için herhangi bir sondalamaya gerek kalmadan yerleştirme işlemi yapılabilir:

0	51
1	21
2	31
3	33
4
5	41
6
7
8
9

Doğrusal sondalamada özetleme fonksiyonundan sonra sırasıyla veri yapısındaki hücrelere bakılır. Bu durum için aşağıdakine benzer bir döngü yazılması gerekir:

Görüldüğü üzere, öncelikle özetleme fonksiyonuna (h) anahtar verilip doğal adres bulunuyor. Bu adresin dolu olması ve sonraki adreslerin de dolu olması durumunda adres değeri arttırılarak devam ediliyor.

İkinci dereceden sondalama kullanılsaydı, bu kodu aşağıdaki şekilde yazmamız gerekecekti:

Yukarıdaki yeni haliyle kodumuz, her defasında artış miktarının karesi kadar sonraki hücreye bakmaktadır.

Yukarıdaki müsvedde kodlar (pseudo codes) ve örnekler fikir vermesi açısından yazılmış olup, özetleme fonksiyonu, doğrusal sondalama ve ikinci dereceden sondalama işlemleri için farklı fonksiyonlar kullanılabilir. Buradaki amaç, ikinci dereceden sondalamada kullanılan fonksiyonun ikinci derece bir denklem olmasıdır.

« C ile Programlamaya Giriş Quiz Soruları ve Çözümleri | Çift Özetleme (Double Hashing) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'İkinci Dereceden Sondalama (Quadratic Probing)' isimli yazı 18 Jan 2010 tarihinde, saat: 13:45 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 265 defa okunmuştur.

Benzer yazıları Dosya Organizasyonu (File Organisation), Veri Güvenliği(Cryptography), Veri Sıkıştırma (Data Compression), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar