Add | Engin Polat\'ın Windows 8 , Windows Phone 8 ve C# içerikli programcılık sitesi

Arşiv

Etiketlenen yazılar add

Generic Priority Queue Yazalım

06 April 2013 Yorum yapılmamış

Queue yapıları, ilk gelen ilk çıkar (first in-first out, FIFO) mantığı ile çalışan listelerdir. C# dilinde yeralan Queue<T> sınıfı bu mantık ile çalışan bir yapıdadır.

Queue sınıfına Dequeue methodu ile de eklenmiş elemanları sırası ile okuyabiliriz.

Projelerimizde sıklıkla Queue sınıfına ihtiyaç duyarız. Örneğin, üye kaydı oluşturan kullanıcılara mail ile erişim bilgileri iletileceği durumda, her yeni oluşturulan üye kaydını bir queue‘ya ekleriz, arka planda çalışan bir servis, queue‘da eleman oldukça alır, veritabanında gerekli kayıtları oluşturduktan, yetkileri tanımladıktan, vs. sonra email gönderme işlemini yapar.

Bazı durumlarda bu senaryo yetersiz kalabilir. Özellikle queue‘ya eklenen elemanlar arasında önceliklendirme yapamadığımız için, yeni kullanıcıya gönderilecek mail ile şifresini unutan kullanıcıya gönderilecek şifre hatırlatma maili aynı önceliğe sahip oluyor.

Queue sınıfına öncelikler eklemeye karar verdik, peki nasıl yapacağız? Başlangıç olarak PriorityQueue sınıfı oluşturalım;

public class PriorityQueue<TPriority, TItem>
{
}

PriorityQueue sınıfına her öncelik tipi için Queue barındıracak aşağıdaki değişken tanımlamasını ekleyelim;

public class PriorityQueue<TPriority, TItem>
{
	private SortedDictionary<TPriority, Queue<TItem>> _subqueues;
}

PriorityQueue sınıfının constructor‘ında _subqueues değişkenine değer ataması yapalım;

public PriorityQueue()
{
	_subqueues = new SortedDictionary<TPriority, Queue<TItem>>();
}

Sırada bekleyen eleman var mı, varsa kaç eleman var sorularını cevaplayacak iki property ekleyelim;

public bool HasItems
{
	get { return _subqueues.Any(); }
}
public int Count
{
	get { return _subqueues.Sum(q => q.Value.Count); }
}

İlgili öncelik tipine eleman ekleme işini yapacak Enqueue method’unu yazalım;

public void Enqueue(TPriority priority, TItem item)
{
	if (!_subqueues.ContainsKey(priority))
	{
		_subqueues.Add(priority, new Queue<TItem>());
	}
 
	_subqueues[priority].Enqueue(item);
}

Eğer ilgili öncelik tipi öncelikler listesinde yoksa, ilk olarak öncelik tipine ait yeni queue oluşturuluyor, sonra eleman öncelik tipinin listesine ekleniyor.

Öncelik tipinin listesinden eleman okumak için gerekli Dequeue method’unu da yazalım;

public TItem Dequeue()
{
	if (_subqueues.Any())
	{
		KeyValuePair<TPriority, Queue<TItem>> first = _subqueues.First();

		TItem nextItem = first.Value.Dequeue();

		if (!first.Value.Any())
		{
			_subqueues.Remove(first.Key);
		}

		return nextItem;
	}
	else
	{
		throw new InvalidOperationException("Queue'da hiç eleman yok!");
	}
}

Örnek kullanım;

var queue = new PriorityQueue<int, string>();
 
queue.Enqueue(1, "A-1");
queue.Enqueue(2, "A-2");
queue.Enqueue(3, "A-3");
queue.Enqueue(1, "B-1");
queue.Enqueue(2, "B-2");
queue.Enqueue(3, "B-3");
queue.Enqueue(1, "C-1");
queue.Enqueue(2, "C-2");
queue.Enqueue(3, "C-3");

while (queue.HasItems)
{
	Console.WriteLine(queue.Dequeue());
}

// ÇIKTI
// A-1
// B-1
// C-1
// A-2
// B-2
// C-2
// A-3
// B-3
// C-3

Kaynak : http://www.blackwasp.co.uk/PriorityQueue.aspx

Euler – 7

17 October 2011 Yorum yapılmamış

Euler serisinin yedinci yazısında, Project Euler’in 7. sorusunu çözeceğiz;

Orjinal Soru; By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10.001st prime number?

Türkçesi; İlk altı asal sayı: 2, 3, 5, 7, 11, ve 13, altıncı asal asal sayının 13 olduğunu görürüz.

