Forum: Diğer Konular RSS
D ile Bir Programlama Dili Yapmak
Sayfa:  önceki  1  2 
acehreli (Moderatör) #16
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj ID 7787
Bağlı liste (linked list) bir tren gibi art arda bağlanmış düğümlerden oluşur. Aslında kullanım alanı çok dar bir veri yapısıdır.

Örnek olarak, bir sunucu kendisine gelen istekleri çabucak bir listenin sonuna ekleyebilir ve listenin başından işler. Böyle bir uygulamada elemanların sıralı (alfabetik veya sayısal) durmalarının gereği yoktur.

Hatta, eleman aramaya bile çok elverişsizdir çünkü sırayla aramak zorundayızdır ve dolayısıyla arama O(N) karmaşıklıktadır. Yani ne kadar çok eleman varsa arama o kadar uzun sürer.

Ağaç (tabii aslında hep ikili ağacı (binary tree) kastediyoruz) ise her birisi iki daldan oluşan düğümlerden oluşur. Soldaki düğüm sıralamada önceki elemanlara, sağdaki düğüm de sıralamada sonraki elemanlara ulaştırır.

Ağaçlar elemanların sıralı durmalarının gerektiği uygulamalara çok elverişlidirler çünkü istenen elemana normal bir dağılımda O(log N) karmaşıklıkta eriştirirler. Aynı ikili arama algoritması gibi... Bilmeyenler için, log N deyince "ikinin hangi kuvveti N'i veriyorsa" demek oluyor. Örneğin, 1000 eleman varsa onu kabaca 1024'e eşit kabul ederiz. 1024 de ikinin onuncu kuvvetidir. Demek ki 1000 elemanlı bir ağaçta istediğimiz elemanı 10 karşılaştırmayla bulacağız demektir. Çok hızlı. :)

Ali
Avatar
Salih Dinçer #17
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yani Huffman ile basit içerikli bir ağaç yapısı arasındaki fark kadar mı? Sonuçta dolaşıcı (iterator) bağlı liste üzerinde gezme kavramı ile tree walker çok farklı şeyler değilmiş gibi...

Öyle ya ikisi de bir hiyearşik bir ağaç yapısına sahipler. Eğer gerçek hayatta bir ağacın çevresinde gezen yılan ile dallar arasında gezen bir solucan arasındaki fark gibiyse sonuçta ikisi de veri bir şeyi üzerinde sürünüyorlar...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #18
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Salih Dinçer:
dolaşıcı (iterator) bağlı liste üzerinde gezme kavramı ile tree walker çok farklı şeyler değilmiş gibi...

Bakış açısına göre değişir. Erişim hızı açısından bakalım: 1000 elemanlı bağlı listedeki bir elemanı bulmak için ortalamada 500 karşılaştırma yapmam gerekir. Ağaçta ise 10 karşılaştırma. Yani o kadar eleman olunca 50 kat hız farkı.

Şimdi bir milyon elemana bakalım: Bağlı listede ortalama 500 bin. Ağaçta ise 20 karşılaştırma. Kaç kat? 25000! Yani bağlı liste 25 bin kat daha yavaş.

İşte bu açıdan bakınca çok farklılar.

Öyle ya ikisi de bir hiyearşik bir ağaç yapısına sahipler.

Bağlı liste bozuk bir ağaç yapısıdır: O ancak yalnızca sol veya yalnızca sağ dallarının kullanıldığı bir ağaç olarak görülebilir.

Eğer gerçek hayatta bir ağacın çevresinde gezen yılan ile dallar arasında gezen bir solucan arasındaki fark gibiyse sonuçta ikisi de veri bir şeyi üzerinde sürünüyorlar...:)

Güzel bir benzetme :) ama eğer liste ile ağacın aynı oldukları çıkarımına götürüyorsa çok yanlış.

Ali
Avatar
Salih Dinçer #19
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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ı...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #20
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Galiba sen ikili ağaçların dizi üzerine oturdukları çok özel bir veri yapısını düşünüyorsun: binary heap. (Bu "heap"in dinamik bellekle ilgili olarak duyduğumuz "heap" ile bir ilgisi yoktur.)

