Self-Organizing Sequential Search

Merhaba tekrar.
Bugün makinem ile ilişiğimi erken keseceğim. :) Çıkmadan bir konuda yazayım dedim.

Self-Organizing Sequential Search. Nedir bu uzunca isimli yöntem? Bu yöntem, Sequential File Organization Methods(Sıralı verilere erişim yöntemleri) başlığı altında incelenen bir konudur. Cache belleklerde sık kullanılan bir yöntemdir. Amaç, verilerin sıralı yapısını tekrar organize ederek, sonraki erişimlerde daha iyi performans elde etmektir. Bu konu altında 3 algoritma mevcuttur.

1. Move-To-Front Algoritması
2. Transpose Algoritması
3. Count Algoritması

Şimdi kısaca bunlara değinelim.

Move-to-Front Algoritması: Herhangi bir dizi elimizde olsun. Örneğin alfabeyi düşünelim.

a b c d e f g h

c harfini aradığımızı varsayalım. 3 adımda(a-b-c) c harfine ulaşırız. Ulaştıktan sonra c harfini öne alırız.

c a b d e f g h

şeklini alır dizimiz. Yani herhangi bir erişimde, eriştiğiniz elemanı en öne alıyorsunuz. Bu işlemler bir süre sonra stabil olurlar ve sık kullanılanlar önde kalır. Sık kullanılmayanlar da cache'den atılır.

Transpose Algoritması: Herhangi bir kayda erişince, o kaydı bulunduğu noktanın 1 adım önüne alır.

a b c d e f g h

c harfini arayalım tekrar. c harfine erişince dizimizin yeni hali:

a c b d e f g h

Şimdi de f harfini arayalım mesela. f harfini de, e'nin önüne alacağız bu durumda.

a c b d f e g h

şeklinde bir dizi elde ederiz. Bu algoritma direkt en öne almıyor diğeri gibi. Belki o eleman sık kullanılmıyordur diye düşünüp, bir adım öne çekiyor sadece. Uygulanması daha kolaydır move to front algoritmasına göre.

Count Algoritması: Uygulanması en zor olanı. Her elemanla birlikte, o elemana kaç kez erişildiğinin sayısını da tutar. En çok erişileni en öne alır.

a b c d e f g h --dizimiz
0 0 0 0 0 0 0 0 --erişim sayıları

Diyelim ki c harfine eriştik. c'nin erişim miktarı 1 arttı.

c a b d e f g h
1 0 0 0 0 0 0 0

Şimdi de a harfine erişelim.

a c b d e f g h --a ya da c önde kalabilir, fark etmez.
1 1 0 0 0 0 0 0

Tekrar c'ye eriştik diyelim.

c a b d e f g h
2 1 0 0 0 0 0 0

şeklinde oluşur dizimiz. Ancak unutmadan belirteyim, bunu böyle her erişimde güncellemeyiz. Timer mantığında çalışır. Belli bir zaman aralığında yapar bu sıralamayı. Örneğin 3 dakikada bir güncelleme yapar ve erişim sayılarına göre diziyi sıralar. Aksi takdirde çok yer değişiminden mütevellit performans kaybı yaşanırdı.

Bu konu bitti, görüşürüz sonra. :)