10.001nci asal sayı kaçtır?

Önce siz çözmeyi deneyin, çözemezseniz Devamını oku…

Generic Dictionary sınıfına karıştırıcı (shuffle) Extension Method yazalım

03 October 2011 Yorum yapılmamış

Winamp MP3 oynatıcısında çalma listesini (playlist) rastgele sıra ile karıştırabiliyorsunuz. Benzer özelliği kendi projelerimizde uygulamak isteyebiliriz.

Daha önce, C# ile Dizi Karıştırma yazısında bir dizi’yi (List<T>) nasıl karıştıracağımızı incelemiştik.

Bu yazı ile Karıştırma (Shuffle) yeteneğini Generic Dictionary (Dictionary<TKey, TValue>) ekleyeceğimizi inceleyeceğiz.

İlk olarak, ExtensionManager isminde static bir sınıf oluşturalım;

public static class ExtensionManager
{
	public static Dictionary<TKey, TValue> Shuffle(this Dictionary<TKey, TValue> liste)
	{
		Random r = new Random();
		return liste.OrderBy(x => r.Next()).ToDictionary(item => item.Key, item => item.Value);
	}
}

ExtensionManager sınıfının Shuffle() isminde bir method’u var.

Bu method, Random sınıfından yeni bir instance‘ın Next() method’unu kullanarak, liste değişkeninin her bir elemanını rastgele bir değerle sıralıyor.

Böylece, Shuffle() method’u her çağırıldığında liste değişkeninin elemanlarının rastgele sıralandığını görüyoruz.

Örnek Kullanım;

Dictionary<int, string> liste = new Dictionary<int, string>();

for (int iLoop = 0; iLoop < 5; iLoop++)
{
	liste.Add(iLoop, "Eleman " + iLoop);
}
//0, Eleman 0
//1, Eleman 1
//2, Eleman 2
//3, Eleman 3
//4, Eleman 4

Dictionary<int, string> karistirilmis = liste.Shuffle();
//2, Eleman 2
//1, Eleman 1
//3, Eleman 3
//0, Eleman 0
//4, Eleman 4

C# SortedSet sınıfı

31 October 2010 1 yorum

SortedSet sınıfı, .Net Framework 4.0 ile birlikte gelen en yeni sınıflardan biridir ve listesine eklenen elemanları sıralı bir şekilde tutar.

Bir örnek ile göstermek gerekirse;

public static void Main(string[] args)
{
	var SiraliListe = new SortedSet<string>();

	SiraliListe.Add("Engin");
	SiraliListe.Add("Ahmet");
	SiraliListe.Add("Mehmet");
	SiraliListe.Add("Ayşe");
	SiraliListe.Add("Fatma");

	foreach (string s in SiraliListe)
	{
		Console.WriteLine(s);
	}

	Console.ReadLine();
}

kodunun çıktısı aşağıdaki gibi olacaktır;

Ahmet
Ayşe
Engin
Fatma
Mehmet
public static void Main(string[] args)
{
	var SiraliListe = new SortedSet<int>() { 2, 5, 4, 6, 9, 3, 2, 8, 10, 7, 1 };

	foreach (int Sayi in SiraliListe)
	{
		Console.WriteLine(Sayi);
	}

	Console.ReadLine();
}
Çıktı : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Tüm koleksiyonlara uygulayabildiğimiz Reverse() methodu SortedSet sınıfında da kullanılabiliyor;

public static void Main(string[] args)
{
	var SiraliListe = new SortedSet<int>() { 2, 5, 4, 6, 9, 3, 2, 8, 10, 7, 1 };

	foreach (int Sayi in SiraliListe.Reverse())
	{
		Console.WriteLine(Sayi);
	}

	Console.ReadLine();
}
Çıktı : 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

Clear() methodu, tüm elemanları silmeye yarıyor;

public static void Main(string[] args)
{
	var SiraliListe = new SortedSet() { 2, 5, 4, 6, 9, 3, 2, 8, 10, 7, 1 };

	SiraliListe.Clear();

	Console.ReadLine();
}

Min ve Max özellikleri sayesinde listedeki en küçük ve en büyük değerli elemanlara ulaşabiliriz;

public static void Main(string[] args)
{
	var SiraliListe = new SortedSet<int>() { 2, 5, 4, 6, 9, 3, 2, 8, 10, 7, 1 };

	Console.WriteLine("Min : {0}, Max : {1}", SiraliListe.Min, SiraliListe.Max);

	Console.ReadLine();
}
Çıktı : Min : 1, Max : 10

For – ForEach – List.ForEach performans karşılaştırması

31 October 2010 1 yorum

