Keşke bu yazıyı bir ay önce buraya koysaydım diyorum şimdi. Neyse artık..
Geçen sene bu zamanlarda yazdığım, yazarken çok keyif aldığım ve birçok şey öğrendiğim LISCH, EICH, RLISCH ve BEISCH algoritmaları arasında performans karşılaştırması yapan programlama ödevimi paylaşıyorum. Gönül isterdi ki proje dosyasını koyayım. Ancak maalesef geçen sene, ödevi bitirmiş olmanın heyecanıyla VS'da program debug'dayken shutdown yaptığım için proje dosyasında hatalar oluştu ve kullanılamayacak hale geldi :)
Geçen sene bu zamanlarda yazdığım, yazarken çok keyif aldığım ve birçok şey öğrendiğim LISCH, EICH, RLISCH ve BEISCH algoritmaları arasında performans karşılaştırması yapan programlama ödevimi paylaşıyorum. Gönül isterdi ki proje dosyasını koyayım. Ancak maalesef geçen sene, ödevi bitirmiş olmanın heyecanıyla VS'da program debug'dayken shutdown yaptığım için proje dosyasında hatalar oluştu ve kullanılamayacak hale geldi :)
Neyse, bir musibet bin nasihattan iyidir dedik, atalarımızı bir kez daha yad ettik.
Neyse ki sürekli yedek almanın önemini bu ödevi yazmadan önce kavramıştım. Aşağıdaki kodlar son hali değildi hatırladığım kadarıyla, birkaç ufak tefek hataları oluyordu, onları düzeltmiştim. Ancak dediğim gibi, onlar yok sanırım, shutdown'la birlikte gitti herhalde. Bu düzgün hali de olabilir, hatırlamıyorum açıkçası. En kötü ihtimalle son aldığım yedek olduğundan eminim, ya %100 doğru, ya da doğruya çok yakın. Hatırlayamıyorum şimdi, artık o kadarını da siz bulun.
Şunu da eklemek isterim, programlama işi yaparak öğrenilen bir iş, hazır kodlar alıp, kopyala yapıştır mantığıyla pogramlar yazarsanız gün gelir kopyalayacak bir şey bulamazsınız, o zaman da "sen nasıl mühendissin?" şeklinde haklı bir soruyla karşılaşırsınız. "Copy-paste mühendisiyim" diye cevaplayabilirsiniz, ya da susma hakkınızı kullanırsınız, sizin bileceğiniz iş. En güzeli hazırcılıktan kaçmak, önce analiz, sonra tasarım sonra da kodlama yapmak. En son da test etmek.
Şimdi aklıma geldi, bu söz bilgisayar ve programlama dünyasına hediyem olsun ;) Program yazmaya klavye-mouse'la değil, kalem-kağıtla başlanır. Artık yakın gelecekte bölüm katına benim bu sözü çerçeveletip asarlar. Yalnız yanına da haritacılık alanındaki 12 prensibimi asmazlarsa hatırım kalır. (Onlara da buradan bakabilirsiniz.)
Uzun lafın kısası, demek istiyorum ki önce algoritmanı ve tasarımını kağıt kalemle oluştur, kodlamaya ondan sonra geç ve copy-paste'den kaçın.
Umarım faydalı olur. Kolay gelsin.
Programın özellikleri:
- Packing factor ~ %90’dır.
- Program her algoritma için tabloyu ekrana yazdırır.
- Program, kullanıcı tarafından girilen rastgele değer sayısına göre algoritmaların performansları karşılaştırır. (Program girilen sayı için her algoritmadaki ortalama probe sayısını verir.)
- Programda aranacak sayı girilerek arama yapılabilir. Kaç probe’da bulunduğu gösterilir.
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
namespace dosya_org_odev_1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
int kac_sayi;
int[] rast_dizi; //***************************************************
Random rd;
public int bulunan_hafiza_boy;
private void button1_Click(object sender, EventArgs e)
{
rd = new Random();
Boolean hata_bayragi=true;
try
{
kac_sayi = Convert.ToInt32(textBox1.Text);//kaç sayı ile çalışacağımız. Not:packing factor hesaplarken de kullanacağız.
}
catch(Exception ex)
{
MessageBox.Show("Adam gibi bir değer girin!\n"+ex.Message);
hata_bayragi = false;
}
if (kac_sayi> 900)
{
MessageBox.Show("900'den küçük bir değer girin!");
hata_bayragi = false;
}
rast_dizi=new int[kac_sayi]; //rastgele sayıların tutulacağı dizi
for (int i = 0; i < kac_sayi; ++i)
{
rast_dizi[i]= rd.Next(100, 1000);
}
if (hata_bayragi == true)
{
// label1.Text = " " + kac_sayi.ToString() + " Adet Rastgele Sayı Oluşturuldu!";
list_boxa_yazdir_1(rast_dizi);
}
else
{
//label1.Text = "Rastgele Sayılar Oluşturulamadı!";
}
bulunan_hafiza_boy = (int)asalbul(Convert.ToDouble(kac_sayi));
}
void list_boxa_yazdir_1(int[] dizi)
{
listBox1.Items.Clear();
for (int i = 0; i < dizi.Length ; ++i)
{
double asalsayim = asalbul(Convert.ToDouble(dizi.Length));
listBox1.Items.Add((i + 1).ToString() + "-) " + dizi[i].ToString()+" Mod " +asalsayim.ToString()+" = "+ (dizi[i]%asalsayim).ToString());
}
}
public double asalbul(double girilen)
{
double asalsayı = girilen+1;
double yuzde;
tekrarara:
for (int i = 2; i <= (int)Math.Sqrt(asalsayı); i++)
{
yuzde=Convert.ToDouble(kac_sayi)/Convert.ToDouble(asalsayı)*100;
if (asalsayı % i == 0)
{
asalsayı = asalsayı + 1;
goto tekrarara;
}
if (yuzde >= 92)
return asalbul(asalsayı);
}
return asalsayı;
}
private void button3_Click(object sender, EventArgs e)
{
//probe_sayisi_eisch = 0;
listBox2.Items.Clear();
eisch_yerlestir2();
for (int i = 0; i < bulunan_hafiza_boy; i++)
{
listBox2.Items.Add((i).ToString() + "-)" + eisch_hafiza2[i].ToString() + "--linki" + eisch_link2[i].ToString());
}
//++++++++++++++++
listBox6.Items.Clear();
int over_cizgisi2 = lich_yerlestir2();
for (int i = 0; i < lich_hafiza2.Length; i++)
{
if (i == over_cizgisi2)
listBox6.Items.Add("-------------------------------------"); //overflow area'yı ekranda gözüken listede bu çizgi ile ayırıyorum
listBox6.Items.Add((i).ToString() + "-)" + lich_hafiza2[i].ToString() + "--linki" + lich_hafiza_link2[i].ToString());
}
//++++++++++++++++
label2.Text = "Packing Factor= " + (Convert.ToDouble(kac_sayi) / asalbul(Convert.ToDouble(kac_sayi))).ToString();
label3.Text = "Hafıza Boyutu= " + bulunan_hafiza_boy.ToString();
listBox4.Items.Clear();
reisch_yerlestir();
for (int i = 0; i < bulunan_hafiza_boy; i++)
{
listBox4.Items.Add((i).ToString() + "-)" + reisch_hafiza[i].ToString() + "--linki" + reisch_link[i].ToString());
}
listBox5.Items.Clear();
blisch_yerlestir();
for (int i = 0; i < bulunan_hafiza_boy; i++)
{
listBox5.Items.Add((i).ToString() + "-)" + blisch_hafiza[i].ToString() + "--linki" + blisch_link[i].ToString());
}
labelları_doldur();
}
int[] eisch_hafiza2;
int[] eisch_link2;
public void eisch_yerlestir2()
{
eisch_hafiza2 = new int[(int)asalbul(Convert.ToDouble(rast_dizi.Length))];
eisch_link2 = new int[(int)asalbul(Convert.ToDouble(rast_dizi.Length))];
int sıra; //ilk değer rastgele olmuyor, o oluyor.
int kayıt_adr=rast_dizi.Length;
for (int i = 0; i < rast_dizi.Length; i++)
{
sıra = rast_dizi[i] % (bulunan_hafiza_boy); //hashing
if (eisch_hafiza2[sıra] == 0)//ilk hesaplanan adres boşsa
{
eisch_hafiza2[sıra] = rast_dizi[i];
}
else//ilk hesaplanan adres doluysa
{
if (eisch_link2[sıra] == 0) //ilk hesaplanan adresin kendisi dolu linki boşsa
{
if (eisch_hafiza2[kayıt_adr] == 0) //son kayıt boş ise hemen oraya kayıt yapılır.
{
eisch_hafiza2[kayıt_adr] = rast_dizi[i]; //kayıt yapılır
eisch_link2[sıra] = kayıt_adr;
}
else //boş değilse
{
while (eisch_hafiza2[kayıt_adr] != 0)kayıt_adr = kayıt_adr - 1;
eisch_hafiza2[kayıt_adr] = rast_dizi[i];
eisch_link2[sıra] = kayıt_adr; //kayıt yapılır
}
}
else//ilk hesaplanan adres dolu linki de dolu ise //linki boş olanı bulana kadar git
{
while (eisch_link2[sıra] != 0)
sıra = eisch_link2[sıra]; //while dan cıkıldığında artık sıra, linki boş bir adresi ifade eder.
//+++++++++++++++4
if (eisch_hafiza2[kayıt_adr] == 0) //son adres boş ise hemen oraya kayıt yapılır.
{
eisch_hafiza2[kayıt_adr] = rast_dizi[i]; //kayıt yapılır
eisch_link2[sıra] = kayıt_adr;
}
else //son adres boş değilse
{
//önce kayıt adresi bir azaltılır
while (eisch_hafiza2[kayıt_adr] != 0)kayıt_adr = kayıt_adr - 1;
eisch_hafiza2[kayıt_adr] = rast_dizi[i];
eisch_link2[sıra] = kayıt_adr; //kayıt yapılır
}
//++++++++++++++
}
}
}
}
void labelları_doldur() {
//packing factor:
label1.Text = (Convert.ToDouble( rast_dizi.Length) / lich_hafiza2.Length).ToString();
label13.Text = (Convert.ToDouble(rast_dizi.Length) / reisch_hafiza.Length).ToString();
label16.Text = (Convert.ToDouble(rast_dizi.Length )/ blisch_hafiza.Length).ToString();
//hafıza boyutları:
label4.Text=lich_hafiza2.Length.ToString();
label12.Text=reisch_hafiza.Length.ToString();
label15.Text=blisch_hafiza.Length.ToString();
//label3.Text += eisch_hafiza2.Length.ToString();
//hash değerleri
label17.Text=label14.Text=label11.Text=asalbul(Convert.ToDouble(textBox1.Text)).ToString();
label10.Text = lich_yerlestir2().ToString();
}
int[] lich_hafiza2;
int[] lich_hafiza_link2;
public int lich_yerlestir2()
{
int normal_kısım_boy = (int)((asalbul(Convert.ToDouble(textBox1.Text))) * 0.86);
int hash = normal_kısım_boy;
int lich_hafiza_boy2 = normal_kısım_boy;
int lich_over_boy2 = (int)(lich_hafiza_boy2 * 0.14);
lich_hafiza2 = new int[lich_hafiza_boy2 + lich_over_boy2];
lich_hafiza_link2 = new int[lich_hafiza_boy2 + lich_over_boy2];
for (int i = 0; i < rast_dizi.Length; i++) //kayıt edileceklerin her biri için for bir defa döner
{
int sıra2 = rast_dizi[i] % (hash) % normal_kısım_boy; //
int sondan_gel2 = lich_hafiza_boy2 + lich_over_boy2; //over'ın sonunun adresi
if (lich_hafiza2[sıra2] == 0) //ilk hesaplanan adres boşsa if e girer ve kaydı yapar.
{
lich_hafiza2[sıra2] = rast_dizi[i]; //burada linke bişey yazmaya gerek yoktur.
}
else //ilk hesaplanan adres boş değilse..
{ //overın sonuna bakacağız.
sondan_gel2 = sondan_gel2 - 1;
if (lich_hafiza2[sondan_gel2] == 0)//overın sonu bossa hemen oraya eklenir.
{
lich_hafiza2[sondan_gel2] = rast_dizi[i];
lich_hafiza_link2[sıra2] = sondan_gel2;
}
else //overın sonu bos değilse bir üste bakılır, taki boş bulunana kadar
{
while (lich_hafiza2[sondan_gel2] != 0)
{
sondan_gel2 = sondan_gel2 - 1;
}
lich_hafiza2[sondan_gel2] = rast_dizi[i];//bosluk bulunduğunda kayıt gerçekleştirilir.
//gerçekleştirilen kaydın adresi aslında olması gerektiği yerin linkine atanır.
lich_hafiza_link2[sıra2] = sondan_gel2;
}
//sondan gel adresi overflow alanı içindeyse linki kaydedilir, değilse linki tutulmaz.
// if (sondan_gel2 >= lich_hafiza_boy2)
lich_hafiza_link2[sıra2] = sondan_gel2;
}
}
return lich_hafiza_boy2;
}
int[] reisch_hafiza;
int[] reisch_link;
public void reisch_yerlestir()
{
reisch_hafiza = new int[(int)asalbul(Convert.ToDouble(textBox1.Text))];
reisch_link = new int[(int)asalbul(Convert.ToDouble(textBox1.Text))];
Random r_reisch = new Random();
int sıra; //ilk değer rastgele olmuyor, o oluyor.
int rastgele_yerlestir = r_reisch.Next(0, bulunan_hafiza_boy);
for (int i = 0; i < rast_dizi.Length; i++)
{
sıra = rast_dizi[i] % (bulunan_hafiza_boy); //hashing
if (reisch_hafiza[sıra] == 0)
{
reisch_hafiza[sıra] = rast_dizi[i];
}
else
{
if (reisch_link[sıra] != 0) //adresin linki boş değilse
{
while (reisch_link[sıra] == 0) //link de boş değilse linki boş olan adresi(sıra) arıyor//NOT:BU OLAYI ARARKEN DE YAPACAĞIZ
{
sıra = reisch_link[sıra]; //adresi linki boş olan ilk değer olarak belirler
}
}
while (reisch_hafiza[rastgele_yerlestir] != 0) //rastgele gidilen yer boş değilse boşu bulana kadar while döner
{
rastgele_yerlestir = r_reisch.Next(0, bulunan_hafiza_boy); //0 yerine sıra yapınca program cakılıyor.
}
reisch_hafiza[rastgele_yerlestir] = rast_dizi[i];
reisch_link[sıra] = rastgele_yerlestir;
}
}
}//end reisch method
public int probe_sayisi_blisch;
int[] blisch_hafiza;
int[] blisch_link;
public void blisch_yerlestir()
{
blisch_hafiza = new int[(int)asalbul(Convert.ToDouble(textBox1.Text))];
blisch_link = new int[(int)asalbul(Convert.ToDouble(textBox1.Text))];
int sıra;
int kayıt_adr_alt = bulunan_hafiza_boy-1; //tablonun son adresi//bulunan_hafiza_boy-1 'e de eşitlenebilirdi
int kayıt_adr_ust=0;
for (int i = 0; i < rast_dizi.Length; i++)
{
sıra = rast_dizi[i] % (bulunan_hafiza_boy); //hashing
if (blisch_hafiza[sıra] == 0) //adres boşsa
{
blisch_hafiza[sıra] = rast_dizi[i]; //kayıt yapılır.
}
else //ilk hesaplanan adres boş değlse
{
if (blisch_link[sıra] != 0) //adresin linki de boş değilse
{
while (blisch_link[sıra] == 0) //link de boş değilse linki boş olan adresi(sıra) arıyor//NOT:BU OLAYI ARARKEN DE YAPACAĞIZ
{
sıra = blisch_link[sıra]; //adresi linki boş olan ilk değer olarak belirler
}
}
//linki boş son adresi bulundu, şimdi kayıt yapılabilir.
bool kayit_bayragi_blisch = false;
for (; ; ) //breaklerle işi bitircem
{
etiket:
if (blisch_hafiza[kayıt_adr_ust] == 0) //en üstteki yer boşsa
{
blisch_hafiza[kayıt_adr_ust] = rast_dizi[i]; //kayıt yapılır
blisch_link[sıra] = kayıt_adr_ust;
kayit_bayragi_blisch = true;
break;
}
else//en üstteki boş değilse
{
kayıt_adr_ust = kayıt_adr_ust + 1; //ustun değeri 1 arttır
if (blisch_hafiza[kayıt_adr_alt] == 0) //ardından alta bak, alt boşsa kayıdı hemen yap
{
blisch_hafiza[kayıt_adr_alt] = rast_dizi[i]; //kayıt yapılır
blisch_link[sıra] = kayıt_adr_alt;
kayit_bayragi_blisch = true;
break;
}
else
{
kayıt_adr_alt = kayıt_adr_alt - 1; //değilse altı bir azalt
}
if (kayıt_adr_ust == kayıt_adr_alt)
{
MessageBox.Show("Blisch tablosu dolu, kayıt yapılamıyor");//burada bu hiç çalışmaz cunku boyutu girilen sayıya gore belirliyorum, ama yinede yazdım
break;
}
//goto etiket;
}
}
}
}
}
bool eisch_bool=true;
int probe_sayısı_eisch = 0;
void eisch_blisc_reisch_ara(int[] dizi_hafiza, int[] dizi_link, int aranan) //0 döndürürse bulamadı demek, 0 dan farklı dondururse o arananı buldu demek
{
probe_sayısı_eisch = 0;
int aranan2 = aranan;
int sıra = aranan2 % (int)asalbul(Convert.ToDouble(textBox1.Text));
eisch_bool = true;
do{
if (eisch_bool == false)
break;
probe_sayısı_eisch++;
if (dizi_hafiza[sıra] != 0 && eisch_bool == true) // adres boş değilse
{
if (dizi_hafiza[sıra] == aranan2) //arranan değer bulunduysa
{
eisch_bool = true;
break;
}
else //aranan değer bulunamadıysa
{
if (dizi_link[sıra] == 0) //aranan bulunamayıp linki boşsa
{
eisch_bool = false; //bişe bulamadı.
break;
}
else //aranan bulunamayıp linki boş değilse
{
sıra = dizi_link[sıra];
}
}
}
else //adres boşsa
{
eisch_bool = false;
break;
}
}
while (dizi_hafiza[sıra] != 0 && eisch_bool == true);
}
void lich_ara(int[] dizi_hafiza, int[] dizi_link, int aranan)
{
probe_sayısı_eisch = 0;
int aranan2 = aranan;
int hash = ((int)((asalbul(Convert.ToDouble(textBox1.Text))) * 0.86));
int sıra = aranan2%hash;
eisch_bool = true;
do{
if (eisch_bool == false)
break;
probe_sayısı_eisch++;
if (dizi_hafiza[sıra] != 0 && eisch_bool == true) // adres boş değilse
{
if (dizi_hafiza[sıra] == aranan2) //arranan değer bulunduysa
{
eisch_bool = true;
break;
}
else //aranan değer bulunamadıysa
{
if (dizi_link[sıra] == 0) //aranan bulunamayıp linki boşsa
{
eisch_bool = false; //bişe bulamadı.
break;
}
else //aranan bulunamayıp linki boş değilse
{
sıra = dizi_link[sıra]; //linke gittim, lichde linke 1 kere gidiliyor!!!!orda da yoksa ilk boşluğa kadar ya da en üzste kadar bakıyor.
if (dizi_hafiza[sıra] == 0)
{
eisch_bool = false; //bişe bulamadı.
break;
}
else
{
while (dizi_hafiza[sıra] == 0 || sıra == 0)
sıra = sıra - 1;//bir yukarı bakıyor.
}
}
}
}
else //adres boşsa
{
eisch_bool = false;
break;
}
}
while (dizi_hafiza[sıra] != 0 && eisch_bool == true);
}
private void button2_Click(object sender, EventArgs e)
{int istenen=Convert.ToInt32(textBox2.Text);
//try //EISCH YAZDIR
//{
eisch_blisc_reisch_ara(eisch_hafiza2,eisch_link2, istenen);
bool bulundu_mu = eisch_bool;
if (eisch_bool==false) label18.Text = "aranan bulunamadı\nprobe sayısı= " + probe_sayısı_eisch.ToString();
else { label18.Text = "aranan bulundu\nprobe sayısı= " + probe_sayısı_eisch.ToString(); }
//}
//catch (Exception ex) { label18.Text = "aranan bulunamadı\nprobe sayısı= " + probe_sayısı_eisch.ToString(); }
// reisch_ara(rast_dizi, Convert.ToInt32(textBox2.Text));
eisch_blisc_reisch_ara(reisch_hafiza, reisch_link, istenen);
if (bulundu_mu==false) label24.Text = "aranan bulunamadı\nprobe sayısı= " + probe_sayısı_eisch.ToString();
else { label24.Text = "aranan bulundu\nprobe sayısı= " + probe_sayısı_eisch.ToString(); }
//blisch yazdır
eisch_blisc_reisch_ara(blisch_hafiza, blisch_link, istenen);
if (bulundu_mu == false) label25.Text = "aranan bulunamadı\nprobe sayısı= " + probe_sayısı_eisch.ToString();
else { label25.Text = "aranan bulundu\nprobe sayısı= " + probe_sayısı_eisch.ToString(); }
//lich yazdır
lich_ara(lich_hafiza2, lich_hafiza_link2, istenen);
if (eisch_bool == false) label23.Text = "aranan bulunamadı\nprobe sayısı= " + probe_sayısı_eisch.ToString();
else { label23.Text = "aranan bulundu\nprobe sayısı= " + probe_sayısı_eisch.ToString(); }
}
}
}
