Permalink
Reply
Merhaba,
İstanbul'dayım (bir hafta tatil yapmıştım) ve gelir gelmez uzunca uyudum. Hani uykuda bir sorunu düşününce cevabı uyku ile beraber geliyor ya iyi oldu. Bir taşla iki kuş hesabı...:)
Şuradaki başlık (http://ddili.org/forum/thread/943)ta Hüseyin kardeşimiz, diğerleri gibi çok ilginç konuda bir soru sormuştu ve bu soru bizi veri yapılarında çok temel öğelerine (bağlı liste, yığın, ağaç, öbek vb.) götürmüştü. Akabinde, bilgi eksikliğimi tamamlamaya (şu Youtube vidyosundaki ders gibi (http://www.youtube.com/watch?v=V_3BM0ykITM)) gayret ettim ama gel gör ki bir sarmaşık ağacı gibi karışık şeylerle karşılaştım...:D
Ancak, kağıt kalemi eline alınca okuyacağınız sayfalarca yazıdan daha verimli olduğunu söyleyebilirim...
Nerede kalmıştık, şöyle bir soru sormuştum:
Alıntı (Salih Dinçer:1348532924):
>Peki hocam; kodumuzda 2^5 elemanlı bir verimiz olsun, örneğin bir dizi. Bu durumda dizi 32 elemanda oluşur ve sağ/sol diye ikili ağaç (binary tree) kurarsak şöyle olmaz mı?
> auto veri = [ 90, 10, 20, 30, 40, 50, 60, 70, 80,
> 5, 15, 25, 35, 45, 55, 65, 75, 85,
> 100, 200, 300, 400, 500, 600, 700,
> 150, 250, 350, 450, 550, 650, 750
> ];//*/
> /* 90
> * ----------
> * / \
> * 10 100
> * / \ \
> * 5 20 200
> * / \ / \
> * 15 30 150 300
> * / \ / \
> * 25 40 250 400
> * / \ / \
> * 35 50 350 500
> * / \ / \
> * 45 60 450 600
> * / \ / \
> * 55 70 550 700
> * / \ / \
> * 65 80 650 750
> * \
> * 85
> */
> ```
> Bu durumda 85'i bulması için 5 değil 10 adım gerekli. Yoksa hile mi yaptım! Ağaç yapısı daha mı farklı olacaktı...:)
>
Meğer bu sayılardan en verimli yapı şu şekilde oluşturuluyormuş:
auto veri = [ 85, /* en tepedeki kök (root) /
45, 25, 65, / soldaki ilk iki dal /
15, 10, 20, / sonraki birinci dalın, soldaki ikilisi /
35, 30, 40, / sağdaki ikilisi /
55, 50, 60, / sonraki ikinci dalın, soldaki ikilisi /
75, 70, 80, / sağdaki ikilisi /
145,125,165, / sağdaki büyükler... /
115,110,120, / yukarıdaki gibiler */
135,130,140,
155,150,160,
175,170,180 ];
/* 85
* /
* 45 145
* / \ /
* 25 65 125 165
* / \ / \ / \ /
* 15 35 55 75 115 135 155 175
* / \ / \ / \ / \ / \ / \ / \ /
* 10 20 30 40 50 60 70 80 110 120 130 140 150 160 170 180
*/
Bu ağaç yapısın (veriyi) şuradaki kod (<http://ddili.org/forum/post/7810>) ile deneyebilir ve hafızada farklı şekilde temsil edilen veri ağacı üzerinde arama yapabilirsiniz. Böylece yarı yarıya daha verimli arama sonucu elde edebiliyorsunuz. Basit bir şekilde rasgele aramalar yapıldığında, ortalaması 3,6 ila 5,3 karşılaştırma arasında değişiyor. Oysa ilk naklettiğim 7 ila 10 arasında değerler gördüm. Tabi bunlar toplam karşılaştırmanın bulunan sayı adetine bölümü olduğunun altını çizmeliyim.
Yine de binlerce test yapmadığım için aralıkta küçük sapmalar olası. Buna rağmen %50 optimize edildiği söylenebilir. Sıra geldi herhangi bir veriyi bu yapıya gelmesini zorlamak. Sanırım basit bir şekilde dallar arasında yer değiştirme yeterli olacak.
Başarılar...
--
[ Bu gönderi, <http://ddili.org/forum>'dan dönüştürülmüştür. ]