Alıntı (acehreli):

Eğer, "Associative Array" ve "Hash Table" gibi şeylerle ilgileniyorsan şu kodu tersine mühendislik ile incelemeni tavsiye ediyorum: https://github.com/9rnsr/New-AA-implementation/blob/master/newAA.d

Her ne kadar 1000 satırı aşan bir kod olsa da içindeki unittest'leri ve fazla satırları çıkarırsak sanırım 500 satır ya var ya yoktur. Buna rağmen içeriğinde asal sayılardan tutta da verilerin sıralanmasına kadar çok güzel bilgiler yer alıyor. Anlamadığın şeyler olursa kodun ilgili bölümünü ayrı bir başlık açıp bizlere sorabilirsin. Sanırım konuyu hatim etmemen için hiç bir sebep yok; belki biraz vakit lazım...:D

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (huseyin325325):

Eşleme tablosunu hash table veri yapısının karşılığı olarak kullanıyoruz. Diğer veri yapıları gibi bu da özel bir kısıtlaması bulunmayan her dilde gerçekleştirilebilir.

Dil böyle bir olanak getirmediğinde bir hash table yapısı yazılır ve kullanılır. Benim çalıştığım yerdeki C kütüphanelerinde bile böyle bir yapı var ama kullanımının ne kadar külfetli olduğunu anlatamam. :)

Alıntı:

O zaman da bir ağaç yapısından bahsediyoruz.

Alıntı:

Hash table olsa gerçekten de nereyse hemen atlanır (tablodaki eleman adedinden bağımsız olarak). İkili ağaçta ise ağaçtaki eleman adedi N ise O(log N) karmaşıklığında atlanır (kabaca, 1000 eleman varsa düğümlerde 10 kere ilerleyerek (çünkü 2^^10 1024'tür)).

Eğer D'nin eşleme tablolarını kullanmak istemiyorsan bence bu işe başlamadan önce veri yapılarını öğrenmek isteyebilirsin. Erdem de şu sıralarda bununla eğleniyor. :)

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (Salih Dinçer):

Orada bir terim karışıklığı var. Bağlı liste (linked list) ve ağaç (tree) farklı veri yapılarıdır.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Evet biraz daha araştırmam gerek bu konular çok sağlam bilgi istiyor :/ Sizden birşey rica edebilir miyim ?
Daha önceden incelediğim şeylerin arasında memphis( http://memphis.compilertools.net/ ) adında bir tree walker var ancak kullanımı hakkında çok bilgi sahibi olamadım bizim yapmamız gereken şey bu mu acaba ? (Ricam: Bunu incelemeniz :) )

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (acehreli:1348252277):

Farkı ne hocam?

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

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...:)

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

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

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (Salih Dinçer):

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.

Alıntı:

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.

Alıntı:

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

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

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ı...:)

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

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:

Alıntı (Post Order):

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?

Alıntı (Post Order):

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...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]