Ama belki de ikili ağaç yapısını başka bir düzende dizi üzerine oturtuyorsun. Ben ise klasik anlamdaki ikili ağaç (ve bağlı liste) veri yapısından bahsediyordum.

Eğer gerçekten binary heap'i düşündüysen veriler doğru görünmüyorlar. O verdiğin değerlerle heap şöyle oluşturulabilir:

import std.stdio;
import std.container;
 
void main()
{
    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 ];
 
    heapify(veri);
 
    writeln(veri);
}

Çıktısı:

[750, 500, 700, 100, 400, 600, 650, 75, 85, 300, 90, 50, 250, 450, 550, 70, 30, 10, 80, 200, 5, 40, 15, 20, 25, 150, 35, 350, 45, 60, 55, 65]

Bağlı listeyle ikili ağacın farklı veri yapılarında anlaştık ve binary heap'e geçtik, değil mi? :)

Ali
Avatar
Salih Dinçer #21
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Sanırım "heap" olayına ben geçmedim...:)

Ancak geçtiğimiz iyi oldu çünkü en iyi ağaç (optimize) yapısını oluşturma kafamı kurcalıyordu. Bu durumda bahsettiğin O(log N) olayı ve farkları ciddi şekilde değişiyor gibi. Örneğin heapify()'dan geçirilen verinin 'postorder'ı (soldan sağa dairesel dizilim) şöyle:

Post Order:
[ 5, 25, 20, 15, 10, 35, 45, 40, 30, 55, 65, 60, 70, 50, 80, 90, 85, 75, 150, 200, 250, 350, 300, 450, 400, 100, 550, 650, 600, 700, 500, 750 ]

Buradan anlıyoruz ki en sondaki eleman (750) en tepede. Peki veriyi ilk naklettiğim sırada en tepede 90 olacak şekilde işlersek ne olur?

Post Order:
[ 5, 15, 25, 35, 45, 55, 65, 75, 85, 80, 70, 60, 50, 40, 30, 20, 10, 150, 250, 350, 450, 550, 650, 750, 700, 600, 500, 400, 300, 200, 100, 90 ]

Diyelim ki 25'i arayacağız ve hemen yukarıdaki sıralamaya göre 5 sorgulamada bulmamız gerekiyor. Oysa Ali hocanın sıralamasında 10 sorgulamada buluyoruz. Şimdi burada sorulması gereken soru şu olabilir:

Veri yapılarını karşılaştırırken, en çabuk bulunabilen elemanın hızına göre mi karşılaştırma yapıyoruz; yoksa tüm elemanlara ortalama erişim sürelini hesaba katıyor muyuz? Açıkçası ben hala, veri yapılarının aynı anneden çıkan karındaş (kardeş) ürünler olduğunu düşünüyorum...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #22
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Salih Dinçer:
Örneğin heapify()'dan geçirilen verinin 'postorder'ı (soldan sağa dairesel dizilim) şöyle:
Belki de 'preorder'dan (kökden başlayarak dizilim) bahsetmeliydim. Bu durumda heapify()'dan geçen verinin ağaçta bulunma sıraları şöyle:

Pre-order:
[ 750, 500, 100, 75, 50, 30, 10, 5, 15, 20, 25, 40, 35, 45, 70, 60, 55, 65, 85, 80, 90, 400, 300, 250, 200, 150, 350, 450, 700, 600, 550, 650 ]

İlk naklettiğim sırada ise şöyle:

Pre-order:
[ 90, 10, 5, 20, 15, 30, 25, 40, 35, 50, 45, 60, 55, 70, 65, 80, 75, 85, 100, 200, 150, 300, 250, 400, 350, 500, 450, 600, 550, 700, 650, 750 ]
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #23
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #21
Salih Dinçer:
Örneğin heapify()'dan geçirilen verinin 'postorder'ı (soldan sağa dairesel dizilim) şöyle:

