https://buraksenyurt.com/Burak Selim Şenyurt - Data Structures, Algorithms2019-10-27T11:03:14+00:00Matematik Mühendisi Bir Bilgisayar Programcısının NotlarıBurak Selim SenyurtBlogEngine.Net Syndication Generatorhttps://buraksenyurt.com/opml.axdBurak Selim SenyurtMatematik Mühendisi Bir Bilgisayar Programcısının Notlarıtr-TRBurak Selim Şenyurt0.0000000.000000https://buraksenyurt.com/post/Sorting-Algorithm-SpeedsSıralama Algoritmaları - Hangisi Daha Hızlı (Bubble, Quick, Insertion, Selection, Shell, Merge, Heap)2013-09-24T14:08:00+00:00bsenyurt<p><a href="https://buraksenyurt.com/pics/Sorting_1.jpg"><img style="float: right; margin: 4px 0px; display: inline;" title="Sorting_1" src="/pics/Sorting_1_thumb.jpg" alt="Sorting_1" width="300" height="222" align="right" /></a>Merhaba Arkadaşlar,</p>
<p>Evimdeki çalışma odasında yer alan kütüphanemi zaman zaman gelen yeni kitaplar ve afacan S(h)arp Efe' nin haylazlıkları nedeni ile darma duman halde bulabiliyorum. Hal böyle olunca çoğu zaman kitaplıkta yer alan onlarca kitabı tekrardan düzenlemem ve uygun bir sırada dizmem gerekebiliyor. Hatta bunu kitapların tozunu almak için hepsini yerlere indirdikten sonra da yaşayabiliyorum. Aslına bakarsanız her seferinde farklı bir kategorilendirme yapıyor ve buna göre bir sıralama işlemi icra etmeye çalışıyorum. Tabi el çabukluğu dışında akıllı düşününce sıralamak ve yerleştirmek kısa sürede bitebiliyor. Ama bazen de kafa bulanık olunca bu işlem sandığımdan da uzun sürüp bir işkence haline gelebiliyor.</p>
<p>Üniversite yıllarında özellikle programlama derslerinde buna benzer şekilde sıralama algoritmaları ile haşır neşir olmayanımız yoktur eminim ki. Hatta çoğu sınavın korkulu rüyası sorularının kaynağını teşkil etmektedir ki hocalarımız genellikle bunları kağıt kalem kullanarak çözmemizi isterler<em>(En azından benim zamanında böyleydi)</em></p>
<p>Özellikle bu algoritmaların dil bağımsız olan <strong>Pseudo Code </strong>içeriklerinden yararlanarak her hangi bir dile uygulanmaya çalışılması üzerine epeyce kafa yormuşuzdur. <strong>C, C++, Java, Basic, Pascal </strong>ve benzeri temel programlama derslerinde edindiğimiz bilgiler ile bu algoritmaları yazmak için çokça uğraşmışızdır. Tabi üzülerek söylemeliyim ki ben üniversite yıllarındayken <strong>Bubble </strong>ve <strong>Quick Sort </strong>sıralama algoritmalarından fazlasını ne yazık ki göremedim.</p>
<p>Dolayısıyla o zamanlarda iş başa düşmüş ve diğer algoritmaları kendi başıma araştırıp öğrenmeye çalışmıştım. Çok şükür ki günümüzde Internet elimizin altında ve her ne kadar bilgi kirliliği olması söz konusu ise de her çeşit bilgiye kolayca ulaşmamız mümkün. Dolayısıyla sıralama algoritmalarının fazlasını herhangibir dil için kolayca bulabiliyoruz.</p>
<p>Gelelim bu yazımızın konusuna. Geçtiğimiz günlerde yine boş anlarıma denk gelen bir zaman diliminde, sıralama algoritmaları arasındaki hız farklarını incelemeye çalışmaktaydım. İş bir süre sonra <strong>Console </strong>uygulamasının <strong>Main </strong>metodu içerisine hapsolmanın ötesine geçti. Dilerseniz hiç vakit kaybetmeden kodlarımızı değerlendirmeye başlayalım. Amacımız bir performans test uygulaması geliştirmek olacak.</p>
<p>Ele almayı düşündüğüm bir kaç sıralama algoritması söz konusu idi. Kimisinin yazımı oldukça kolay, kimisin ise inanılmaz karmaşıktı. Örnekte <strong>Bubble, Heap, Insertion, Merge, Quick, Selection </strong>ve <strong>Shell </strong>sıralama algoritmalarını ele aldım. Aslında amacım algoritmaların yazılmasından ziyade, bunları aynı dizi içerikleri ile test edebilmenin kolay bir yolunu bulmaktı. Bu noktada aklımdaki yapıda tek bir <strong>Execute </strong>metodunun, kendisine parametre olarak gelen herhangibir sıralama algoritmasını, belli bir dizi için yapması gerektiğini düşünmekteydim. Bu tip bir test ortamını kurmak çok zor değildir aslında. Aynı metodun kendisine parametre olarak gelen herhangibir sıralama algoritmasını icra etmesini planlıyorsak bir <strong>arayüz(Interface) </strong>tipinden yararlanabiliriz.</p>
<blockquote>
<p>Hatırlayacağınız üzere<em>(Hatta hatırlamanız gerektiği üzere)</em> <strong>Interface' </strong>ler ile, kendilerini uygulayan diğer tiplere icra etmesi gereken zorunlulukları bildirebilir ve diğer yandan çok biçimli olarak hareket etmelerini sağlayabiliriz. <em>(Özellikle <strong>Plug-In </strong>tabanlı programlamada çok işe yaradığını unutmayalım) </em></p>
</blockquote>
<p>Örneğimizde son derece basit bir arayüz tipi kullanılmaktadır. Aşağıdaki kod parçasında görüldüğü gibi.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">namespace SortingAlgorithm
{
public interface ISorter
{
string Description { get; }
void Execute(int[] Array);
}
}</pre>
<p><strong>ISorter </strong>arayüz tipi basit olarak iki <strong>üye(Member)</strong> bildirimi içermektedir. <strong>Execute </strong>metodu parametre olarak gelen <strong>Array </strong>dizisi üzerinde uygulanacak sıralama işlemini icra eden fonksiyon bildirimidir. Diğer yandan <strong>Description </strong>özelliği ile de sıralama algoritması için kısa bir açıklama verilmesi sağlanabilir. Dolayısıyla sıralama işlerini üstlenecek olan tiplerin bu arayüzü uygulamasını sağlayarak yola devam edebiliriz. <em>(Hem de tüm sıralama algoritmalarının C# tarafındaki kod karşılıklarını tek bir yazı içerisinde toplamış oluruz)</em> Öyleyse hiç vakit kaybetmeden sıralama algoritma tiplerini yazmaya başlayalım.</p>
<h2><strong>Bubble Sort</strong></h2>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">namespace SortingAlgorithm.Sorters
{
public class Bubble
:ISorter
{
#region ISorter Members
public string Description
{
get { return "Bubble Sort Sıralama Algoritması"; }
}
public void Execute(int[] Array)
{
int i;
int j;
int TempValue;
for (i = (Array.Length - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (Array[j - 1] > Array[j])
{
TempValue = Array[j - 1];
Array[j - 1] = Array[j];
Array[j] = TempValue;
}
}
}
}
#endregion
}
}</pre>
<h2><strong>Quick Sort</strong></h2>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">namespace SortingAlgorithm.Sorters
{
public class Quick
:ISorter
{
#region ISorter Members
public string Description
{
get { return "Quick Sort Sıralama Algoritması"; }
}
public void Execute(int[] Array)
{
Sort(0, Array.Length - 1,Array);
}
#endregion
private void Sort(int LeftValue, int RightValue,int[] Array)
{
int PivotValue, LeftHoldValue, RightHoldValue;
LeftHoldValue = LeftValue;
RightHoldValue = RightValue;
PivotValue = Array[LeftValue];
while (LeftValue < RightValue)
{
while ((Array[RightValue] >= PivotValue) && (LeftValue < RightValue))
{
RightValue--;
}
if (LeftValue != RightValue)
{
Array[LeftValue] = Array[RightValue];
LeftValue++;
}
while ((Array[LeftValue] <= PivotValue) && (LeftValue < RightValue))
{
LeftValue++;
}
if (LeftValue != RightValue)
{
Array[RightValue] = Array[LeftValue];
RightValue--;
}
}
Array[LeftValue] = PivotValue;
PivotValue = LeftValue;
LeftValue = LeftHoldValue;
RightValue = RightHoldValue;
if (LeftValue < PivotValue)
{
Sort(LeftValue, PivotValue - 1,Array);
}
if (RightValue > PivotValue)
{
Sort(PivotValue + 1, RightValue,Array);
}
}
}
}</pre>
<h2><strong>Insertion Sort</strong></h2>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">namespace SortingAlgorithm.Sorters
{
public class Insertion
: ISorter
{
#region Sorter Members
public string Description
{
get { return "Insertion Sort Sıralama Algoritması"; }
}
public void Execute(int[] Array)
{
int i;
int j;
int IndexValue;
for (i = 1; i < Array.Length; i++)
{
IndexValue = Array[i];
j = i;
while ((j > 0) && (Array[j - 1] > IndexValue))
{
Array[j] = Array[j - 1];
j = j - 1;
}
Array[j] = IndexValue;
}
}
#endregion
}
}</pre>
<h2><strong>Selection Sort</strong></h2>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">namespace SortingAlgorithm.Sorters
{
public class Selection
:ISorter
{
#region ISorter Members
public string Description
{
get { return "Selection Sıralama Algoritması"; }
}
public void Execute(int[] Array)
{
int i, j;
int MinValue, TempValue;
for (i = 0; i < Array.Length - 1; i++)
{
MinValue = i;
for (j = i + 1; j < Array.Length; j++)
{
if (Array[j] < Array[MinValue])
{
MinValue = j;
}
}
TempValue = Array[i];
Array[i] = Array[MinValue];
Array[MinValue] = TempValue;
}
}
#endregion
}
}</pre>
<h2><strong>Shell Sort</strong></h2>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">namespace SortingAlgorithm.Sorters
{
public class Shell
:ISorter
{
#region ISorter Members
public string Description
{
get { return "Shell Sıralama Algoritması"; }
}
public void Execute(int[] Array)
{
int i, j, Increment, TempValue;
Increment = 3;
while (Increment > 0)
{
for (i = 0; i < Array.Length; i++)
{
j = i;
TempValue = Array[i];
while ((j >= Increment) && (Array[j - Increment] > TempValue))
{
Array[j] = Array[j - Increment];
j = j - Increment;
}
Array[j] = TempValue;
}
if (Increment / 2 != 0)
{
Increment = Increment / 2;
}
else if (Increment == 1)
{
Increment = 0;
}
else
{
Increment = 1;
}
}
}
#endregion
}
}</pre>
<h2><strong>Merge Sort</strong></h2>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">namespace SortingAlgorithm.Sorters
{
public class Merge
:ISorter
{
int[] Array2;
#region ISorter Members
public string Description
{
get { return "Merge Sıralama Algoritması"; }
}
public void Execute(int[] Array)
{
Array2 = new int[Array.Length];
Sort(0, Array.Length - 1,Array);
}
#endregion
private void Sort(int LeftValue, int RightValue,int[] Array)
{
int mid;
if (RightValue > LeftValue)
{
mid = (RightValue + LeftValue) / 2;
Sort(LeftValue, mid,Array);
Sort(mid + 1, RightValue,Array);
DoMerge(LeftValue, mid + 1, RightValue,Array);
}
}
private void DoMerge(int LeftValue, int MiddleValue, int RightValue,int[] Array)
{
int i, LeftEnd, NumberOfElements, TempPosition;
LeftEnd = MiddleValue - 1;
TempPosition = LeftValue;
NumberOfElements = RightValue - LeftValue + 1;
while ((LeftValue <= LeftEnd) && (MiddleValue <= RightValue))
{
if (Array2[LeftValue] <= Array[MiddleValue])
{
Array2[TempPosition] = Array[LeftValue];
TempPosition = TempPosition + 1;
LeftValue = LeftValue + 1;
}
else
{
Array2[TempPosition] = Array[MiddleValue];
TempPosition = TempPosition + 1;
MiddleValue = MiddleValue + 1;
}
}
while (LeftValue <= LeftEnd)
{
Array2[TempPosition] = Array[LeftValue];
LeftValue = LeftValue + 1;
TempPosition = TempPosition + 1;
}
while (MiddleValue <= RightValue)
{
Array2[TempPosition] = Array[MiddleValue];
MiddleValue = MiddleValue + 1;
TempPosition = TempPosition + 1;
}
for (i = 0; i < NumberOfElements; i++)
{
Array[RightValue] = Array2[RightValue];
RightValue = RightValue - 1;
}
}
}
}</pre>
<h2><strong>Heap Sort</strong></h2>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">namespace SortingAlgorithm.Sorters
{
public class Heap
:ISorter
{
#region ISorter Members
public string Description
{
get { return "Heap Sıralama Algoritması"; }
}
public void Execute(int[] Array)
{
for (int i=(Array.Length-1)/2; i >= 0;i--)
Adjust (Array, i, Array.Length - 1);
for (int i = Array.Length - 1; i >= 1; i--)
{
int Temp = Array[0];
Array[0] = Array[i];
Array[i] = Temp;
Adjust (Array, 0, i - 1);
}
}
#endregion
private void Adjust(int[] Array, int i, int m)
{
int TempValue = Array[i];
int j = i * 2 + 1;
while (j <= m)
{
if (j < m)
if (Array[j] < Array[j + 1])
j = j + 1;
if (TempValue < Array[j])
{
Array[i] = Array[j];
i = j;
j = 2 * i + 1;
}
else
{
j = m + 1;
}
}
Array[i] = TempValue;
}
}
}</pre>
<p>Vowwww!!! Ne çok kod, ne çok algoritma, ne çok matematik...</p>
<p>Örneğimizde bir de Performans testini gerçekleştirecek yardımcı bir tipe ihtiyacımız olacaktır. Bu sınıfı da aşağıdaki gibi tasarladığımızı düşünebiliriz.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Diagnostics;
using System.IO;
namespace SortingAlgorithm
{
public class PerformanceTester
{
public void Execute(ISorter Sorter, int[] Array)
{
Stopwatch watcher = new Stopwatch();
watcher.Start();
Sorter.Execute(Array);
watcher.Stop();
File.AppendAllText(
Path.Combine(Environment.CurrentDirectory, "ExecutionLog.txt")
, String.Format("{0} Sıralama Algoritması için Toplam Çalışma Süresi : {1} milisaniyedir. Dizi boyutu {2}|"
, Sorter.Description
, watcher.ElapsedMilliseconds.ToString()
,Array.Length)
);
}
}
}</pre>
<p><strong>Execute </strong>metoduna dikkat edilecek olursa <strong>ISorter </strong>interface tipinden bir parametre aldığı görülmektedir. Dolayısıyla bu metoda, yukarıda tanımlanmış olan sıralama sınıflarından herhangibiri atanabilir. Çünkü hepsi bu <strong>arayüzü(Interface)</strong> implemente etmektedir. Diğer yandan <strong>Execute </strong>metodu,<strong> çalışma zamanında(Runtime), Sorter </strong>isimli değişkenin büründüğü sıralama sınıfının <strong>Execute </strong>metodunu yürütmekte ve ayrıca bu sıralama algoritması için bir <strong>Text </strong>dosyaya <strong>log </strong>atmaktadır. Metodumuzun önemli özelliklerinden birisi de, <strong>Stopwatch </strong>tipini kullanarak sıralama işlemi için gerekli çalışma süresi farkını hesaplıyor ve bunu yine <strong>Text </strong>dosyası içerisine raporluyor olmasıdır.</p>
<h1>Uygulamanın Testi</h1>
<p>Örnek uygulamamız aslında bir <strong>Test </strong>uygulamasıdır. Amacı çeşitli sıralama algoritmalarını, içerikleri karışık tamsayılardan oluşan birden fazla boyuttaki dizi için çalıştırmak ve çalışma zamanındaki toplam icra süresi farklarını görmektir. Dolayısıyla bize yardımcı bir kaç fonksiyonellik daha gerekmektedir. Örneğin belirtilen boyutta rastgele <strong>int </strong>tipinde sayılardan oluşacak bir dizi üretimi fonksiyonelliği ve hatta bu dizinin ham ve sıralanmış hallerinin karşılıklarını yine <strong>log </strong>amaçlı olarak <strong>Text </strong>dosyasına yazdıracak bir metod düşünülebilir. Bunun için uygulamamıza <strong>Utility </strong>isimli <strong>static </strong>bir tip ilave edebiliriz.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.IO;
using System.Text;
namespace SortingAlgorithm
{
public static class Utility
{
public static int[] GenerateRandomNumbers(int Size)
{
int[] numbers = new int[Size];
Random rnd = new Random();
for (int i = 0; i < Size; i++)
{
numbers[i] = rnd.Next(1, Size);
}
return numbers;
}
public static void WriteLog(int[] Array)
{
StringBuilder builder = new StringBuilder();
foreach (int element in Array)
{
builder.AppendLine(String.Format("{0} ", element.ToString()));
}
File.AppendAllText(
Path.Combine(Environment.CurrentDirectory, "ExecutionLog.txt")
, builder.ToString()
);
}
}
}</pre>
<p><strong>GenerateRandomNumbers </strong>metodu testler için gerekli <strong>n boyutlu int tipinden dizi</strong> üretimini üstlenmektedir. Söz konusu kobay diziler rastgele <strong>int </strong>sayılarından oluşmaktadır. Diğer yandan <strong>WriteLog </strong>metodu' da <strong>int </strong>tipinden herhangibir dizinin içeriğini<em>(Sıralı veya değil) </em><strong>ExecutionLog </strong>isimli text tabanlı dosyaya yazmaktadır.Buraya kadar yazmış olduğumuz tipleri aşağıdaki sınıf diagramında daha net bir şekilde görebilirsiniz.</p>
<p><a href="https://buraksenyurt.com/pics/Sorting_2.gif"><img style="margin: 4px 0px; display: inline;" title="Sorting_2" src="/pics/Sorting_2_thumb.gif" alt="Sorting_2" width="640" height="748" /></a></p>
<p>Artık yazmış olduğumuz tipleri kullanarak ilgili test işlemlerini gerçekleştirecek olan uygulama kodunu geliştirmeye başlayabiliriz.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.IO;
using SortingAlgorithm.Sorters;
namespace SortingAlgorithm
{
class Program
{
#region Program değişlenleri
static PerformanceTester neco = new PerformanceTester();
static Insertion insertion = new Insertion();
static Bubble bubble = new Bubble();
static Heap heap = new Heap();
static Quick quick = new Quick();
static Selection selection = new Selection();
static Shell shell = new Shell();
static Merge merge = new Merge();
static Tuple<int[], int[], int[], int[], int[], int[], int[]> numbers;
#endregion
static void Main(string[] args)
{
Console.WriteLine("Testler başladı. Lütfen bekleyiniz");
numbers = Load(100);
Execute(numbers);
numbers = Load(500);
Execute(numbers);
numbers = Load(1000);
Execute(numbers);
numbers = Load(5000);
Execute(numbers);
numbers = Load(10000);
Execute(numbers);
numbers = Load(50000);
Execute(numbers);
numbers = Load(100000);
Execute(numbers);
numbers = Load(500000);
Execute(numbers);
Console.WriteLine("Testler tamamlandı. {0}");
string Result = File.ReadAllText(Path.Combine(Environment.CurrentDirectory, "ExecutionLog.txt"));
Console.WriteLine(Result);
}
private static Tuple<int[], int[], int[], int[], int[], int[], int[]> Load(int MaxValue)
{
int[] randomNumbers = Utility.GenerateRandomNumbers(MaxValue);
numbers = new Tuple<int[], int[], int[], int[], int[], int[], int[]>(
randomNumbers
, (int[])randomNumbers.Clone()
, (int[])randomNumbers.Clone()
, (int[])randomNumbers.Clone()
, (int[])randomNumbers.Clone()
, (int[])randomNumbers.Clone()
, (int[])randomNumbers.Clone()
);
return numbers;
}
private static void Execute(Tuple<int[], int[], int[], int[], int[], int[], int[]> numbers)
{
neco.Execute(bubble,numbers.Item1);
neco.Execute(heap, numbers.Item2);
neco.Execute(insertion, numbers.Item3);
neco.Execute(merge, numbers.Item4);
neco.Execute(quick, numbers.Item5);
neco.Execute(selection, numbers.Item6);
neco.Execute(shell, numbers.Item7);
}
}
}</pre>
<p>Program kodumuzda kritik olan noktalardan birisi, üretilen 7 adet dizinin <strong>Tuple<> </strong>tipine yüklenişi sırasında ortaya çıkmaktadır. Diziler bildiğiniz üzere referans tipleridir. Dolayısıyla bir metoda parametre olarak atandıklarında ve içeride değişikliğe uğradıklarında, bu metodun çağırıldığı yerdeki orjinal dizinin içeriğinin de değişmesi söz konusudur. Çünkü her ikiside zaten aynı adresi işaret eden bir pointer' dır. Bu sebepten <strong>Tuple<> </strong>içerisindeki dizileri set ederken klonlamamız gerekmektedir. Aksi durumda ilk dizinin sıralanmasını takiben diğer metodların kullanacağı tüm dizilerin zaten sıralanmış olarak işleme alındığı görülecektir.</p>
<p>Demek ki basit bir Performans Test uygulaması yazarken dahi çok dikkali davranmalı ve özellikle Debug işlemlerine ağırlık vermeliyiz.</p>
<h1>Sonuçlar</h1>
<p>Artık uygulamamızı çalıştırabilir ve sonuçları irdeleyebiliriz. Dizilerimize ait değer aralıkları <strong>100, 500, 1000 , 5000, 10000, 50000 ve 100000' </strong>dir. Çok doğal olarak son değer aralıklarının büyüklüğü nedeni ile uygulama ilgili sıralama algoritmalarını oldukça zorlayacaktır ki bu istediklerimizden birisidir. Ben şahsen uygulamayı denediğimde bir kaç saat çalıştığına şahit oldum. Tabi burada işi yavaşlatan farklı faktörler ve etkenlerde var. Ancak sonuç olarak aşağıdaki test değerlerini elde ettim.</p>
<p><a href="https://buraksenyurt.com/pics/Sorting_3.gif"><img style="margin: 4px 0px; display: inline;" title="Sorting_3" src="/pics/Sorting_3_thumb.gif" alt="Sorting_3" width="544" height="787" /></a></p>
<p>Görüldüğü üzere değer aralığı büyüdükçe en hızlı sonuçlar <strong>Quick Sort </strong>algoritmasından gelmektedir. Diğer yandan <strong>Bubble Sort </strong>algoritmasının çok fazla maliyet getirdiği ve uzun sürdüğü ortadadır. <strong>Heap</strong> ve <strong>Merge </strong>algoritmaları birbirlerine yakın süreler vermiştir. Insertion, Selection ve Shell algoritmaları tatmin edici hızlarda değildir. Tabi buradaki süreler <strong>Milisaniye </strong>cinsinden olup alsında çok fazla önemli görünmeyebilir. Ancak matematiksel hesaplamaların yoğun yapıldığı bilimsel uygulamalarda sıklıkla kullanıldıkları ve ihtiyaç duyuldukları da bilinmektedir.</p>
<p>Elbette çok daha etkili ve faydalı bir test uygulaması yazılabilir. Mesela <strong><a href="http://www.sorting-algorithms.com">http://www.sorting-algorithms.com</a> </strong>adresinde bunun web tabanlı güzel bir örneği bulunmaktadır. Diğer yandan akılda oluşması gereken önemli sorulardan birisi de şudur. Acaba bu sıralamaların paralelize edilmiş versiyonları var mıdır? Olay sadece <strong>Parallel.ForEach</strong> veya <strong>Parallel.For</strong> metodlarını kullanmak kadar basit olabilir mi? Yoksa dikkat edilmesi gereken başka unsurlar da var mıdır? Bu soruların cevaplarını ilerleyen yazılarımızda bulmaya çalışıyor olacağız. Diğer yandan bu yazımızda sadece kullandığımız sıralama algoritmaları hakkında en iyi bilgilere wikipedia üzerinden ulaşabilirsiniz.(<a title="Bubble Sort" href="http://en.wikipedia.org/wiki/Bubble_sort" target="_blank">Bubble Sort</a>, <a title="Insertion Sort" href="http://en.wikipedia.org/wiki/Insertion_sort" target="_blank">Insertion Sort</a>, <a title="Selection Sort" href="http://en.wikipedia.org/wiki/Selection_sort" target="_blank">Selection Sort</a>, <a title="Heap Sort" href="http://en.wikipedia.org/wiki/Heapsort" target="_blank">Heap Sort</a>, <a title="Quick Sort" href="http://en.wikipedia.org/wiki/Quicksort" target="_blank">Quick Sort</a>, <a title="Merge Sort" href="http://en.wikipedia.org/wiki/Merge_sort" target="_blank">Merge Sort</a>, <a title="Shell Sort" href="http://en.wikipedia.org/wiki/Shell_sort" target="_blank">Shell Sort</a>) Tekrardan görüşünceye dek hepinize mutlu günler dilerim.</p>
<p><a href="https://buraksenyurt.com/pics/2011%2f11%2fSortingAlgorithm.rar">SortingAlgorithm.rar (40,36 kb)</a></p>2013-09-24T14:08:00+00:00c#sıralama algoritmalarıquick sortheap sortmerge sortselection sortinsertion sortshell sortbubble sortalgoritmasorting algorithmc# temelleribsenyurtÖzellikle bu algoritmaların dil bağımsız olan Pseudo Code içeriklerinden yararlanarak her hangi bir dile uygulanmaya çalışılması üzerine epeyce kafa yormuşuzdur. C, C++, Java, Basic, Pascal ve benzeri temel programlama derslerinde edindiğimiz bilgiler ile bu algoritmaları yazmak için çokça uğraşmışızdır. Tabi üzülerek söylemeliyim ki ben üniversite yıllarındayken Bubble ve Quick Sort sıralama algoritmalarından fazlasını ne yazık ki göremedim.https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=41c84bbd-cf51-4786-b205-1393b914086d4https://buraksenyurt.com/trackback.axd?id=41c84bbd-cf51-4786-b205-1393b914086dhttps://buraksenyurt.com/post/Sorting-Algorithm-Speeds#commenthttps://buraksenyurt.com/syndication.axd?post=41c84bbd-cf51-4786-b205-1393b914086dhttps://buraksenyurt.com/post/En-Kisa-Metni-BulmakEn Kısa Metni Bulmak2013-09-01T20:45:00+00:00bsenyurt<p><img style="float: right;" src="/pics/2012%2f1%2f205735_getting_the_last_word.jpg" alt="" />Merhaba Arkadaşlar,</p>
<p>Uzun zamandır makale yazmaya çalışmakta ve öğrendiklerimi, edindiğim tecrübeleri sizlere aktarmaktayım. Tabi zaman ilerledikçe yazacak konu bulmakta da bir hayli zorlanıyor insan. Bu noktada öğrenmeninin sınırının olmadığını hepimiz biliyoruz. Olaya bu açıdan baktığımızda yazılmaya ve araştırılmaya değer binlerce konu olduğunu gönül rahatlığıyla ifade edebilirim. Yazma hevesli bir birey olarak bu benim için gerçekten önemli <img title="Smile" src="/editors/tiny_mce3/plugins/emotions/img/smiley-smile.gif" alt="Smile" border="0" /></p>
<p>İşte geçtiğimiz hafta içerisinde de Internet üzerinden araştırma yaparken enteresan bir konu ile karşılaştım. Aslında konuyu isimlendirmek oldukça zor ama bir optimizasyon işlemi olduğunu ifade edebilirim. Sorun n sayıda kelimenin saklanmak istendiği bir durumda ortaya çıkıyor. İstenen, bu kelimeleri birleştirerek saklamak ancak bunu yaparkende olabilecek en kısa cümleyi elde ederek ilgili depolama işlemini gerçekleştirmek. Öyleki, üretilen cümle hem çok kısa olmalı hem de tüm kelimeleri içermeli.</p>
<p>Dilerseniz önce sorunu ve ulaşmak istediğimiz hedefi bir örnek üzerinden ifade etmeye çalışalım. Elimizde 4 adet kelime olduğunu farz edelim. <strong>Enginar, Arpa, Keten </strong>ve <strong>Paket</strong>. Normal şartlarda bu 4 kelimeyi sırasız olarak birleştirirsek aşağıdaki gibi bir <strong>string </strong>katarının oluştuğunu görürüz.</p>
<p><strong>EnginarArpaKetenPaket</strong></p>
<p>Bu son derece doğal bir sonuç tabi <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /> Ancak amacımız bu metni mümkün olduğu kadar kısaltmak. Peki bunu nasıl yapabiliriz?</p>
<p>Aslına bakarsanız bir şekilde kelimeler arasındaki ilişkileri matematiksel olarak anlamlandırmak ve olabilecek en iyi kombinasyonları seçerek ilerlemeye çalışmak yerinde olacaktır. Bunu düşünerek <strong>Paket </strong>ile <strong>Keten </strong>kelimelerini göz önüne alalım.</p>
<p><img src="/pics/2012%2f1%2fko_1.png" alt="" /></p>
<p>Dikkat edileceği üzere <strong>paket </strong>ile <strong>keten </strong>kelimelerini yan yana getirdiğimizde, <strong>KET </strong>hecesinin ortak olmasından dolayı <strong>paketen </strong>şeklinde daha kısa bir birleşim elde etmiş durumdayız. Ancak önce keten sonra paket kelimesini yan yana getirirsek, bu durumda bir kısaltma söz konusu olmayacaktır.</p>
<p><img src="/pics/2012%2f1%2fko_2.png" alt="" /></p>
<p>Dolayısıyla paket ile keten kelimeleri arasındaki ilişkiyi sayısal olarak anlamlandırmaya çalıştığımızda şunları söyleyebiliriz.</p>
<ul>
<li><strong>Keten Paket </strong>sırası düşünüldüğünde arada hiç ortak birleşim harfi veya hecesi yoktur. Dolayısıyla <strong>Keten </strong>kelimesinden <strong>Paket </strong>kelimesine geçişinin değeri <strong>0 </strong>olarak nitelendirilebilir.</li>
<li><strong>Paket Keten </strong>sırasına baktığımızda ise, <strong>ket </strong>hecesinin ortak olduğu bir durum söz konusudur. <strong>ket </strong>hecesi teke indirgendiğinde, iki kelime birleşimi önemli ölçüde kısaltılmış olmaktadır. Buna göre <strong>Paket </strong>kelimesinden <strong>Keten </strong>kelimesine geçişin maliyeti <strong>3</strong> olarak düşünülebilir<em>(3 harfli bir kısım kesilmiş olduğu için)</em></li>
</ul>
<p>Diğer kelimeleri de göz önüne alarak devam edelim. İlk olarak <strong>Arpa </strong>ile <strong>Paket</strong>' e bir bakalım. Yukarıdaki tekniği göz önüne alacak olursak aşağıdaki görsellerde yer alan ilişkileri kurabiliriz.</p>
<p><img src="/pics/2012%2f1%2fko_3.png" alt="" /></p>
<p>Buna göre <strong>paket </strong>-> <strong>arpa </strong>geçişinin değeri <strong>0 </strong>iken, <strong>arpa </strong>-> <strong>paket </strong>geçişinin değeri <strong>pa </strong>hecesinin değişmesi nedeniyle <strong>2 </strong>olarak hesaplanabilir.</p>
<p>Şimdi de <strong>Enginar</strong>, <strong>Arpa </strong>ve <strong>Keten </strong>kelimeleri arasındaki ilişkiye bir bakalım. Çünkü bu 3 kelime arasında aynı değerlere sahip bir ilişki durumu söz konusudur. Aşağıdaki şekilde bu durum ifade edilmeye çalışılmıştır.</p>
<p><img src="/admin/app/..http:/www.buraksenyurt.com/pics/2012%2f1%2fko_4n.png" alt="" /></p>
<p>Burada <strong>enginar </strong>-> <strong>arpa </strong>birleşimi ile <strong>keten </strong>-> <strong>enginar </strong>birleşimlerinin sayısal ağırlıkları aynıdır(2). Karar vermek çok önemli değildir aslında. Nitekim ağırlık puanları eşittir ve iki birleşiminde tüm sözcük dizimine etkisi aynı olacaktır. Elimizde bulunan 4 kelimeyi ve aralarındaki ilişkileri düşündüğümüzde aşağıdaki şekilde olduğu gibi bir ağırlıklandırma yapabiliriz.</p>
<p><img src="/pics/2012%2f1%2fko_5.png" alt="" /></p>
<p>Sanırım bu şekil yardımıyla kelimeler arasındaki ilişkileri daha net görebilmekteyiz. Biraz renkli oldu ama olsun <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /> Sonuç olarak aşağıdaki iki kelime katarından birisini üretebiliriz.</p>
<p><strong>arpaketenginar</strong></p>
<p>veya</p>
<p><strong>enginarpaketen</strong></p>
<p><img src="/pics/2012%2f1%2fko_6.png" alt="" /></p>
<p>Herşey iyi güzel. Kafamızda kelimeleri bir şekilde birbirlerine bağladık. Peki ama bunun kodlamasını nasıl yapacağız?<img title="Undecided" src="/editors/tiny_mce3/plugins/emotions/img/smiley-undecided.gif" alt="Undecided" border="0" /> Sonuçta en önemli nokta aslında bu sıkıştırma şeklini bir şekilde kod tarafında üretebilmemizdir. İşe ufak bebek adımları ile başlamakta yarar var. Örneğin çok temel bir <strong>genişletme metodu(Extension Method)</strong> ile iki <strong>string</strong>' i ağırlık derecesine göre uygun bir biçimde birleştirmeyi düşünelim. İşte kod parçamız.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Linq;
using System.Collections.Generic;
namespace EnKisaCumle
{
class Program
{
static void Main(string[] args)
{
string[] words = { "Paket", "KETEN", "EngiNar", "arPA","demir" };
Console.WriteLine("{0} ile {1} için {2}",words[0],words[1], words[0].Combine(words[1]));
Console.WriteLine("{0} ile {1} için {2}",words[0], words[2], words[0].Combine(words[2]));
Console.WriteLine("{0} ile {1} için {2}", words[2], words[3], words[2].Combine(words[3]));
Console.WriteLine("{0} ile {1} için {2}", words[3], words[0], words[3].Combine(words[0]));
}
}
public static class Extensions
{
public static string Combine(this string LeftWord,string RightWord)
{
int weight = FindWeight(LeftWord, RightWord);
string result =string.Format("{0}{1}", LeftWord, RightWord.Substring(weight, RightWord.Length - weight));
return result;
}
private static int FindWeight(string wordLeft, string wordRight)
{
int maxLength = wordLeft.Length < wordRight.Length ? wordLeft.Length : wordRight.Length;
for (int i = 0; i < maxLength; i++)
{
if (wordLeft.EndsWith(wordRight.Substring(0, maxLength - i), true, null)) // büyük küçük harf ayrımı yapmasın
{
return maxLength - i;
}
}
return 0;
}
}
}</pre>
<p>Uygulamamızda basit bir extension metod ile string birleştirme işlemi gerçekleştirilmektedir. Buna göre örneğin sonucu aşağıdaki gibi olacaktır.</p>
<p><img src="/pics/2012%2f1%2fartcl_13_1.png" alt="" /></p>
<p>Görüldüğü üzere ağırlık derecelerine göre bazı kelimelerin birleşimi daha kısa olurken bazıları ise arka arkaya gelmektedir, nitekim ağırlıkları <strong>0</strong> dır.</p>
<p>Yazmış olduğumuz bu temel fonksiyon iki kelime işin içerisinde olduğunda işe yaramaktadır. Lakin kelime dizisinin tamamının ele alınması biraz daha farklı bir durumdur. Daha fazla kod ve daha karmaşık bir algoritma gerekmektedir. Yaptığım araştırmalar sonucunda aşağıdaki gibi bir kod parçasını toparlamayı başarabildim.</p>
<p><img src="/pics/2012%2f1%2fko_8.png" alt="" /></p>
<p><strong>Sınıf diagramında(Class Diagram)</strong> da görüleceği üzere, kelimeler arası ilişkileri tasvir edebilmek adına bir <strong>Node </strong>listesini modelemeye çalışıyoruz. Bu <strong>Node </strong>listesi, bir kelime ve buna bağlı ne kadar diğer kelime kombinasyonu varsa, ağırlıkları ile birlikte <strong>cover </strong>etmeye çalışmaktadır. Diğer yandan <strong>Node </strong>listesini kullanarak uygun olabilecek bir birleşimi üretme fonksiyonelliğini, <strong>Creator </strong>isimli tip karşılamaktadır. Kodun biraz karmaşık olduğunu biliyorum. Lakin bu konu ile ilişkili olarak yaptığım araştırmalarda, en basite indirgeyebildiğim sıkıştırma algoritması bu oldu. İnanın bu anlamda ele alınan diğer algoritmalar <em>(NP Algoritmaları özellikle)</em> inanılmaz derecede karışık geliyor bana <img title="Sealed" src="/editors/tiny_mce3/plugins/emotions/img/smiley-sealed.gif" alt="Sealed" border="0" /> Ama yılmak yok! Lafı fazla uzatmadan kodumuzu paylaşalım.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Collections.Generic;
using System.Linq;
namespace EnKisaCumle
{
class Program
{
static void Main(string[] args)
{
string[] words = { "Paket", "KETEN", "EngiNar", "arPA" };
Creator graph = new Creator(new List<string>(words));
Console.WriteLine(graph.CompressWords());
}
}
// Yardımcı olacak genişletme metodlarımız
public static class Extensions
{
// İki kelimeyi ağırlıkları mertebesinde birleştirir.
public static string Combine(this string LeftWord, string RightWord)
{
int weight = FindWeight(LeftWord, RightWord);
string result = string.Format("{0}{1}", LeftWord, RightWord.Substring(weight, RightWord.Length - weight));
return result;
}
// İki kelimenin birleşme ağırlık değerini hesaplar
public static int FindWeight(this string LeftWord, string RightWord)
{
int maxLength = LeftWord.Length < RightWord.Length ? LeftWord.Length : RightWord.Length;
for (int i = 0; i <= maxLength; i++)
{
if (LeftWord.EndsWith(RightWord.Substring(0, maxLength - i), true, null)) // büyük küçük harf ayrımı yapmasın
{
return maxLength - i;
}
}
return 0;
}
// Belirtilen Sequence koleksionu üzerindeki her bir elemanda Action temsilcisi ile belirtilen fonksiyonelliğin çalıştırılmasını sağlar
public static void Run<T>(this IEnumerable<T> Sequence, Action<T> Action)
{
foreach (var item in Sequence)
Action(item);
}
// Reduce metodu içerisinde devreye girer
public static IEnumerable<T> With<T>(this IEnumerable<T> Sequence, T Item)
{
foreach (var t in Sequence)
yield return t;
yield return Item;
}
// Bir kelime kombinasyonu içerisindeki Node ve Parent' ı arasındaki birleşimi üretir ve yeni bir Node olarak elde etmemizi sağlar
public static Node<string, int> Combine(this Combination<string, int> Combination)
{
return new Node<string, int>(Combination.Parent.Value.Combine(Combination.Node.Value));
}
}
// Bir kelime ve bu kelime ile diğerleri arasındaki ilişkiler ile ağırlıkları tutan temel tipimizdir
public class Node<T, W>
{
private List<Combination<T, W>> combinations = new List<Combination<T, W>>();
Func<Node<T, W>, Node<T, W>, W> weightCalculator;
public Func<Node<T, W>, Node<T, W>, W> WeightCalculator
{
get
{
if (weightCalculator == null)
weightCalculator = (n1, n2) => default(W);
return weightCalculator;
}
set
{
weightCalculator = value;
}
}
public List<Combination<T, W>> Combinations
{
get
{
return combinations;
}
set
{
combinations = new List<Combination<T, W>>(value);
}
}
public T Value { get; private set; }
public Node(T value)
{
Value = value;
}
public void Add(Node<T, W> node)
{
var combination = new Combination<T, W>(this, node, WeightCalculator(this, node));
combinations.Add(combination);
}
}
// Kelime kombinasyonlarını Parent ve Current Node bazında ağırlıkları ile birlikte saklar.
public class Combination<T, W>
{
public Node<T, W> Parent { get; private set; }
public Node<T, W> Node { get; private set; }
public W Weight { get; private set; }
public Combination(Node<T, W> Parent, Node<T, W> Node, W Weight)
{
this.Parent = Parent;
this.Node = Node;
this.Weight = Weight;
}
}
// Asıl işlemleri üstlenen tipimiz. Kelimelere ait node listesine yeni örnekler eklenmesi, sıkıştırma yapılması, olası kombinasyonların azaltılması gibi fonksiyonellikleri üstlenir.
public class Creator
{
List<Node<string, int>> nodes = new List<Node<string, int>>();
Func<Node<string, int>, Node<string, int>, int> weightCalculator;
public Creator()
{
weightCalculator = (node, newNode) =>
{
return node.Value.FindWeight(newNode.Value);
};
}
public Creator(List<string> Words)
{
Words.Run(Add);
}
public List<Node<string, int>> Nodes
{
get
{
return nodes;
}
set
{
nodes = new List<Node<string, int>>(value);
}
}
public void Add(string Value)
{
if (!nodes.Exists(n => n.Value == Value))
{
var newNode = new Node<string, int>(Value)
{
WeightCalculator = weightCalculator
};
nodes.Run(node =>
{
newNode.Add(node);
node.Add(newNode);
});
nodes.Add(newNode);
}
}
public Creator With(string value)
{
Add(value);
return this;
}
public Creator Reduce()
{
if (nodes.Count <= 1)
return this;
var combinations = from n in nodes
from e in n.Combinations
select e;
var combination = combinations.First(n => n.Weight == combinations.Max(e => e.Weight));
return new Creator(nodes.Select(n => n.Value)
.Where(str => str != combination.Parent.Value && str != combination.Node.Value)
.With(combination.Combine().Value).ToList());
}
public string CompressWords()
{
Creator graph = this;
while (graph.nodes.Count > 1)
{
graph = graph.Reduce();
}
return graph.nodes[0].Value;
}
}
}</pre>
<p>Örneğimizi çalıştırdığımızda aşağıdaki gibi bir sonuç elde ederiz.</p>
<p><img src="/pics/2012%2f1%2fko_9.png" alt="" /></p>
<p>Görüldüğü üzere kelimeleri istediğimiz şekilde birleştirebilidik.</p>
<p>Uygulama kodunu kavrayabilmek adına <strong>Debug </strong>ederek adım adım ilerlemenizi öneririm. Lakin içeride makaleyi yazdığım tarih itibariyle halen çözemediğim bazı <strong>bug</strong>' lar bulunmakta. Söz gelimi kelime dizimize <strong>5nci </strong>bir içeriği eklediğimizi düşünelim. "<strong>DEMİR"</strong>. Aşağıdaki sonucu elde ederiz.</p>
<p><img src="/pics/2012%2f1%2fko_10.png" alt="" /></p>
<p>Başarılı bir birleştirme işlemi yapılmış gibi görünüyor değil mi? Aslında biraz daha dikkat edersek, hiç bir kelime ile ortak notkası olmayan <strong>DEMİR </strong>sözcüğünün en sona veya en başa alınmasının daha doğru olduğunu görebiliriz. Çünkü bu durumda</p>
<p><strong>EngiNarPAketENDEMİR veya DEMİREngiNarPAKetEN <br /></strong></p>
<p>sonuçlarını elde edebiliriz. Yani <strong>PA </strong>hecesinin teke indirgenmesi söz konusudur. Dolayısıyla kodun gözden geçirilmesi, algoritmanın temizlenerek en uygun sonucun elde edilmesi için gerekli müdahalelerin yapılması gerekmekte. Burada iş biraz da sizlere düşüyor. Her ne kadar mükemmel şekilde çalışan bir algoritma olmasa da, kendi adıma kelime sıkıştırma konusunda epey bir fikir verdiğini, en azından kağıt üzerinde kelimeler arası ilişkilerin bulunması noktasında nasıl hareket edilebileceğini hem kendi adıma hem de değerli okurlarım adına anlamış bulunmaktayım. Tabi önmeli bir eksiğimiz daha var. Sıkıştırılan metni nasıl geri çözümleyeceğimiz. Buna bir çözüm getirebilir misiniz?</p>
<p>Tekrardan görüşünceye dek hepinize mutlu günler dilerim.</p>
<p><a href="https://buraksenyurt.com/pics/2013%2f9%2fEnKisaCumle.zip">EnKisaCumle.zip (59,15 kb)</a></p>2013-09-01T20:45:00+00:00c#stringextension methodsnp algorithmsbsenyurtİşte geçtiğimiz hafta içerisinde de Internet üzerinden araştırma yaparken enteresan bir konu ile karşılaştım. Aslında konuyu isimlendirmek oldukça zor ama bir optimizasyon işlemi olduğunu ifade edebilirim. Sorun n sayıda kelimenin saklanmak istendiği bir durumda ortaya çıkıyor. İstenen, bu kelimeleri birleştirerek saklamak ancak bunu yaparkende olabilecek en kısa cümleyi elde ederek ilgili depolama işlemini gerçekleştirmek. Öyleki, üretilen cümle hem çok kısa olmalı hem de tüm kelimeleri içermeli.https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=3aadd719-8791-42c8-aaae-4f4b51f3d1785https://buraksenyurt.com/trackback.axd?id=3aadd719-8791-42c8-aaae-4f4b51f3d178https://buraksenyurt.com/post/En-Kisa-Metni-Bulmak#commenthttps://buraksenyurt.com/syndication.axd?post=3aadd719-8791-42c8-aaae-4f4b51f3d178https://buraksenyurt.com/post/Levenshtein-Distance-AlgoritmasiLevenshtein Distance Algoritması2012-07-01T23:05:00+00:00bsenyurt<p><a href="https://buraksenyurt.com/pics/artcl_11_4.jpg"><img style="margin: 4px 0px; display: inline; float: right;" title="artcl_11_4" src="/pics/artcl_11_4_thumb.jpg" alt="artcl_11_4" width="300" height="199" align="right" /></a>Merhaba Arkadaşlar,</p>
<p>Bir süredir yazılım dünyasında sıklıkla kullanılan basit algoritmalara merak salmış durumdayım. Bazıları kafayı yedirtecek cinsten olsalarda arada sırada bunları değerlendirmekte ve paslanan dimamızı açmaya çalışmakta yarar olduğu kanısındayım.</p>
<p>Aslına bakarsanız bilgisayar bilimlerinde uygulanabilen, gerçekten çok işe yarayan ve onları keşfedenleri saygıyla hatırlamamız gereken algoritmalar mevcut. Örneğin bunlardan birisi olan <a href="http://en.wikipedia.org/wiki/Vladimir_Levenshtein">Levenshtein Distance</a> algoritması ve mucidi <strong>Vladimir Levenshtein</strong> <img class="wlEmoticon wlEmoticon-winkingsmile" style="border-style: none;" src="/pics/wlEmoticon-winkingsmile_79.png" alt="Winking smile" /></p>
<p>Bu algoritma bizlere, özellikle arama motorlarında da kullanılabilen bir model sunmaktadır. Son kullanıcıların aradıkları kelimeleri tam olarak belirleyemedikleri veya kestiremedikleri durumlarda, öneri olarak sunulan kelimelerin tespit edilmesi sırasında ele alınan bir algoritmadır. Örneğin ben <strong>Google</strong> sitesindeki arama kutucuğunda kendi ismimi eksik karakterler ile yazdığımda, <strong>google</strong> daha önceden yapmış olduğu indekslenmiş içeriklere göre bir öneri de bulunmuştur<em>(Bunu mu demek istediniz kısmı)</em> Aşağıdaki şekilde bu durum açık bir şekilde görülmektedir.</p>
<p><a href="https://buraksenyurt.com/pics/artcl_11_1.png"><img style="background-image: none; margin: 4px 0px; padding-left: 0px; padding-right: 0px; display: inline; padding-top: 0px; border: 0px;" title="artcl_11_1" src="/pics/artcl_11_1_thumb.png" alt="artcl_11_1" width="375" height="190" border="0" /></a></p>
<p>Arama motorları dışında, özellikle imla kontrolü yapan uygulamalarda da<em>(Söz gelimi <strong>Microsoft Outlook</strong> veya <strong>Microsoft Word’</strong> ün <strong>Spell Checking</strong> mekanizmalarında)</em> bu algoritmanın kullanımına sıklıkla şahit olmaktayız.</p>
<p>Biz bu yazımızda söz konusu algoritmanın kullanılması için gerekli olan temel fonksiyonu, sıklıkla yaptığımız üzere bir <strong>Extension Method</strong> olarak geliştirmeye ve test etmeye çalışıyor olacağız. Ancak kodlama kısmına geçmeden önce algoritmanın nasıl çalıştığına ve işlediğine bakmamızda yarar olacağı kanısındayım.</p>
<p>Aslında algoritma temel olarak iki kelimenin birbirlerine olan benzerliklerini ölçümlemek amacıyla kullanılmaktadır. Sonuç tek bir sayısal değerdir ve iki kelimeden birinin diğerine dönüştürülebilmesi için gerekli olan işlem sayısını ya da maliyetini vermektedir. Çok doğal olarak bu sayınının düşük olması arzu edilen neticedir. Nitekim daha az değişiklik anlamına gelmektedir. Çok doğal olarak bir kelimenin, bir öneri kelime kümesi içerisindekiler ile karşılaştırılması sonucu ortaya çıkan sayısal değerlerden en küçüğü veya küçükleri, sonuca ulaşılması ve doğru önerilerde bulunulması açısından önemlidir.</p>
<p>Peki bu yakınlık değeri nasıl hesaplanmaktadır? <img class="wlEmoticon wlEmoticon-smile" style="border-style: none;" src="/pics/wlEmoticon-smile_27.png" alt="Smile" /> Bunun için kelimeler arası iki boyutlu bir matris dizisi kullanılır. Lakin söz konusu matrisin içereceği değerlerin tespiti çok da kolay değildir. Dilerseniz aşağıdaki Excel görüntüsünde yer alan örneklemelere bir bakalım ve algoritmayı daha yakından tanımaya çalışalım.</p>
<p><a href="https://buraksenyurt.com/pics/artcl_11_3.png"><img style="background-image: none; margin: 4px 0px; padding-left: 0px; padding-right: 0px; display: inline; padding-top: 0px; border: 0px;" title="artcl_11_3" src="/pics/artcl_11_3_thumb.png" alt="artcl_11_3" width="536" height="464" border="0" /></a></p>
<p>Bu grafikte, 5 farklı örnek ile 10 kelimenin birbirleri ile yakınlıklarının<strong> Levensthein Distance</strong> algoritmasına göre nasıl hesap edildiği gösterilmektedir. İlk olarak <strong>rest</strong> kelimesinin <strong>test</strong> kelimesi ile olan yakınlığı bulunmaya çalışılmıştır. Aslına bakarsanız bu iki kelime arasında sadece<strong> 1 işlem</strong> yaparak sonuca ulaşılabilir. Bu işleme göre <strong>rest kelimesindeki r harfi yerine, t harfinin gelmesi</strong> yeterlidir. Matris içerisinde yer alan sayılar o andaki sütuna veya satıra kadar olan harf topluluklarının birbirleri ile eş düşmeleri için gerekli işlem sayılarını içermektedir.</p>
<p>Şimdi de <strong>google</strong> ve <strong>yahoo!</strong> kelimelerinin yakınlık hesabını göz önüne alalım. Normal şartlarda iki kelime içerisinde ortak olan<strong> 2 “o”</strong> harfi bulunmaktadır ancak yerleri farklıdır. Diğer harfler ise zaten birbirlerinde yoktur. Bu nedenle<strong> 6 işlemlik bir operasyon yapılması</strong> gerekmektedir.</p>
<p>Peki sayılar tam olarak nasıl yerleştirilmekte veya okunmaktadırlar? Hemen <strong>Samantha</strong> ile <strong>Sam’</strong> in karşılaştırılmasını ele alalım. Şimdi <strong>0 indisli</strong> olacak şekilde <strong>1nci sütun</strong> ve <strong>1inci satırı</strong> göz önüne alalım. 1nci sütunda <strong>“s”</strong> harfi ve 1nci satırda yine <strong>“s”</strong> harfi bulunmaktadır. Dolayısıyla o anki karşılaştırmada, her iki harfte aynı olduğunda bir işlem yapılmasına gerek yoktur. Dolayısıyla <strong>işlem maliyeti 0dır</strong>. Şimdi <strong>2ncü sütuna</strong> ve<strong> 1nci satıra</strong> bakalım. 2nci sütuna kadar olan kısımda <strong>“sa“</strong> hecesi oluşmuştur. Satır tarafında ise sadece <strong>“s” </strong>harfi bulunmaktadır. Dolayısıyla eşleştirme için satır kısmındaki <strong>“s”</strong> harfine bir de <strong>“a”</strong> harfinin eklenmiş olması gerekir. Ki bu da <strong>1 işlem maliyeti</strong> olarak ifade edilmektedir.</p>
<p>Durumu biraz daha öteleyelim. 5 numaralı örnekte yer alan <strong>puzzle</strong> ve <strong>pzzel</strong> kelimelerinin karşılaştırılmasında <strong>5nci sütun</strong> ve <strong>4ncü satıra</strong> bakalım. 5nci sütuna kadar <strong>puzz</strong> kelimesi 4ncü satıra kadar da <strong>pzz</strong> kelimesi söz konusudur.<strong>pzz</strong>’ un <strong>puzz</strong> kelimesine benzemesi için araya bir <strong>“u”</strong> harfinin konulması yeterlidir. Diğer kısımlar satır ve sütun bazında da eşleşmektedir. Bu yüzden buradaki <strong>işlem maliyeti değeri 1</strong> dir. Ancak yine 0 indisli baktığımızda ve <strong>7nci sütun</strong> ve<strong> 6ncı satıra</strong> kadar olan kısımda <strong>puzzle</strong> ve <strong>pzzel</strong> kelimeleri göz önüne alındığında ise; pzzel’ dan puzzle’a geçmek istenildiğinde ilk olarak araya bir<strong> “u”</strong> harfi konulur.</p>
<p>p<strong><sup>u</sup></strong>zzel</p>
<p>Ardından <strong>“el” </strong>hecesinde<strong> e’ nin l yerine, l’ nin e yerine</strong> geçmesi gerekir.</p>
<p>p<strong><sup>u</sup></strong>zz<strong><sup>le</sup></strong></p>
<p>Dolayısıyla toplamda <strong>3 işlem maliyeti</strong> söz konusu olmuştur.</p>
<p>Bu algoritma gereği iki kelime arasındaki yakınlık derecesi, matrisin sağ alt hücresindeki sayısal değer ile ifade edilmektedir. Buna göre <strong>puzzle</strong> ile <strong>pzzel</strong> kelimeleri arasındaki mesafe <strong>3 işlem</strong> <strong>operayonu </strong>ile ölçülürken, bu <strong>Samantha</strong> ve <strong>Sam</strong> kelimeleri arasında <strong>5</strong> işlemlik bir maliyet oluşması söz konusudur<em>(Samantha’ dan <strong>antha</strong> kısmının atılması nedeni ile 5 işlemlik bir maliyet oluşmaktadır)</em></p>
<p>Algoritmayı biraz kavradığımıza göre dilerseniz bunu <strong>C#</strong> tarafında bir <strong>Extension</strong> <strong>Method</strong> içerisine dahil edelim ve test uygulamamıza çıkalım. Bu amaçla aşağıdaki örnek Console uygulamasını göz önüne alabiliriz.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
namespace UsingLevenshtein
{
class Program
{
static void Main(string[] args)
{
TestMethod("rest", "test");
TestMethod("google", "yahoo!");
TestMethod("mike", "mayk");
TestMethod("samantha", "sam");
TestMethod("puzzle", "pzzel");
}
private static void TestMethod(string Source,string Target)
{
int[,] matrix3 = new int[Source.Length, Target.Length];
int distance3 = Source.FindLevenshteinDistance(Target, out matrix3);
Console.WriteLine("{0} vs {1}\nDistance : {2}\n",Source,Target, distance3);
WriteToConsole(matrix3);
}
static void WriteToConsole(int[,] Matrix)
{
for (int i = 0; i < Matrix.GetLength(0); i++)
{
for (int j = 0; j < Matrix.GetLength(1); j++)
{
Console.Write("\t{0} ", Matrix[i, j]);
}
Console.WriteLine();
}
Console.WriteLine();
}
}
public static class StringExtensions
{
// Genişletme metodu, karşılaştırma matrisini de out parametresi olarak döndürmektedir.
public static int FindLevenshteinDistance(this string Source, string Target,out int[,] Matrix)
{
int n = Source.Length;
int m = Target.Length;
Matrix = new int[n + 1, m + 1]; // Hesaplama matrisi üretilir. 2 boyutlu matrisin boyut uzunlukları ise kaynak ve hedef metinlerin karakter uzunluklarına göre set edilir
if (n == 0) // Eğer kaynak metin yoksa zaten hedef metnin tüm harflerinin değişimi söz konusu olduğundan, hedef metnin uzunluğu kadar bir yakınlık değeri mümkün olabilir
return m;
if (m == 0) // Yukarıdaki durum hedefin karakter içermemesi halinde de geçerlidir
return n;
// Aşağıdaki iki döngü ile yatay ve düşey eksenlerdeki standart 0,1,2,3,4...n elemanları doldurulur
for (int i = 0; i <= n;i++)
Matrix[i, 0] = i;
for (int j = 0; j <= m; j++)
Matrix[0, j] = j;
// Kıyaslama ve derecelendirme operasyonu yapılır
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
int cost = (Target[j - 1] == Source[i - 1]) ? 0 : 1;
Matrix[i, j] = Math.Min(Math.Min(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1), Matrix[i - 1, j - 1] + cost);
}
return Matrix[n, m]; // sağ alt taraftaki hücre değeri döndürülür
}
}
}</pre>
<p>Uygulamamız içerisinde dikkat edeceğiniz üzere <strong>Excel</strong> tablosunda yer alan kelimelere ait bir test işlemi gerçekleştirilmektedir.<strong>FindLevenshteinDistance </strong>isimli metodumuz bir genişletme fonksiyonu olarak herhangibir <strong>string</strong> tipine uygulanabilecek şekilde tasarlanmıştır. Bununla birlikte söz konusu metod hem <strong>Levenshtein</strong> <strong>Distance</strong> matrisini, hemde yakınlık derecesini döndürmektedir. Uygulama içerisinde kelimeler arası testi kolaylaştırmak adına <strong>TestMethod</strong> isimli bir fonksiyon da ele alınmıştır. Programın çalışma zamanındaki çıktısı ise aşağıdaki gibi olacaktır.</p>
<p><a href="https://buraksenyurt.com/pics/artcl_11_2.png"><img style="background-image: none; margin: 4px 0px; padding-left: 0px; padding-right: 0px; display: inline; padding-top: 0px; border: 0px;" title="artcl_11_2" src="/pics/artcl_11_2_thumb.png" alt="artcl_11_2" width="459" height="759" border="0" /></a></p>
<p>Artık bundan sonrasında yapılması gereken, bir text kutucuğuna girilen metni, bir metin kümesi içerisinde söz konusu algoritmaya göre aramak ve yakınlık derecesi, bir başka deyişle operasyon işlem maliyeti en düşük olan kelime veya kelimeleri kullanıcıya sunmaya çalışmaktan ibarettir. Dilerseniz bu konuyu bir düşünün ve uygulamaya çalışın <img class="wlEmoticon wlEmoticon-winkingsmile" style="border-style: none;" src="/pics/wlEmoticon-winkingsmile_79.png" alt="Winking smile" /> Tekrardan görüşünceye dek hepinize mutlu günler dilerim.</p>
<p><a href="https://buraksenyurt.com/pics/2011%2f12%2fUsingLevenshtein.zip">UsingLevenshtein.zip (15,85 kb)</a></p>2012-07-01T23:05:00+00:00c#levenshtein distancealgoritmaextension methodsbsenyurtAslına bakarsanız bilgisayar bilimlerinde uygulanabilen, gerçekten çok işe yarayan ve onları keşfedenleri saygıyla hatırlamamız gereken algoritmalar mevcut. Örneğin bunlardan birisi olan Levenshtein Distance algoritması ve mucidi Vladimir Levenshtein Winking smile...https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=6fbdc82d-c361-4376-9046-d4ffecf83c6d4https://buraksenyurt.com/trackback.axd?id=6fbdc82d-c361-4376-9046-d4ffecf83c6dhttps://buraksenyurt.com/post/Levenshtein-Distance-Algoritmasi#commenthttps://buraksenyurt.com/syndication.axd?post=6fbdc82d-c361-4376-9046-d4ffecf83c6dhttps://buraksenyurt.com/post/Cerezlik-Algoritmalar-ve-Extension-MethodlarÇerezlik Algoritmalar ve Extension Methodlar2012-06-07T23:30:00+00:00bsenyurt<p><img style="float: right;" src="/pics/2011%2f12%2fartcl_8_1.jpg" alt="" />Merhaba Arkadaşlar,</p>
<p>Akademik yıllarımızda çoğumuz karmaşık matematik algoritmaları ile uğraşmak durumunda kalmışızdır<em>(Sınav stresini hatırlamak bile istemiyorum)</em> Özellikle veri yapıları ve algoritmalar<em>(Data Structures and Alogirthms)</em> veya Numeric Analiz gibi derslerde yoğun algoritma tasarımları üzerinde çalışılmaktadır. Doğruyu söylemek gerekirse ülkemizde bu dersleri layıkıyla veren kurum sayısı oldukça azdır. Konular genellikle sırlama algoritmalarının<em>(özellikle Quick Sort' un)</em> ötesine pek geçmemektedir. En fazla yüksek lisans öğreniminde farklı konulara girilmesi söz konusudur.</p>
<p>Pek tabi yazılım dünyası söz konusu olduğunda var olan hemen her algoritmanın karşılığı olan kodlamaların geliştirilmesi de önemli bir mevzudur. Bilimsel uygulamalarda, finansal model çözümlerinde, endusturi alanındaki planlama tekniklerinde vb...Ben bu yazımda sizleri o karmaşık ve anlaşılması zor algoritmalar ile yormayacağım. Bunun yerine eğilenceli sayılabilecek ve özellikle oyun programlamada oyunculara keyifli dakikalar yaşatmanızı sağlayabilecek basit bir kaç algoritma üzerinde durmaya çalışacağım. Söz konusu algoritmaları birer <strong>Extension Method </strong>olarak geliştireceğiz<em>.</em> Dilerseniz hiç vakit kaybetmeden ilk algoritmamız ile işe başlayalım.</p>
<p><img style="float: right;" src="https://buraksenyurt.com/image.axd?picture=/2017/02/2011-12-artcl_8_5.jpg" alt="" width="189" height="239" />Biraz eskilere gidiyor olacağız. Hatta <strong>Roma </strong>imparatoru <strong>Ceaser </strong>zamanına <img title="Smile" src="/editors/tiny_mce3/plugins/emotions/img/smiley-smile.gif" alt="Smile" border="0" /> <strong>Ceaser</strong>, <strong>Roma </strong>imparatorluğunun şaşalı dönemlerinde generalleri ile haberleşirken basit bir şifreleme metodolojisini kullanmaktaymış. Büyük bir ihtimalle sonradan <strong>Ceaser Cheaper </strong>olarak adlandırılan bu algoritmanın çalışma şekli aslında son derece basitmiş. Algoritmaya göre bir cümleyi veya metni, alfabe üzerinde belirlenen sayı kadar sağa(ileri) veya sola(geri) doğru ötelenmek suretiyle karşılık gelen harfler ile dizmek söz konusudur. Sonuçta ortaya, okunabilirliği pek olmayan anlamsız bir veri çıkmaktadır ama generaller tarafından bu, merkez sayı noktasına göre tekrardan geriye doğru ötelenerek anlamlı hale getirilebilir. Elbetteki bizim gerçek hayat uygulamalarımızda kullanacağımız bir şifreleme algoritması değildir bu. Ancak basit bir zeka oyununda neden kullanılmasın ki. Eğlenceli olabilir <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /> <em>(Algoritma hakkında detaylı bilgilere <a title="Ceaser Chiper" href="http://en.wikipedia.org/wiki/Caesar_cipher" target="_blank">bu adresten</a> ulaşabilirsiniz.)</em> Haydi gelin bu algoritma için bir genişletme metodu yazalım.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">public static class AlgorithmExtensions
{
#region Ceaser Cheaper ile karıştırma
public static string CaesarChiper(this string Word, int ShiftNumber)
{
char[] chars = Word.ToCharArray();
for (int i = 0; i < chars.Length; i++)
{
char currentLetter = chars[i];
currentLetter = (char)(currentLetter + ShiftNumber);
if (currentLetter > 'z')
currentLetter = (char)(currentLetter - 26);
else if (currentLetter < 'a')
currentLetter = (char)(currentLetter + 26);
chars[i] = currentLetter;
}
return new string(chars);
}
#endregion
}</pre>
<p>Aslında algoritma oldukça basit gördüğünüz gibi. Girilen <strong>Shift </strong>değerine göre <strong>ASCII </strong>tablosu üzerinden sağa veya sola doğru hareket ediliyor. <strong>z</strong> ve <strong>a </strong>aralığında bir öteleme hareketi yapıldığına dikkat edelim. Öteleme noktalarında elde edilen karakterler ardışıl olarak dizilerekten metnin karıştırılmış hali geriye döndürülüyor. Bir <strong>Extension Method</strong> olarak yazdığımız için herhangibir <strong>String </strong>değişken üzerinden uygulanabilir. Peki nasıl kullanacağız? <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /></p>
<p>Gelin aşağıdaki kod parçası ile ilerleyelim.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Collections.Generic;
using System.Linq;
namespace TestApp
{
class Program
{
static void Main(string[] args)
{
#region Ceaser Chipper Test
string word = "sol kanattan saldırın";
Console.WriteLine("Cümle : {0}\n",word);
Console.WriteLine("{0}\n",word.CaesarChiper(15));
Console.WriteLine("{0}\n", word.CaesarChiper(-15));
Console.WriteLine("{0}\n", word.CaesarChiper(6));
Console.WriteLine("{0}\n", word.CaesarChiper(10));
#endregion
}
}
}</pre>
<p>Örnek uygulamamızda girilen cümlenin <strong>Shift </strong>değerine göre farklı çıktılarının üretildiği görülecektir. İlk seferde 15 karakter sağa gidilerek işe başlanırken ikinci denemede 15 karakter sola gidilmek suretiyle bir üretim söz konusudur. Aşağıdaki ekran çıktısında çalışma zamanındaki durum net bir şekilde görülmektedir.</p>
<p><img src="/pics/2011%2f12%2fartcl_8_2.jpg" alt="" /></p>
<p>Dikkat edileceği üzere eğlenceli görünen karmaşık veri içerikleri üretilmiş durumda. Tabi bunu çözümlemeye çalışmak oyuncunun işi olacak. Oldukça fazla zorlanacağından emin olabilirsiniz. <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /></p>
<p><img style="float: left;" src="https://buraksenyurt.com/image.axd?picture=/2017/02/2011-12-artcl_8_7.jpg" alt="" />Ceaser' ın hakkına Ceaser' a verip ve <strong>Ceaser</strong>' a elveda diyerek yolumuza devam edelim. Sırada yer alan algoritmamız ise <strong>Fisher-Yates Shuffle </strong>olarak literatürde yer almaktadır. Bu algoritma yardımıyla bir sayı veya kelime dizisinin ya da farklı bir veri kümesinin her defasında farklı olacak şekilde karıştırılarak elde edilmesi söz konusudur. Bir başka deyişle farklı <strong>permütasyonların </strong>hesap edilerek bir karma veri içeriği üretilmesi gibi bir durum mevcuttur. <em>(1938 yılında keşfedilmiş olan bu algoritma hakkında ki detaylı bilgileri yine <a title="Fisher Shuffle Algorithm" href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" target="_blank">wikipedia</a> adresi üzerinden elde edebilirsiniz.) </em>Biz hiç vakit kaybetmeden bu algoritma için bir extension metod geliştirerek ilerleyelim.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Collections.Generic;
public static class AlgorithmExtensions
{
#region Fisher-Yates ile Shuffling
public static void Shuffle<T>(this List<T> SourceArray) // Fisher-Yates Shuffle Algoritmasına göre karıştırır
{
Random randomizer = new Random();
for (int i = SourceArray.Count; i > 1; i--)
{
int j = randomizer.Next(i); // 0 ile i-1 arasında rastgele bir değer üretecektir
T temp = SourceArray[j];
SourceArray[j] = SourceArray[i - 1];
SourceArray[i - 1] = temp;
}
}
#endregion
}</pre>
<p>Görüldüğü gibi algoritmamız kaynak olan dizi içerisindeki elemanları sondan başa doğru gezmektedir. Bu işlem sırasında o anki iterasyon değerine kadarki aralıkta üretilen bir rastgele sayı ve bunun dizideki karşılığı olan değer geçici bir değişkene atanır. Ardından o anki iterasyonun bir önceki değerine karşılık gelen dizi elemanı rastgele elde edilen değerin işaret ettiği indise taşınır. Son olarak da geçici değişkene alınan eleman o anki iterasyon değerinin bir öncesine karşılık gelen indise yerleştirilir. Genişletme metodunu generic olarak tasarladığımızı ve herhangibir <strong>List </strong>tipine uygulayabildiğimizi fark etmişsinizdir. Temel olarak hedefimiz sayısal veya metin tabanlı koleksiyon listelerinin karıştırılmış çıktılarını elde etmektir <em>(ki bir Puzzle uygulamasında bu teknik oldukça işe yarayabilir <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /> ) </em>Metodun kalbinde <strong>Random </strong>tipi yer almaktadır. Metodumuzu aşağıdaki kod parçasında olduğu gibi test sürüşüne çıkartabiliriz.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Collections.Generic;
using System.Linq;
namespace TestApp
{
class Program
{
static void Main(string[] args)
{
#region Fisher - Yates Shuttle Alogirtması
List<int> numbers = Enumerable.Range(0, 50).ToList();
List<string> names = new List<string> {
"bill","steve","daniel","meg","julia"
,"sunny","Matheus","chris","lora"
,"maggi","jim","steve","Emilie"
,"Maria","eva","samantha"
};
numbers.Shuffle();
WriteToConsole(numbers);
numbers.Shuffle();
WriteToConsole(numbers);
names.Shuffle();
WriteToConsole(names);
names.Shuffle();
WriteToConsole(names);
#endregion
}
private static void WriteToConsole<T>(List<T> SourceArray)
{
foreach (var element in SourceArray)
{
Console.Write("{0} ", element);
}
Console.WriteLine("\n\n");
}
}
}</pre>
<p><strong>Test </strong>kodunda <strong>string </strong>tipte isimlerden oluşan bir <strong>List </strong>koleksiyonu ve benzer şekilde sayılardan oluşan bir veri içeriği söz konusudur. Uygulamanın çalışma zamanı çıktısı ise aşağıdakine benzer olacaktır.</p>
<p><img src="/pics/2011%2f12%2fartcl_8_3.jpg" alt="" /></p>
<p>Size tavsiyem basit bir fotoğrafı n sayıda kareye böldükten sonra, bu parçaları işaret eden sınıfa ait nesne örneklerinden oluşan bir <strong>List </strong>koleksiyonunu, <strong>Fisher-Yates Shuffle </strong>algoritmasını kullanarak, oyuncuyu her seferinde farklı bir karmaşa ile baş başa bırakmayı denemeniz olacaktır <img title="Smile" src="/editors/tiny_mce3/plugins/emotions/img/smiley-smile.gif" alt="Smile" border="0" /></p>
<p><img style="float: left;" src="https://buraksenyurt.com/image.axd?picture=/2017/02/2011-12-artcl_8_6.jpg" alt="" width="197" height="179" />Geldik bu yazımızda size aktarmak istediğim son algoritmaya. Bu kez <strong>Palindromik </strong>veri tespiti yapmak için kullanılan bir algoritma üzerinde duracağız. <strong>Palindromic </strong>sayılar <strong>181, 191, 55 </strong>gibi tersten okunduklarında da aynı sayı değerini veren kavramlar olarak düşünülebilirler. Aslında <strong>Palindromic </strong>sayılar olarak düşünebileceğimiz bu modeli kelimeler için de ele alabiliriz. <strong>ANA, KAÇAK </strong>gibi örnekler bu anlamda düşünülebilir. Senaryo olarak baktığımızda ise, söz gelimi metin içerikli bir döküman içerisinde yer alan <strong>Palindromic </strong>kelimeleri veya cümleleri oyuncuya buldurabilir ve süre bazında başarısını ölçümlemeye çalışabiliriz. <em>(Bu algoritma ile ilişkili detaylı bilgileri yine <a title="Palindrom" href="http://tr.wikipedia.org/wiki/Palindrom" target="_blank">Wikipedia</a> üzerinden okuyabilirsiniz.) </em>Ancak öncesinde algoritma için gerekli olan genişletme metodumuzu yazalım.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Collections.Generic;
public static class AlgorithmExtensions
{
#region Palindromic Kelimeleri/Cümleleri Bulmak
public static List<string> PalindromicCheck(this List<string> Words)
{
List<string> result = new List<string>();
foreach (string word in Words)
{
if (IsPalindromicData(word))
result.Add(word);
}
return result;
}
private static bool IsPalindromicData(string SourceValue)
{
int minValue = 0;
int maxValue = SourceValue.Length - 1;
while (true)
{
if (minValue > maxValue)
return true;
char a = SourceValue[minValue];
char b = SourceValue[maxValue];
if (char.ToLower(a) != char.ToLower(b))
return false;
minValue++;
maxValue--;
}
}
#endregion
}</pre>
<p>Sonsuz while döngüsü aslında kelimenin başından ve sonundan itibaren orta noktasına gelinceye kadar bir iterasyonu kullanmaktadır. İlk karakter ve son karakterin aynı olup olmadığı noktasında devreye giren algoritma orta noktadaki karaktere kadar devam edecektir. Genişletme metodumuz bu versiyonu ile <strong>string </strong>tipinden <strong>List </strong>koleksiyonuna uygulanabilecek şekilde tasarlanmıştır. Koleksiyon içerisindeki veriler, <strong>IsPalindromicData</strong> metodu yardımıyla kontrol edilmektedir. Metod sonuç olarak <strong>Palindromic </strong>veri içeriğini barındıran başka bir <strong>List </strong>koleksiyonunu geriye döndürür. Haydi gelin örneğimizi test edelim. Bu amaçla aşağıdaki kod parçasını göz önüne alabiliriz.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">using System;
using System.Collections.Generic;
using System.Linq;
namespace TestApp
{
class Program
{
static void Main(string[] args)
{
#region Palindromik kelimelerin tespiti
List<string> words = new List<string>{
"ana","baba","amaç","abla","aha","kaçak"
,"kayak","kırık","cam","uzak","yakın","meşale"
,"neden","sus","süs","'ey edip adanada pide ye'"
};
var result = words.PalindromicCheck();
WriteToConsole(result);
#endregion
}
private static void WriteToConsole<T>(List<T> SourceArray)
{
foreach (var element in SourceArray)
{
Console.Write("{0} ", element);
}
Console.WriteLine("\n\n");
}
}
}</pre>
<p>Örnekte kullanılan koleksiyon içerisinde tertsten okunduklarında da aynı olan bazı kelimeler ve hatta bir cümle mevcuttur. İşte çalışma zamanı sonuçları.</p>
<p><img src="/pics/2011%2f12%2fartcl_8_4.jpg" alt="" /></p>
<p>Bu algoritmayı oyuncudan ziyade oyun motoru kullanıyor olabilir. Ya da siz geniş bir kelime kümesini ekrana basıp bu küme içerisindeki <strong>Palindromic </strong>kelimeleri tespit etmesi için henüz ilk okul çağında olan bir oyuncuyu tercih edebilir ve süre bazlı bir ortam sağlayarak, onun dikkat, kavrama, fark etme, görsel hafıza gibi yeteneklerini arttırmaya çalışabilirsiniz <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /></p>
<p>Aslında oyun programlama denilince çok basit ve yararlı algoritmalar olduğunu görebiliyoruz. Ben bu yazımızda sadece 3 tanesini sizlere aktarmaya çalıştım. Elbetteki çok daha fazlası var. Araştırmak, denemek, öğrenmek, test etmek ve kullanmak sizin göreviniz. Tekrardan görüşünceye dek hepinize mutlu günler dilerim <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /></p>2012-06-07T23:30:00+00:00extension methodsfisher yates shuffleceaser chipperpalindromic wordspalindromic numbersc#bsenyurtPek tabi yazılım dünyası söz konusu olduğunda var olan hemen her algoritmanın karşılığı olan kodlamaların geliştirilmesi de önemli bir mevzudur. Bilimsel uygulamalarda, finansal model çözümlerinde, endusturi alanındaki planlama tekniklerinde vb...Ben bu yazımda sizleri o karmaşık ve anlaşılması zor algoritmalar ile yormayacağım. Bunun yerine eğilenceli sayılabilecek ve özellikle oyun programlamada oyunculara keyifli dakikalar yaşatmanızı sağlayabilecek basit bir kaç algoritma üzerinde durmaya çalışacağım. Söz konusu algoritmaları birer Extension Method olarak geliştireceğiz(Extension Method kavramını hatırlayalım. C# 3.0 - Derinlemesine Extension Method Kavramı) Dilerseniz hiç vakit kaybetmeden ilk algoritmamız ile işe başlayalım.https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=af34cd2c-64e0-4826-8a06-b5d747dad1894https://buraksenyurt.com/trackback.axd?id=af34cd2c-64e0-4826-8a06-b5d747dad189https://buraksenyurt.com/post/Cerezlik-Algoritmalar-ve-Extension-Methodlar#commenthttps://buraksenyurt.com/syndication.axd?post=af34cd2c-64e0-4826-8a06-b5d747dad189https://buraksenyurt.com/post/Binary-Search-Tree-yi-AnlamakBinary Search Tree' yi Anlamak2012-01-09T11:01:00+00:00bsenyurt<p><img style="float: right;" src="/pics/2012%2f1%2foldradio.jpg" alt="" />Merhaba Arkadaşlar,</p>
<p>İnsan hafızası gizemli çalışan ama çoğu zamanda bizleri şaşırtan bir mekaniğe sahiptir. Doğduğumuz andan itibaren 3 yaşına kadar geçen zaman dilimi içerisinde görsel olarak ne izlersek kaparız. Ancak neredeyse bunların hiç birini hatırlamayız.</p>
<p>Çocukluğumuz, ergenliğimiz, yetişkinliğimiz, orta yaş halimiz ve yaşlılığımız. Tüm bu zaman dilimlerinde beynimiz sürekli olarak bir şeyleri hafıza da tutma ihtiyacı hisseder. Zaman zaman öğrendiğimiz pek çok bilgiyi kolayca unutur ve ihtiyacımız olduğunda hatırlamakta zorlanırız. Ama kimi bilgilerde bilinç altımıza neredeyse kazınır ve geçerli bir sağlık problemi oluşmadığı sürece hiç unutmayız<em>(Çarpım tablosu, matematik dört işlemin nasıl yapıldığı veya hangi ışıkta durulması gerektiği gibi)</em></p>
<p>Peki kolayca unutabileceğimiz bilgiler nasıl oluşurlar? <img title="Undecided" src="/editors/tiny_mce3/plugins/emotions/img/smiley-undecided.gif" alt="Undecided" border="0" /></p>
<p>Genelde öğrendiklerimizi çok sık kullanmadığımız veya tekrar etmediğimiz durumlarda unutmak kaçınılmaz gerçeklerden birisidir. Kullanmama süresi arttığında ise, ihtiyaç duyulduğu anda söz konusu bilgileri tekrardan hatırlamak da giderek zorlaşmaktadır. Aslında çok sık kullanılmayan ama yaşamın herhangibir anında ihtiyaç duyabileceğimiz bilgileri yazarak bir yerlerde saklamak, mücadele etme yollarından birisidir.</p>
<p>Örneğin Üniversitede okutulan veri yapıları ve algoritmalar derslerini düşünelim. Öğrenmek, kavrayabilmek, kodlarını geliştirebilmek için epey kafa patlattığımız zorlayıcı bu içerikler, kolayca unutulabilecek cinstendir <img title="Frown" src="/editors/tiny_mce3/plugins/emotions/img/smiley-frown.gif" alt="Frown" border="0" /> Tabi eğer bunları her dönem anlatan bir akademisyen veya sürekli matematik modeller geliştiren bir uzman değilseniz. Eğer ki,<strong> .Net Framework, Java EE, SAP</strong> gibi ortamları kullanarak ağırlıklı olarak veri odaklı uygulamalar geliştiriyorsanız, zaten bu ders içeriğinin yakınından çok nadir olarak geçersiniz. İşte ben de bu hafıza kaybını yaşadığım şu dönemlerde, eski bilgilerimi hatırlamaya çalışmak istedim. İlk gözüme kestirdiğim konu ise <strong>ikili ağaç yapısı(Binary Tree)</strong> ve bunun üzerinden arama, ekleme gibi temel işlemlerin nasıl yapıldığı oldu?</p>
<p>İkili ağaç yapısı basitliği ve hızlı sonuç üretimi açısından bakıldığında, arama algoritmalarından tutunda oyun programlamaya, ilişkisel veri tabanlarından, karmaşık matematik modellere kadar pek çok alanda kullanılmaktadır. <strong>Binary Tree</strong> veri yapısı ve bu yapı üzerinde gerçekleştirilecek çeşitli operasyonlar<em>(arama, ekleme, silme gibi)</em> göz önüne alındığında ilk etapta bu ağacın nasıl oluşturulduğunun kavranması gerekmektedir. Aslında ikili ağaçlar, şirketlerin organizasyon ağacına benzer bir içeriğe sahiptirler. Tabi teknik olarak düşündüğümüzde bu ağacı oluşturmanın bazı kuralları vardır. Şimdi gelin teknik terim karmaşası içerisine girmeden konuyu bir örnek üzerinde kavramaya çalışalım.</p>
<p>Elimizde şöyle bir sayı dizisi olduğunu düşünelim.</p>
<p><span style="font-size: large;"><strong>7,4,9,1,3,10,12,8,5,6,9,11</strong></span></p>
<p>Şimdi bu rakamsal dizinin <strong>Binary Tree </strong>grafiğini oluşturmaya çalışalım.</p>
<p>İlk olarak 7 rakamından başlayıp, bunun <strong>Kök Boğum(Root Node)</strong> olduğunu düşünerekten en başa yerleştirelim. Ardınan ikinci rakama geçelim. İkinci rakam, ilk rakam olan 7' ye bağlı olmak durumda. Bir başka deyişle onun <strong>alt boğumu/çocuk boğumu(Child Node)</strong> olacak. 4, 7' den küçük bir rakam. Bu sebepten onu sol alt tarafa alalım.</p>
<p><img src="/pics/2012%2f1%2fbt1.png" alt="" /></p>
<p>3ncü rakamımız ise 9. Root Node ile karşılaştırdığımızda ondan büyük olduğunu görüyoruz. Bu yüzden onu 7nin sağ alt node' u olacak şekilde grafiğimize yerleştirelim.<img src="/pics/2012%2f1%2fbt2.png" alt="" /></p>
<p>Hımmm...<img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /> Demek ki bir kuralımız var.<strong> "Bir node değeri eğer bağlı olduğu node' un içindeki değerden küçükse onun solunda, değilse sağında yer alıyor olmalı."</strong></p>
<p>4ncü rakamdan devam edelim.1, root node olan 7den küçük. Dolayısıyla sol dalda yer almalı. Ancak sol dalda 4 değeri de var. 1, 4ten küçük olduğundan ve az önce bahsettiğimiz kuraldan dolayı sol alt node olarak grafiğe eklenmeli.</p>
<p><img src="/pics/2012%2f1%2fbt3.png" alt="" /></p>
<p>5nci rakamımız ise 3. Yine Root Node' dan aşağıya doğru inmeye başlıyoruz. Kuralımıza göre 3, 7den küçük ve onun sol dalında yer almalı. Bir alt seviyeye indiğimizde 4 ile karşılaşılıyor. 3, 4ten küçük olduğu için kuralımıza göre sol alt node olmalı ama yol devam ediyor. Çünkü sol alt node' da 1 var. 3, 1den büyük olduğu için kuralımıza göre sağ alt node' olmalı.</p>
<p><img src="/pics/2012%2f1%2fbt4.png" alt="" /></p>
<p>6ncı rakamımız 10. 10, root node olan 7den büyük olduğu için kuralımıza göre sağ dalda yer almalı. Sağ daldan aşağıya doğru indiğimizde 1nci seviyede 9 olduğunu görüyoruz. 10, 9dan büyük olduğu için sağ alt node' unda yer almalı.</p>
<p><img src="/pics/2012%2f1%2fbt5n.png" alt="" /></p>
<p>7nci rakamımız 12. Yine Root Node ile kıyaslayarak başladığımızda kuralımıza göre sağ dalda olması gerekiyor. 12, 9 dan büyük olduğu için sağ daldan inmeye devam ediyor ve yine 10dan büyük olduğu için sağ alt node olarak 3ncü seviyedeki yerini alıyor.</p>
<p><img src="/pics/2012%2f1%2fbt6.png" alt="" /></p>
<p>8nci elemanımız ise 8. Root node olan 7den büyük olduğu için sağ daldan aşağıya doğru akması gerekiyor. Yol üstünde ilk olarak karşılaştığı 9dan küçük olduğu içinse sol alt node olarak 2nci seviyedeki yerini alıyor.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2017/01/2012-1-bt12.png" alt="" /></p>
<p>9ncu elemanımız 5. Root Node olan 7den küçük olduğu için kuralımıza göre sol daldan aşağıya doğru kaydırılması gerekiyor. 1nci seviyede karşılaştığımız 4ten büyük bir değer olduğu içinse sağ alt node olarak 2nci seviyedeki yerini alıyor.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2017/01/2012-1-bt11.png" alt="" /></p>
<p>10ncu elemanımız 9. Ancak 9 zaten rakam dizimizde bir kez kullanıldı ve bir kere daha kullanılmaması gerekiyor. Hımm...Öyleyse bir kural daha ortaya çıkıyor.</p>
<p><strong>"Zaten dizide var olan bir elemanı ağaça tekrardan ekleyemeyiz."</strong></p>
<p>Örneğimizde yer alan son elemanımız ise 11. Yine root node ile başladığımızda 7den büyük olduğu için kuralımıza göre sağ dalda yer alması gerekiyor. Rakamı sağ daldan aşağıya doğru kaydırdığımızda, 1nci seviyedeki 9dan büyük olduğunu görüyoruz. Buna göre sağ daldan devam edilmeli. Sıradaki 10 rakamından da büyük olduğundan yine sağ dalda kalmalı. Sonradan gelen 12 rakamından küçük olduğu içinse sol alt dal olarak son seviyede yerini almalı.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2017/01/2012-1-bt9n.png" alt="" /></p>
<p>Daha başka sayımız kalmadığı için Binary Tree grafiğini tamamlamış bulunuyoruz. Görüldüğü gibi Root Node' dan aşağıda doğru inen ağaç yapısında <strong>her boğuma en fazla iki boğum bağlanabilmektedir</strong><em>(Zaten Binary denmesinin sebebi de budur <img title="Smile" src="/editors/tiny_mce3/plugins/emotions/img/smiley-smile.gif" alt="Smile" border="0" />)</em>. Bunun temel sebebi ise büyük ve küçük olma durumuna göre ilgili boğumun sağ veya sol alt boğum olarak grafiğe ekleniyor olmasıdır. Tabi bunun dışında zaten ağaç içerisinde yer almış bir elemanın tekrardan yer almaması gerekliliği ortaya konulmuştur. Dallar haricinde aslında boğumlar belirli seviyelere denk gelirler. Tüm bu bilgiler ışığında sayı dizisinin <strong>Binary Tree</strong> grafiği aşağıdaki nihai halini alır.</p>
<p><img src="https://buraksenyurt.com/image.axd?picture=/2017/01/2012-1-bt10n.png" alt="" /></p>
<p>Peki bu tip bir ağaç yapısını programatik ortamda tasarlamak istersek?</p>
<p>Aslında bu ağaç yapısı içerisinde dolaşmak bile başlı başına bir iş. Kağıt üzerinde her ne kadar kolay olsa da teorik olarak bunun bilinen 3 yöntemi bulunmaktadır. <strong>Traverse </strong>adı verilen bu dolaşım teknikleri InOrder<em>(Sol dalı dolaş, root' a uğra, sağ dalı dolaş)</em>, PreOrder<em>(Root' dan başla, sol dalı yukarıdan aşağı gez, sol dalı yukarıdan aşağı gez) </em>ve PostOrder<em>(Sol dalı aşağıdan yukarı tara, sağ dalı aşağıdan yukarı tara, root' a uğra) </em>olarak geçmektedir. </p>
<p>Ne yazık ki <strong>.Net Framework</strong> tarafında<strong> Binary Tree</strong> yapısını destekleyen hazır bir tip ve özellikle koleksiyon bulunmamaktadır. Dolayısıyla bunu kendimiz oluşturmak durumundayız. Biraz uğraştırıcı olsa da buna hizmet edecek bir geliştirme yapabiliriz. Bize iki temel tip gerekmektedir. Birincisi ağaç yapısındaki her bir boğumu temsil edecek olan tiptir. Bu tip bir Node' un değerini, kendinden sonraki Sol ve Sağ Node' ları ve bağlı olduğu Parent Node' u bilecek şekilde tasarlanmalıdır. Yani aşağıdaki gibi.</p>
<p><img src="/pics/2012%2f1%2fbt13.png" alt="" /></p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">public class BinaryTreeNode<T>
{
public T Value { get; set; }
public BinaryTreeNode<T> ParentNode { get; set; }
public BinaryTreeNode<T> LeftNode { get; set; }
public BinaryTreeNode<T> RightNode { get; set; }
public bool IsRoot { get { return ParentNode == null; } }
public bool IsLeaf { get { return LeftNode == null && RightNode == null; } }
public BinaryTreeNode(T RealValue)
{
Value = RealValue;
}
public BinaryTreeNode(T RealValue, BinaryTreeNode<T> Parent)
{
Value = RealValue;
ParentNode = Parent;
}
public BinaryTreeNode(T RealValue, BinaryTreeNode<T> Parent, BinaryTreeNode<T> Left, BinaryTreeNode<T> Right)
{
Value = RealValue;
RightNode = Right;
LeftNode = Left;
ParentNode = Parent;
}
}</pre>
<p>Bu basit bir tip. Asıl önemli olan ağacın grafiğini kodsal olarak sembolize edecek, Add, Remove ve Traverse gibi işlemlerini yapacak olan tipi geliştirmek. Onu da biraz uğraştıktan sonra aşağıdaki gibi yazabiliriz.</p>
<p><img src="/pics/2012%2f1%2fbt14.png" alt="" /></p>
<p>Dikkat edileceği üzere <strong>BinaryTree </strong>sınıfı <strong>generic </strong>olarak tasarlanmış ve <strong>ICollection<T></strong> ile <strong>IEnumerable<T></strong> <strong>arayüzlerini(Interface)</strong> uygulamıştır. Bu nedenle zorunlu olarak ezmesi gereken bazı üyeleri vardır. Ayrıca <strong>BinaryTree</strong> içerisinde yer alacak olan <strong>BinaryTreeNode</strong> nesne örneklerinin en azından değer bazında karşılaştırma yapılabilir olması gerekmektedir. Nitekim değerlerin bibirlerinden büyük ve küçük olma durumlarına göre bir yerleştirme ve arama söz konusudur. Bu yüzden bir de generic <strong>Constraint </strong>konularak <strong>T</strong> tipinin <strong>IComparable<T> </strong>arayüzünü uygulama zorunluluğu konulmuştur. Sınıfımıza ait kodlar ise aşağıdaki gibidir.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">public class BinaryTree<T>
: ICollection<T>, IEnumerable<T>
where T : IComparable<T>
{
public BinaryTreeNode<T> RootNode { get; set; }
public int NodeCount { get; set; }
public bool IsEmpty { get { return RootNode == null; } }
// Ağaç içerisindeki en küçük değerli elemanı döndürür
public T MinValue
{
get
{
if (IsEmpty)
throw new Exception("Ağaç içerisinde hiç bir eleman yok");
BinaryTreeNode<T> tempNode = RootNode;
while (tempNode.LeftNode != null) // Sol dallarda değer olduğu sürece dolaş
tempNode = tempNode.LeftNode;
return tempNode.Value;
}
}
// Ağaç içerisindeki en büyük değerli elemanı döndürür
public T MaxValue
{
get
{
if (IsEmpty)
throw new Exception("Ağaç içerisinde hiç bir eleman yok");
BinaryTreeNode<T> tempNode = RootNode;
while (tempNode.RightNode != null) // Sağ dallarda değer olduğu sürece dolaş
tempNode = tempNode.RightNode;
return tempNode.Value;
}
}
// Kaç eleman olduğunu döndürür
public int Count
{
get { return NodeCount+1; }
}
public BinaryTree(BinaryTreeNode<T> Root)
{
RootNode = Root;
NodeCount = 0;
}
public IEnumerator<T> GetEnumerator()
{
foreach (BinaryTreeNode<T> tempNode in Traversal(RootNode))
yield return tempNode.Value; // Çok şükürki 2.0 ile gelen yield keyword' ü var :)
}
IEnumerator IEnumerable.GetEnumerator()
{
foreach (BinaryTreeNode<T> tempNode in Traversal(RootNode))
yield return tempNode.Value;
}
// Koleksiyona eleman ekleyebilmek için kullanılır
public void Add(T SourceItem)
{
if (RootNode == null)
{
RootNode = new BinaryTreeNode<T>(SourceItem);
NodeCount++;
}
else if(Contains(SourceItem))
return;
else
Insert(SourceItem);
}
public void Clear()
{
RootNode = null;
}
// Koleksiyonda T tipinden olan eleman olup olmadığını araştırır
public bool Contains(T SourceItem)
{
if (IsEmpty)
return false;
BinaryTreeNode<T> tempNode = RootNode;
while (tempNode != null)
{
int comparedValue = tempNode.Value.CompareTo(SourceItem);
if (comparedValue == 0)
return true;
else if (comparedValue < 0)
tempNode = tempNode.LeftNode;
else
tempNode = tempNode.RightNode;
}
return false;
}
// Koleksiyon içeriğinin aynı tipten bir Array' e kopyalar
public void CopyTo(T[] TargetArray, int IndexNo)
{
T[] tempArray = new T[NodeCount+1];
int Counter = 0;
foreach (T value in this)
{
tempArray[Counter] = value;
Counter++;
}
Array.Copy(tempArray, 0, TargetArray, IndexNo, this.NodeCount);
}
// Koleksiyondan eleman çıkartmak için kullanılır
public bool Remove(T SourceItem)
{
BinaryTreeNode<T> item = Find(SourceItem);
if (item == null)
return false;
List<T> values = new List<T>();
foreach (BinaryTreeNode<T> tempNode in Traversal(item.LeftNode))
values.Add(tempNode.Value);
foreach (BinaryTreeNode<T> tempNode in Traversal(item.RightNode))
values.Add(tempNode.Value);
if (item.ParentNode.LeftNode == item)
item.ParentNode.LeftNode = null;
else
item.ParentNode.RightNode = null;
item.ParentNode = null;
foreach (T value in values)
Add(value);
return true;
}
public bool IsReadOnly
{
get { return false; }
}
BinaryTreeNode<T> Find(T SourceItem)
{
foreach (BinaryTreeNode<T> item in Traversal(RootNode))
if (item.Value.Equals(SourceItem))
return item;
return null;
}
// InOrder modeline göre elemanlar dolaşılır.
IEnumerable<BinaryTreeNode<T>> Traversal(BinaryTreeNode<T> Node)
{
if (Node.LeftNode != null)
foreach (BinaryTreeNode<T> leftNode in Traversal(Node.LeftNode))
yield return leftNode;
yield return Node;
if (Node.RightNode != null)
foreach (BinaryTreeNode<T> rightNode in Traversal(Node.RightNode))
yield return rightNode;
}
void Insert(T SourceItem)
{
BinaryTreeNode<T> tempNode = RootNode;
bool found = false;
while (!found)
{
int comparedValue = tempNode.Value.CompareTo(SourceItem);
if (comparedValue < 0)
{
if (tempNode.LeftNode == null)
{
tempNode.LeftNode = new BinaryTreeNode<T>(SourceItem, tempNode);
NodeCount++;
return;
}
else
{
tempNode = tempNode.LeftNode;
}
}
else if (comparedValue > 0)
{
if (tempNode.RightNode == null)
{
tempNode.RightNode = new BinaryTreeNode<T>(SourceItem, tempNode);
NodeCount++;
return;
}
else
{
tempNode = tempNode.RightNode;
}
}
else
{
return;
}
}
}
}</pre>
<p>Artık yeni tiplerimizi denemeye çıkabiliriz. Bu amaçla program kodunda aşağıdaki test kodları göz önüne alınabilir.</p>
<pre class="brush:csharp;auto-links:false;toolbar:false" contenteditable="false">class Program
{
static void Main(string[] args)
{
BinaryTree<int> numbers = new BinaryTree<int>(new BinaryTreeNode<int>(7));
numbers.Add(4);
numbers.Add(9);
numbers.Add(1);
numbers.Add(3);
numbers.Add(10);
numbers.Add(12);
numbers.Add(8);
numbers.Add(5);
numbers.Add(6);
numbers.Add(9);
numbers.Add(11);
Console.WriteLine("{0} eleman aktarıldı", numbers.Count);
foreach (int number in numbers)
Console.WriteLine(number);
Console.WriteLine("{0} değeri koleksiyonda {1}",5,numbers.Contains(5)?"Var":"Yok");
Console.WriteLine("Max {0} Min {1}",numbers.MaxValue,numbers.MinValue);
int[] array = new int[numbers.Count];
numbers.CopyTo(array, 0);
}
}</pre>
<p>Temel olarak koleksiyonumuza eklediğimiz temel operasyonlardan bazılarını kullanmaya çalıştık. Uygulamanın <strong>Runtime </strong>çıktısı aşağıdakine benzer olacaktır.</p>
<p><img src="/pics/2012%2f1%2fbt15.png" alt="" /></p>
<p>Tabi kodda gözden kaçırdığım bazı noktalar olabilir. Ben elimden geldiğince test etsem de farklı gözlerin bakmasında yarar var. Ancak temel olarak <strong>Binary Tree</strong> veri yapısını, C# ile nasıl kodlanabileceğini kavradığınızı düşünüyorum. Böylece geldik bir yazımızın daha sonuna. Tekrardan görüşünceye dek hepinize mutlu günler dilerim <img title="Wink" src="/editors/tiny_mce3/plugins/emotions/img/smiley-wink.gif" alt="Wink" border="0" /></p>
<p><a href="https://buraksenyurt.com/pics/2012%2f1%2fBinarySearchTree.zip">BinarySearchTree.zip (42,36 kb)</a></p>2012-01-09T11:01:00+00:00binary treebinary search treetree nodedata structuresalgorithmsbsenyurtİkili ağaç yapısı basitliği ve hızlı sonuç üretimi açısından bakıldığında, arama algoritmalarından tutunda oyun programlamaya, ilişkisel veri tabanlarından, karmaşık matematik modellere kadar pek çok alanda kullanılmaktadır...https://buraksenyurt.com/pingback.axdhttps://buraksenyurt.com/post.aspx?id=2a391f82-1748-4b19-be3c-fdf54abc76e10https://buraksenyurt.com/trackback.axd?id=2a391f82-1748-4b19-be3c-fdf54abc76e1https://buraksenyurt.com/post/Binary-Search-Tree-yi-Anlamak#commenthttps://buraksenyurt.com/syndication.axd?post=2a391f82-1748-4b19-be3c-fdf54abc76e1