CCI (Computed Chaining Insertion, Hesaplamalı Zincir Eklemesi)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde, özellikle dosya yönetimi konusunun (file organization) kullandığı bir özetleme (hashing) çakışması (collision) çözüm algoritmasıdır. Basitçe bir özetleme fonksiyonu (hashing function) sonucunda, çalışma olması durumunda (collision), dizi üzerinde farklı bir adrese çakışan sayı konulur veya aranır. Bu farklı sayı için ikinci bir özetleme fonksiyonu kullanılır. Buraya kadar olan tanım, aslında doğrusal bölüm (linear quotient) yöntemi ile aynıdır. CCI yönteminin getirdiği en önemli farklılık ise sayıların asil yerlerinde bulunma önceliğidir. Yani bir adresleme alanında özetleme fonksiyonu sonucunda (hashing function) yerleştirilen sayılar ve çakışma sonucunda yerleştirilen sayılar bulunmaktadır. Çakışma sonucu yerleştirilen sayılar, asil yerlerinde değil de çakışma çözüm yönteminin gösterdiği yerlerdedir. CCI yöntemi, bu şekilde çakışmadan dolayı doğal adresinde olmayan sayıların bulunduğu sıraya, yeni ve asil yeri olarak bir sayı gelmesi durumunda bu yeni gelen sayının yazılmasını söyler.

Bu anlamda hesaplamalı zincir ekleme yöntemi (CCI), EISCH, LISCH veya doğrusal sondalama (linear probing) yöntemlerinin aksine hareketli bir yöntemdir (dynamic method) ve yerleşen sayıların yerlerini değiştirebilir.

Bu durumu bir örnek üzerinden anlamaya çalışalım.

Eklenecek olan sayılarımız 27, 18, 29, 28, 39, 13, 16, 38, 53, 49 olsun. Kullanacağımız özetleme fonksiyonu ise H : K mod 11 olarak verilsin.

Bu duruma mod 11 için 11 farklı alandan oluşan boş bir dizimiz bulunacaktır:

Sıra Anahtar Adım
0
1
2
3
4
5
6
7
8
9
10

Yukarıdaki boş tabloda, sıra sütunu, verilerin ekleneceği yeri, anahtar sütunu örnekte verilen sayıların nereye eklendiğini, adım sütunu ise, arama ve ekleme işlemleri sırasında bir sayının beklenen yerde bulunamadığında kaçar adım eklenerek aranacağıdır.

Bu anlamda CCI algoritması bağlantılı çakışma çözümü (collision with links) yapmaktadır. Yani bir çakışma durumunda, konulması gereken sıraya değil farklı bir sıraya, bir sayı konulduğunda, bu yer bağlantı bilgisinde durmaktadır.

Yukarıdaki örnekte bulunan sayıları sırasıyla ekleyelim. İlk sayımız 27 için sıra hesaplanır ve 27 mod 11 = 5 olarak bulunur ve çakışma olmadan sorunsuz bir şekilde eklenir:

Sıra Anahtar Adım
0
1
2
3
4
5 27 2
6
7
8
9
10

Yukarıdaki ekleme işlemi sırasında 27 / 2 = 2 hesaplamasına göre adım değeri de yazılır.

Ardından eklenen sayımız 18 için sıra hesaplanır ve 18 mod 11 = 7 olarak bulunur ve 18/11 = 1 bölüm değeri, adım değeri olarak çakışma olmadan sorunsuz bir şekilde eklenir:

Sıra Anahtar Adım
0
1
2
3
4
5 27 2
6
7 18 1
8
9
10

Ardından eklenen sayımız 29 için sıra hesaplanır ve 29 mod 11 = 7 olarak bulunur. Yukarıdaki görüldüğü üzere 7. Sıra doludur ve dolayısıyla bir çakışma durumu söz konusudur. Çakışma durumunda, sayının eklenmesi gereken sıradaki adım değeri kadar ilerlenir ve ilk bulunan boş yere bu yeni sayı eklenir. Yukarıdaki örnekte bu adım değeri, daha önceden 7. Sıraya konulan 18 sayısından dolayı 1’dir. Dolayısıyla sayımız 1 adım atlanarak ilk boş bulunan yere yani 8. Sıraya yerleştirilir:

Sıra Anahtar Adım
0
1
2
3
4
5 27 2
6
7 18 1
8 29
9
10

Sıradaki sayımı 28 mod 11 = 6. Sıraya problemsiz bir şekilde yerleşir:

Sıra Anahtar Adım
0
1
2
3
4
5 27 2
6 28 2
7 18 1
8 29
9
10

Bir sonraki sayı olan 39 mod 11 = 6, yerleştirilirken çakışma Çakışma olan 6. Sıradaki adım değeri 2’dir dolayısıyla yeni sayımız 39, bu adım değeri kadar atlanarak ilk boş bulunan yere yerleştirilecektir. 2 adım atlandığında 8. Sıra bulunur ve burası doludur, tekrar 2 adım atlanır ve 10. Sırada bulunan boş yere 39 sayısı yerleştirilir.:

Sıra Anahtar Adım
0
1
2
3
4
5 27 2
6 28 2
7 18 1
8 29
9
10 39

13 sayısı sorunsuz bir şekilde 13 mod 11 = 2. Sıraya yerleştirilir:

Sıra Anahtar Adım
0
1
2 13 1
3
4
5 27 2
6 28 2
7 18 1
8 29
9
10 39

16 sayısı ise 16mod11= 5. Sıra dolu olduğu için çakışır. 5. Sıradaki adım değeri 2’dir dolayısıyla 2 adım atlanarak ilk boş bulunan yere sayı yerleştirilecektir. 7. sıra doludur dolayısıyla 9. Sıraya yerleştirilir.

Sıra Anahtar Adım
0
1
2 13 1
3
4
5 27 2
6 28 2
7 18 1
8 29
9 16
10 39

38 sayısı da benzer şekilde problemli bir sayıdır. 38 mod 11 = 5 sırası doludur. Çözüm olarak 5. Sıradaki adım miktarı kadar attırılarak boş yer aranır ve 5, 7, 9, 0. Sıralara bakılarak , boş bulunan 0. Sıraya yerleştirilir.

Sıra Anahtar Adım
0 38
1
2 13 1
3
4
5 27 2
6 28 2
7 18 1
8 29
9 16
10 39

Ardından gelen 53 sayısı için benzer şekilde çakışma olur çünkü 53 mod 11 = 9. Sıra doludur. Bu sayının, şimdiye kadar olan sayılardan farkı, çakıştığı ve daha önceden 9. Sıraya yerleşen sayı olan 16 sayısının doğal yerinde bulunmamasıdır. Yani 9. Sırada, daha önceden yerleşen 16 sayısı, aslında 9. Sıraya yerleşmesi gerekmeyen ancak 5. Sıra dolu olduğu için buraya yerleştirilmiş sayıdır.

Bu durumda, CCI algoritması, doğal olarak yerleşen sayıya, çakışmadan dolayı yerleştirilen sayıdan öncelik tanımaktadır. 16 sayısının yerine 53 sayısı öncelikli olarak yerleştirilir.

Sıra Anahtar Adım
0 38 16 1
1 38
2 13 1
3
4
5 27 2
6 28 2
7 18 1
8 29
9 16 53 1
10 39

53 sayısının yerleştirilmesi üzerine 16 sayısı sıradaki adım değeri olan ve 1 adım sonrası olan 0. Sıraya taşınır. Burada bulunan 38 sayısı da bir sonraki boş sıraya taşınarak adım değerleri buna göre güncellenir.

Sıra Anahtar Adım
0 16 1
1 38
2 13 1
3
4
5 27 2
6 28 2
7 18 1
8 29
9 53 1
10 39

Son olarak gelen 49 sayısı, yerleşmesi gereken 49 mod 11 = 5. Sıra dolu olduğu için 5. Sırada bulunan adım değeri kadar atlanarak boş yer aranır. Sırayla, 5, 7, 9,0,2 ve 4.. Sıralara bakılır. 4. Sırada boş yer bulunduğu için buraya yerleştirilir:

Sıra Anahtar Adım
0 16 1
1 38
2 13 1
3
4 49
5 27 2
6 28 2
7 18 1
8 29
9 53 1
10 39

Yukarıdaki örnekte sayıların nasıl yerleştirildiğini gördük. Bu yöntemi özetleyecek olursak:

  1. Yerleşecek sayının (anahtarın) özetleme fonksiyonu değerini (hashing function) hesapla ayrıca bölümden gelen adım değerini de hesaplayarak buraya yerleştir.
  2. Şayet burası doluysa, hesaplanan adım değeri kadar atlanarak boş olan ilk yere sayı yerleştirilir.
  3. Şayet sayının yerleşeceği yer doluysa ve buradaki sayı, normalde yerleşmesi gereken yer değilse o zaman yeni gelen sayı önceliğe sahip olup buradaki sayı ile yer değiştirilir.

Yukarıdaki bu 3 basit adım takip edilerek CCI algoritmasına göre yerleştirme işlemi yapılabilir.

brent yöntemine (Brent’s method) benzer şekilde, CCI yöntemi de sınıflandırma bakımından, hareketli metot (dynamic method) olarak kabul edilebilir. Bundan kasıt, bir sayı bir sıraya yerleştikten sonra buradan hareket edebilir, bu durum yukarıdaki örnekte 53 sayısının yerleştirilmesi sırasında açıkça görülmektedir.

Tagged:

Yorumlar

  1. Reply
    Gökhan Duman

    Adım sayısını 11’e göre hesapladınız yazınızın başında(bknz 18/11 = 1 bölüm değeri, adım değeri olarak…) Yazının devamında 53’ün adım sayısını 2 olarak atadınız. Bunun nedeninini öğrenebilir miyim ?

  2. Reply
    Şadi Evren ŞEKER Article Author

    Yukarıdaki yazıda hata olmuş. 53’ün yanındaki adım değeri 2 değil 1 olacaktı. Bu değer nasıl hesaplandı derseniz 53 ile 16 yer değiştirdiği için, 53 gelmeden önce 9. sırada bulunan 16 sayısının adım değeri buraya yazılıyor ve 16 / 11 = 1 olduğu için adım değeri 1 oluyor.
    Yazıda da durumu düzeltiyorum. İlginiz için teşekkürler.

    Update: Yazıda ilgili hatayı düzelttim.

  3. Reply
    Ahmet Güngör

    Çok güzel bir anlatım olmuş teşekkürler 🙂 Ben de üstte 53%11=4 oldugu ıcın 4. adımı bekliyorum ama aşağıdaki yorumunuzu görünce anladım:)Sanırım bir de 27/11=2 yerine 27/2=2 yazmışsınız 🙂
    Tekrardan çok teşekkürler 🙂

    http://letscoding.com

  6. Reply
    Kemal

    kitapta gösterildiğine göre en son 9. adresten 16 çıkıp 53 girdikten sonra, sanki 16 yeni bir recordmuş gibi tekrar koyuluyor ve 5. adreste bulunan 27 nin pseudolinkini(adımını) 2den 3 e yükseltiyor. Böylece 16 0. adrese oturuyor ve home adresi olan 5 ten 3 “adımda” ulaşılıyor.

    9. adreste bulunan 53 ün de bi psuedolink bulundurmasına gerek yok çünkü 53 ten sonra gelen başka 9. adrese girilmesi gereken record yok.Aynı şey 1. adreste bulunan 13 içinde geçerli.

    son gelen 49 un home adresi 5. ve psuedolinki de 3(önceki söylediklerimin doğru olduğunu düşünerek) böylece 0. adrese gidilir ordan 1. adrese yani 38 e gidilir ve pseudolink null olduğundan buraya linklenebileceği düşünülür 38%11=3 oldugundan 3 atlanır ve 4. adrese 49 yazılır , 38 in yanına da 1.

    benim kitaptan anladığım buydu tekrar kontrol edip varsa yanlışlarımla beraber cevap verirseniz sevinirim

  9. Reply
    Şadi Evren ŞEKER Article Author

    neden 53’ün adım sayısını 1 yaptığımız sorusunun cevabı, aslında burada bulunan 16 sayısının adım sayısını alıyor olmamız. Yani 16 ile 53 yer değiştirdikten sonra adım sayısı 16’ya göre ayarlanmıştır. Bu durumu arama sırasında test ederek görebilirsiniz (4 olsa 16yı bulamazdı).

    Kemal Beyin yazdıkları ise mümkün. Yani 16 ile 53 arasında yer değiştirme yapmak yerine 16 yeniden sisteme yeni bir kayıt gibi eklenirse sistem çalışacaktır. En azından ben test ettim ve bir problem göremedim.

    Başarılar

  12. Reply
    Memati Baş

    Hocam merhabalar,
    Çok faydalı paylaşımlarınız olmakla birlikte, baştan sonra yanlış yazılarınız da var. Bu duruma şaşırıyorum. Bütün kitaplar ve videolar yanlış mı yoksa siz hata mı yapıyorsunuz?
    Bu yazınızdaki hatayı söylemek istiyorum:
    Tablonun son halinde bütün sayılar doğru olarak yerleşmiş.Ancak adım kısmı yanlış.Sözel olarak nasıl yapılması gerektiğini doğru yazmışsınız ama tablonun son halinde 53′ ün yanında 1 yazıyor.Bunun anlamı, 53 dışında modu 9 alan bir sayı var ve yeri de 53 ün adım boyuyla 1 adım sonra yani 4 sıra sonra.Ama bu gösterilen yerde 13 var yani 53 le alakası olmayan bir sayı.
    16′ yı arayan bir kişi 5 inci indise baktığında 27 sayısını görecek.Yanında adım olarak 2 yazmışsınız.27 ‘nin adım boyuyla 2 adım sonrasında 53 var.Computed chaining coalesced olgusuna izin vermez.Hadi coalesced olduğunu varsayalım 53 de 13 ü gösteriyor.13 ise boş bir yeri gösteriyor.Arayan işi 16’ ya ulaşamadı.
    Eğer ben computed chaining tablosunu tamamlamadım, adım yazan yerdeki değerler o indisteki sayının adım boyudur diyorsanız o zaman da 53 ün yanında 4 yazmalı. 16 nın yerine yazdım bu nedenle 16 nın adım boyuyla yer değişir gibi bir ezber bilgi literatürde yoktur.
    Tablonun son halinde number of ofset dediğimiz nof bölümünü şu şekilde değiştirmemiz gerekiyor:
    0 16 1
    1 38
    2 13
    3
    4
    5 27 3
    6 28 2
    7 18 1
    8 29
    9 53
    10 39

    Umarım bu hatanızı farkeder ve düzeltirsiniz.Şimdiden teşekkürler.

Bir cevap yazın

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