Bir dizinin tüm elemanları üzerinde bir aksiyon gerçekleştirmemiz gerektiğinde, sıklıkla şu üç yoldan birini kullanırız;

  • For döngüsü
  • ForEach Döngüsü
  • List generic sınıfının ForEach extension method’u

Şimdi basit bir örnek ile bu üç yöntemi karşılaştıralım (*);

(* Not : Karşılaştırmalar; Windows7 64bit kurulu, Core2Duo 3.0 GHz ve 4 GB Ram’li bilgisayarımda yapılmıştır. Sadece fikir verme amaçlıdır, farklı durumlarda faklı sonuçlar ile karşılaşılabilir.)

Öncelikle parametre olarak Generic List (List<T>) alan üç tane method yazalım;

private static long ToplamFor(List<int> Liste)
{
	long Sonuc = 0;
	int ListeAdet = Liste.Count;

	for (int iLoop = 0; iLoop < ListeAdet; iLoop++)
		Sonuc += Liste[iLoop];

	return Sonuc;
}

private static long ToplamForEach(List<int> Liste)
{
	long Sonuc = 0;

	foreach (int Rakam in Liste)
		Sonuc += Rakam;

	return Sonuc;
}

private static long ToplamForEachExtension(List<int> Liste)
{
	long Sonuc = 0;

	Liste.ForEach(Rakam => Sonuc += Rakam);

	return Sonuc;
}

Aynı testi 10 defa gerçekleştirip, ortalamasını alacak bir test fonksiyonu yazalım. Yazacağımız fonksiyonu test listesinde olacak eleman adedini parametre olarak alacak;

private static void Testler(int ListeElemanAdet)
{
	List<int> ForSureler = new List<int>();
	List<int> ForEachSureler = new List<int>();
	List<int> ForEachExtensionSureler = new List<int>();

	List<int> TestVerisi = Enumerable.Range(0, ListeElemanAdet).ToList();

	Stopwatch sw = new Stopwatch();

	for (int iLoop = 0; iLoop < 10; iLoop++)
	{
		sw.Restart();
		ToplamFor(TestVerisi);
		sw.Stop();
		ForSureler.Add(sw.ElapsedTicks);

		sw.Restart();
		ToplamForEach(TestVerisi);
		sw.Stop();
		ForEachSureler.Add(sw.ElapsedTicks);

		sw.Restart();
		ToplamForEachExtension(TestVerisi);
		sw.Stop();
		ForEachExtensionSureler.Add(sw.ElapsedTicks);
	}

	Console.WriteLine("For Döngüsü ({0} Eleman) : {1}", ListeElemanAdet, ForSureler.Average());

	Console.WriteLine("ForEach Döngüsü ({0} Eleman) : {1}", ListeElemanAdet, ForEachSureler.Average());

	Console.WriteLine("ForEach Extension ({0} Eleman) : {1}", ListeElemanAdet, ForEachExtensionSureler.Average());
}

Artık uygulamamızın test fonksiyonunu kullanacak son kod parçasını yazabiliriz;

public static void Main(string[] args)
{
	Console.WriteLine("Test Başladı");

	Testler(1000);
	Testler(5000);
	Testler(10000);
	Testler(50000);
	Testler(100000);
	Testler(500000);
	Testler(1000000);
	Testler(5000000);
	Testler(10000000);
	Testler(50000000);

	Console.WriteLine("Test Bitti");

	Console.ReadLine();
}

Bakalım yaptığımız testler nasıl sonuç vermiş;

For - ForEach - ForEach extension Performans Karşılaştırması / Ekran Görüntüsü

Sonuçlardan aşağıdaki tabloyu çıkarttım;

Test Verisi For ForEach ForEach Extension
1.000 71,1 121,5 79,7
5.000 34,3 92,2 55,6
10.000 70,0 185,1 110,4
50.000 349,3 918,4 568,3
100.000 715,2 1.902,7 1.159,0
500.000 3.583,3 9.379,3 5.600,0
1.000.000 7.260,4 18.877,9 11.242,8
5.000.000 37.927,2 96.096,9 57.845,4
10.000.000 74.553,5 192.621,6 115.559,6
50.000.000 371.698,1 956.394,4 572.776,7

İlk olarak 50.000 elemana kadar olan listeler için karşılaştırma yapalım;

For - ForEach - ForEach extension Performans Karşılaştırması / 50.000 elemana kadar inceleme

Son olarak 50.000.000 elemana kadar olan listeler için karşılaştırma yapalım;

For - ForEach - ForEach extension Performans Karşılaştırması / 50.000.000 elemana kadar inceleme