Anlayamıyorum. :( Veriyi belirli bir düzende saklamak başka, preorder veya postorder olarak işlemek başka.

en tepede 90 olacak şekilde işlersek ne olur?

Bilmiyorum. O yine de binary heap mi? Çünkü benim bildiğim kadarıyla her eleman eklendiğinde elemanların yer değiştirerek binary heap'in tutarlılığının korunması gerekiyor. Tamam, verdiğin dizi öyledir herhalde ama ben soruyu anlamadım.

Diyelim ki 25'i arayacağız ve hemen yukarıdaki sıralamaya göre 5 sorgulamada bulmamız gerekiyor. Oysa Ali hocanın sıralamasında 10 sorgulamada buluyoruz.

Aslında binary heap aramaya uygun bir veri yapısı değil. Ortaya attığım için kusura bakma. Herşey karıştı.

Şimdi burada sorulması gereken soru şu olabilir:

Veri yapılarını karşılaştırırken, en çabuk bulunabilen elemanın hızına göre mi karşılaştırma yapıyoruz; yoksa tüm elemanlara ortalama erişim sürelini hesaba katıyor muyuz?

Hepsi: En iyi durumda nasıl? Ortalamada nasıl? En kötü durumda nasıl?

Açıkçası ben hala, veri yapılarının aynı anneden çıkan karındaş (kardeş) ürünler olduğunu düşünüyorum...

Hepsi aynı babadan olamazlar ama. Bazıları da doğumdan kusurlu... :(

Ali
Avatar
Salih Dinçer #24
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Sondaki uzun soru dışında öncekiler bir incelemeydi ve emin olmadığım çok şey vardı. Bilmediğimden saçma sorular sormuş olabilirim. Cevaplar için teşekkürler, denemeye devam...:)

Son olarak binary heap'in her eleman eklendiğinde güncellenmesi diye bir şey olduğunu yeni öğreniyorum. Bu durumda hız denemelerinde ya bunu da dikkate almalı ya da yukarıda yaptığımız gibi durağan (static) değerler ile deneme yapmalıyım.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
Salih Dinçer #25
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #22
Salih Dinçer:
Pre-order:
[ 750, 500, 100, 75, 50, 30, 10, 5, 15, 20, 25, 40, 35, 45, 70, 60, 55, 65, 85, 80, 90, 400, 300, 250, 200, 150, 350, 450, 700, 600, 550, 650 ]

İlk naklettiğim sırada ise şöyle:

Pre-order:
[ 90, 10, 5, 20, 15, 30, 25, 40, 35, 50, 45, 60, 55, 70, 65, 80, 75, 85, 100, 200, 150, 300, 250, 400, 350, 500, 450, 600, 550, 700, 650, 750 ]

Eğer mantığını doğru kavradıysam, soldakileri ve sağdakileri ayrı sıralarsak bu daha iyi gibi:

Pre-order:
[ 90, 85, 80, 70, 50, 40, 5, 15, 10, 25, 20, 35, 30, 45, 60, 55, 65, 75, 750, 500, 400, 300, 150, 100, 250, 200, 350, 450, 700, 650, 550, 600 ]

Bunu da şu şekilde ağaça (bitree) eklemeden önce yaptım:
    heapify(veri[1..18]); //baştaki en iyi kök elemanı almadım
    heapify(veri[18..$]);
    writeln(veri[1..18]);
    writeln(veri[18..$]);
Çıktısı:
[85, 80, 70, 75, 50, 60, 65, 40, 5, 15, 25, 35, 45, 55, 30, 20, 10]
[750, 500, 700, 400, 450, 650, 300, 150, 250, 350, 200, 550, 600, 100]


Aslında bu değerli konuyu artık burada devam etmeyip iyice olayları kavradıktan sonra ayrı bir başlık açmayı düşünüyorum; İstanbul'a dönünce...

Sevgiler, saygılar...
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Sayfa:  önceki  1  2 
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-18, 09:37:37 (UTC -08:00)