İ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 12 = 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 12 = 1 sonraki hücrede de (yani 2. Hücre) çakışma yaşanıyor,

ardından gelen 22 = 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, 12 = 1 sonraki hücre dolu, 22 = 4 sonraki hücre dolu ve nihayet 32 = 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.

Yorumlar

  1. Reply
    can

    merhaba hocam emeğinize sağlık öncelikle hocam bize şu şekilde bir formülle anlatıldı bu konular
    h(k,i)=(h'(k)+c1*i+c2*i^2)modm doğrusu siz baya kısa yoldan sanırım çözmüşsünüz ama anlayamadım ben çözüm yolunuzu 2.ve sonrasındaki elemanları yerleştirmeyi nasıl yapıyorsunuz…

  2. Reply
    Şadi Evren ŞEKER Article Author

    İkinci dereceden sondalamanın tek şartı, çakışma (collision) durumlarında, ikinci dereceden bir fonksiyon kullanılmasıdır. Sizin verdiğiniz fonksiyon kullanılabileceği gibi, yazıdaki fonksiyon da kullanılabilir, veya başka herhangi ikinci dereceden bir fonksiyon kullanılabilir.

    Yazıda çakışma olan indeksin karesi alınıyor. Yani sizin gösteriminizle i2 şeklinde indeks değerinin karesi alınarak deneniyor.

    Başarılar

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir