Linear Quotient

Merhaba arkadaşlar,

Bugün, daha önce başlamış olduğumuz, collision resolution algorithms without links(bağlantı olmadan çakışmaları çözme algoritmaları)'e devam edeceğiz. Bugünkü konumuz Linear Quotient. Bu algoritma, Progressive Overflow yöntemine çok benzer. O yöntemde, collision olduğunda, kaydı bir sonraki boş adrese yerleştiriyorduk. Yani artım sayımız 1 idi(1 sonraki adres doluysa, yine 1 sonrasına gidiyorduk. Hatırlayamayanlar için: http://gurkanalkan.blogspot.com/2010/12/progressive-overflow-linear-probing.html). Linear Quotient'te ise artım sayısı değişkendir. Yani collision(çarpışma) olduğunda, 1 sonraki kayda bakmak zorunda değiliz. Artım sayısı kaç ise, o kadar ötedeki adrese yerleştiririz. Bu sayede probe(adım) sayısı azaltılarak, average probe(bir kayda ulaşmak için gereken ortalama adım sayısı) düşürülmüş; başka bir deyişle progressive overflow'a göre performans artışı sağlanmış olur.

Peki bunca şeyi nasıl yapıyoruz? 2 adımda yaparız. Önce her zaman olduğu gibi, değerin home adress'ini bulan hash fonksiyonuna tabi tutarız. Ardından collision yaratan kayıt varsa şayet, o kayıt için artım miktarını belirleyen ikinci bir hash fonksiyonunu uygularız.

hash₁=key modP

hash₂=Quotient(key/P) modP

Yine Alan Tharp ve yine klasik örneğimiz diyorum. :)

SORU: 27-18-29-28-39-13-16-42-17 mod 11

ÇÖZÜM:
hash(27)=5 mod11
Tablomuza ilk elemanımızı sorunsuzca yerleştiriyoruz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7
8
9
10

İkinci elemanımıza geçelim. hash(18)=7 mod11
7 numaralı adres(göz) de boş olduğundan, 18'i de sorunsuzca yerleştiririz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7	18
8
9
10

Sıradaki kayda geçelim.
hash(29)=7 mod11
Evet arkadaşlar, konuyu anlama vakti. :) Collision oldu şimdi. 7 numaralı adrese az önce 18'i yerleştirmiştik, 29'u yazamayız artık. Linear Quotient'te şöyle yapıyoruz: Collision'ı yaratan kaydı buluruz. Örneğimizde collicion'a sebep olan değer 29. O halde collision'a sebep olan kaydın(29) artım miktarını bulmalıyız. Yani ikinci kez hash fonksiyonuna tabi tutarız. O da şöyledir: 29/11=2. Yani 29'u, mod 11'e göre yaptığımızdan dolayı, 11'e böldük. Bölen 2 çıktı. Bizi bölen değer ilgilendirir, kalan ilgilendirmez. Bölen değer bizim artım miktarımız oluyor aynı zamanda.
Şimdi... 29 değerinin home adress'i 7 çıkmıştı. Artım miktarını(bölen değer) 2 bulmuştuk.. Yani 7 numaralı adresten 2 birim ötesine bakarız. 7+2=9 numaralı adrese bakarız. Orası boş ise şayet, 29'u yerleştiririz. Boş olduğunu gördüğümüze göre, yerleştirelim.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7	18
8
9	29
10

Herhalde neden Quotient isminin kullanıldığını anlamışsınızdır. Quotient, bölen demektir. Biz de artım miktarını bulurken, değerimizi, mod değerine bölüyoruz ve böleni alıyoruz...

Sırada 28 var.
hash(28)=6 mod11
6 numaralı adres boş olduğundan sorunsuzca yerleştiririz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6	28
7	18
8
9	29
10

Sırada 39 var.
hash(39)=6 mod 11
Yine collision oluştu. 6 numaralı adrese az önce 28'i yerleştirmiştik. O zaman collision'ı yaratan kayıt olan 39'u ikinci kez hash'leyeceğiz.
39/11=3. Bölen 3, kalan 6. Ancak bizi sadece bölen ilgilendirir. (Bu arada hep 11'e bölmemizin sebebi, soruda mod 11 olarak verilmesindendir. mod7 denseydi, 7'ye bölerdik)
6 numaralı adrese yerleştirememiştik. Artım miktarı 3 çıktığından, 3 birim sonrasına gideriz: 6+3=9 numaralı adres. Ancak 9 numaralı adreste de 29 değeri var, yani yine dolu... O zaman bir 3 birim daha gitmeliyiz. Ta ki boş alan bulana dek gideriz. (Ancak sonsuza kadar gidilmez tabi. Tekrardan 6 numaralı adrese geldiğimizde, bu işlemi sonlandırırız.). 9 numaralı adresten, 3 birim daha gidersek, 1 numaralı adrese gideriz. Orası boş, o halde 39'u yerleştirebiliriz.

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

Sırada 13 var.
hash(13)=2 mod11
2 numaralı göz boş olduğundan sorunsuzca yerleştiririz.

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

Sıra geldi 16'yı yerleştirmeye.
hash(16)=5 mod11
5 numaralı göz dolu.
16/11=1.(Bölen 1, kalan 5; bizi sadece bölenin ilgilendirdiğini hatırlayın)
Yani 1 birim öteleyerek uygun/boş adresi bulacağız. 5 numaralı adres dolu idi. 1 birim sonrası:6 numara da dolu. 1 birim daha ötelersek:7 numaralı göz de dolu. 1 birim daha ötelersek:8 numaralı göz boş. 16 değerini 8 numaralı göze yerleştirebiliriz.

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

Sırada 42 var.
hash(42)=9 mod11
9 numaralı göz dolu maalesef.
42/11=3 (Bölen 3, kalan9. Bizi yalnızca bölen ilgilendiriyor)
9 numaralı gözden 3 birim öteye gideriz:1 numaralı göz de dolu. Yine 3 birim öeteye gideriz:4 numaralı göz boş. O halde 42'yi oraya yerleştiririz.

Sıra	Anahtar Değeri
0
1	39
2	13
3
4	42
5	27
6	28
7	18
8	16
9	29
10

Son olarak 17'yi yerleştirelim.
hash(17)=6 mod11
6 numaralı adres dolu olduğundan, yeni collision'ımız hayırlı uğurlu olsun. Hemen ikinci hash fonksiyonumuza geçelim.
17/11=1 (Bölen 1, kalan 6. Biz sadece bölene bakarız)
6 numaralı göz doluydu. 1 birimötelersek:7 numaralı göz de dolu. Yine 1 birim ötelersek, 8 numaralı göz de dolu. Yine öteleyelim:9 numaralı göz de dolu. Durmak yok, yola devam, öteleyelim efendim:10 numaralı göz boş. O halde hemen 17'yi yerleştiriyoruz.

Sıra	Anahtar Değeri
0
1	39
2	13
3
4	42
5	27
6	28
7	18
8	16
9	29
10	17

Böylece bir kayda erişmek istediğimizde, bunu daha az adımda başarabileceğiz. Average probe da yaklaşık 1.9 çıkmakta. Bu yöntemde de kayıt silmek istediğinizde tombstone kullanmalısınız. Sebebini diğer kayıtta açıklamıştım gerçi: arama yaparken, arada boşluk olur. Arama işlemi de boşluğu görünce sonlanır. O yüzden kayıt silerken, yerine bir işaret koyarız. Böylece orda kayıt olmasa da, ordan bir yol geçtiğini biliriz. Yerine yeni bir kayıt geldiğinde de tombstone'u kaldırırız.

Eğer arada anlamadığınız terimler var ise, sormaktan çekinmeyin. Çünkü bugün bazı yerleri anlamayan arkadaşlarım olduğunu öğrendim. Konu bütünlüğü için tüm hash konularımı okumanızı öneririm, eğer vaktiniz varsa.

İyi akşamlar.

Progressive Overflow (Linear Probing)

Herkese tekrar merhaba,

Çarpışmayı engelleyen(collusion resolution) yöntemlerimize devam ediyoruz. En son EISCH algoritmasından bahsetmiştik. Tıpkı LISCH-LICH gibi, EISCH'in de EICH adında farklı bir versiyonu var. Ama benzer mantık olduğu için onu anlatmadan geçtim. BLISCH gibi konulara değineceğim bir ara da. Şimdiye kadar hep bağlantı yoluyla çarpışma engelleme algoritmalarından bahsettik(with links). Şu anda ise bağlantı olmadan, without links, çarpışmayı engelleme algoritmasına geçiyoruz.

Link'ler ile olan yöntemde, hatırlarsınız, bir anahtar değerini tutan alanımız, bir de bağlantıyı koparmamak için Link değerini tutan alanımız vardı. Without Links kategorisinde, adından da anlaşılacağı üzere, Link değerini tutan bir alanımız yok. Bu anlamda, Link ile çalışan algoritmalara göre daha avantajlı.

Progressive Overflow, bağlantısız (without links) çalışan algoritmalar içerisinde en basit olanı. Mantık şu: herhangi bir anda collision(çarpışma) olursa, takip eden ilk boş/müsait yere yerleştirilir.(Tablonun sonuna kadar gittiniz ve boş yer bulamadıysanız, tablonun en başından itibaren yerleştirmeye çalışınız). Basit olduğu için tercih edilebilse de, başarısız aramalarda performansı oldukça düşüktür.

Her zaman olduğu gibi Alan Tharp amcamızın kitabındaki soruyu çözelim.

SORU: 27-18-29-28-39-13-16-42-17       mod 11


ÇÖZÜM: Her zaman olduğu gibi hash'ini alarak home address'lerini buluruz.
hash(27)=5 mod11
Hash bulmayı unutanlar için bir kez daha hatırlatayım. 27 değeri verilmiş bize. mod da 11 imiş. 27'yi 11'e bölüyoruz. Kalan değer bizim hash değerimiz veya bir başka deyişle home address'imiz oluyor. 27 için home address'i 5 çıktı. O halde 27 değerini tablomuzun 5 numaralı gözüne yazıyoruz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7
8
9
10

Şimdi de 18'i yerleştirelim.
hash(18)=7 mod 11
7 numaralı göz de boş olduğundan sorunsuzca yerleştiririz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7	18
8
9
10

29'a geldi sıra. Şimdi bu yöntemi anlamaya başlayacaksınız.
hash(29)=7 mod 11
7 numaralı göz dolu, az önce oraya 18 yerleşmişti. Link kullandığımız önceki algoritmalarda R değeri tutuyor, bu değerin gösterdiği gözlere sayımızı yerleştiriyorduk. Progressive Overflow'da ise bir sonraki göze yazıyoruz, gayet basit. :) 7 numaralı göz dolu olduğundan, bir sonraki göze bakıyoruz. 8 numaralı göz dolu mu boş mu diye kontrol ediyoruz. Boş olduğunu görüyoruz(yukarıdaki tabloya bakın). Bu yüzden kaydımızı 8 numaralı göze yazıyoruz. Eğer 8 numaralı göz de dolu olsaydı, bu sefer 9 numaralı göze bakardık. Tablonun son hali şöyledir:

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6
7	18
8	29
9
10

28'i yerleştirelim.
hash(28)=6 mod 11
6 numaralı göz boş olduğundan, 28'i sorunsuzca yerleştiriyoruz.

Sıra	Anahtar Değeri
0
1
2
3
4
5	27
6	28
7	18
8	29
9
10

39'a geldi sıra.
hash(39)=6 mod11
6 numaralı göz dolu. Oraya az önce 28'i yerleştirmiştik. O yüzden bir sonraki göze bakıyoruz:7 numaralı göz. Ancak 7 nuaralı göz de dolu, orda da 18 var. Yine bir sonraki göze bakıyoruz:8 numaralı göz. Maalesef orası da dolu, orda da 29 var. Yine bir sonrasına bakarız:9 numaralı göz. Nihayet boş bir göze denk geldik. :) 39 değerini 9 numaralı göze yerleştiriyoruz. Tablo şu hale gelir:

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

13'ü yerleştiriyoruz şimdi.
hash(13)=2 mod11
2 numaralı göz boş olduğundan, 13 değerini sorunsuzca yerleştiririz.

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

16'da sıra.
hash(16)=5 mod11
5 numaralı göz dolu. 6, 7, 8 ve 9 numaralı gözlere de sırayla bakacak olursak, onların da dolu olduğunu göreceğiz. O yüzden yine bir sonraki göze bakıyoruz:10 numaralı göz. Orası boş!! :) 16 değerini de 10 numaralı göze yerleştiriyoruz o halde. Tablo şu hale gelir:

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

42'ye geldi sıra.
hash(42)=9 mod11
9 numaralı göz dolu olduğundan, oraya yerleştiremiyoruz. Bir sonraki göze bakarız:10 numaralı göz. Ancak orası da dolu. Yazının en başında, böyle bir durumla karşılaşırsak, ne yapacağımızı belirtmiştim. Tablonun sonuna ulaştık. O yüzden tablonun en başından başlayarak, boş yer aramaya devam ederiz. 10 numaralı göz doluydu. Bir sonraki göze bakalım:0(sıfır) numaralı göz. Orası boş. Bu yüzden 42 değerini 0 numaralı göze yerleştiririz. Tablo şu hale gelir.

Sıra	Anahtar Değeri
0	42
1
2	13
3
4
5	27
6	28
7	18
8	29
9	39
10	16

Son olarak 17'yi de yerleştirelim.
hash(17)=6 mod 11
6 numaralı göz dolu. Ondan sonra gelen, sırasıyla 7, 8, 9, 10 ve 0 numaralı gözler de dolu. 1 numaralı göz ise boş. 17 değerini de buraya yerleştiririz. Tablonun nihai hali şöyledir:

Sıra	Anahtar Değeri
0	42
1	17
2	13
3
4
5	27
6	28
7	18
8	29
9	39
10	16

Bu algoritma için de average probe'u(bir değere ortalama kaç adımda ulaşabildiğimiz) hesaplarsanız(daha önce yapmıştık), oldukça yüksek bir değer elde edeceksiniz. Bunun sebebi secondary clustering(ikincil kümeler)'dir. Bu da farklı home address'ine sahip kayıtlardan kaynaklanmaktadır. Daha farklı açıklamak gerekirse, artış sayısının 1 olmasından ötürü, ikincil kümeler ortaya çıkmaktadır. Pratikte pek de kullanılmaz bu algoritma.
Son bir not, bu algoritmada da kayıt direkt silinmez. Aksi takdirde arama işlemi sırasında boşluklar oluşabilir. Arama işlemi de boşluğu gördüğünde, aramayı durdurur; aranan kayıt tabloda bile olsa ulaşılamaz olur. Bu yüzden silinecek kaydın başına tombstone konur(işaretleme yapıyorsunuz yani). Bu göze yeni bir kayıt ekleyince de o tombstone'u kaldırırsınız.

Bu algoritma da bu kadar. Sonra görüşürüz..