Atree: Basit ve Verimli, İşaretçisiz Bir Tree Uygulaması

• C++ ile Apter Trees
• Yalnızca iki vektör kullanarak, (düğüm değeri, ebeveyn indeksi) ile sade biçimde ifade edilen bir tree
• Çoğu tree, ikili tree gibi uygulanır ve her düğüm kendi değeriyle birlikte sol/sağ çocuk düğümlere işaret eden pointer'lar içerir
• Bu tür veri yapıları genellikle özyinelemeli olarak uygulanır ve cache davranışı ile sık malloc() çağrıları nedeniyle yavaş olabilir
• Bir tree düğümüne kimin "sahip olduğu" kavramı, çok katmanlı yazılımlarda karmaşık hale gelebilir
• Apter tree çok daha hızlıdır, hakkında akıl yürütmesi daha kolaydır ve uygulanması daha basittir

Nasıl çalışır

• Aynı boyutta iki diziyle uygulanır
  • Verinin vektörü (dizi) d
  • Ebeveyn indekslerinin vektörü p. d vektöründeki indeks anahtar olarak kullanılır (c)
  • Çoğu zaman anahtar/indeks c bir tamsayıdır
• Coco, Molly ve Arca'nın ebeveyniyse ve Arca'nın da Cricket adında bir çocuğu varsa yapı aşağıdaki gibi olur
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• Ebeveyni 0 olan ve anahtarı 0 olan düğüm kök düğümdür (Apter tree'de kök düğüm zorunludur ya da -1 "ebeveyn yok" anlamına gelir, ancak burada bunu göz ardı ediyoruz)
• Bilgisayarlar vektörleri çok hızlı işler. Pointer işlemlerinden çok daha hızlı oldukları için, algoritmaların Big-O gösterimini karşılaştırmak pratikte pek anlamlı değildir

Neden önemli

• Bu uygulama biçimi, yazarın gördüğü tree uygulamaları arasında en zarif olanı
• Uygun bir vektör işlemleri kütüphanesiyle kullanıldığında anlaşılması kolay ve hata ayıklaması kolaydır
• Basitliği sayesinde başka kullanım senaryolarına da kolayca uyarlanabilir
• Ebeveyn indeks vektörünü yok sayıp değerler üzerinde hızlıca yineleme yapılabilir; bu da ücretsiz bir Deep Map gibidir
• GPU dostudur ve gömülü ortamlarda kullanımı kolaydır
• Vektörlerin belirli bir boyutun ötesine büyümesini engelleyerek güvenliği korumak daha kolay hale gelir

Kökeni

• Bu tekniği kimin icat ettiğini bulmaya çalışıyor; 60'lar ve 70'lerdeki vektör odaklı dönemde bunun zaten bir adı olduğunu tahmin ediyor
• İlk tam açıklamayı Apter'ın anlattığı biçimde görmüş olsa da, K3'te de kapsamlı biçimde belgelenmiş
• APL, tree'leri geleneksel biçimde uygular ama vektör graph'lar için benzer teknikler kullanır
• J kullanıcıları arasında da biliniyor; Rosetta Code'da J dilinde tree uygulamasına dair bir açıklama var
• John Earnest, silinmiş öğeler için "offset index" yaklaşımı da dahil olmak üzere vektör tree uygulamasını daha ayrıntılı açıklar
• Daha karmaşık bir yaklaşım ise her öğenin derinliğini takip etmektir

Diğer yaygın tree uygulamaları

• FreeBSD'nin kernel tree uygulaması, klib'in tree'leri, Ruby'nin tree sınıfı ve Python'un bildirime dayalı tree sınıfı gibi örnekler var
• Bunlar Apter tree ile aynı işlevi yerine getirmez; bazıları genelleştirme nedeniyle çok daha büyüktür

Bu kodun durumu

• Bunu, C++17 öğrenmek için bir uygulama denemesi olarak yazmış
• Henüz kullanıma hazır değil ve C++ hakkında daha fazla şey öğrenmesi gerekiyor

GN⁺'un görüşü

• Apter Trees, mevcut karmaşık tree yapılarını sadeleştirerek hızlı ve verimli veri yönetimini mümkün kılar
• Vektör tabanlı tree uygulaması, bellek ek yükünü en aza indirip doğrusal erişimle performansı artırabilir
• Bu yazı, yazılım mühendisliğinde veri yapılarına yönelik yenilikçi yaklaşımları keşfetmek açısından ilgi çekici

[GN⁺]

Hacker News görüşleri

• Bir kullanıcı, kendi çalışmasının Hacker News'te bağlantılanmış olduğunu görünce şaşırdığını ifade etti. Hafif, dizi tabanlı veri yapılarıyla ilgilendiğini ve özellikle 3D model skinning için düğüm ağaçlarında sık kullanılan bir uygulama biçiminden bahsetti. Dizi, ebeveyn düğümler çocuk düğümlerden önce gelecek şekilde sıralanırsa, tüm düğümler için world transform'un yeniden hesaplanmasının basit bir döngüyle yapılabileceğini açıkladı.
• Başka bir kullanıcı, bu tür ağaç stilinde çocuk düğümleri yinelemenin O(N) olduğuna dair yoruma karşılık, ilk çocuk ve sonraki kardeş işaretçileri ekleyerek atree tasarımını genelleştirmenin aslında kolay olduğunu belirtti. Ayrıca, gereken işlemleri desteklemek için veri yapısını değiştirmenin tavsiye edildiğini söyledi.
• Bir kullanıcı, düğümleri bir dizide depolayıp indeksleri işaretçi olarak kullanmanın ağaç algoritmalarını uygulamak için temel olduğunu savundu. Özellikle düğümün çocuklarına erişmek gerekiyorsa, bellek tasarrufu için iç düğümler ile yaprak düğümler için ayrı yapılar düşünülmesini önerdi.
• Başka bir kullanıcı, bir ağacı parent array ile temsil etme yaklaşımının Hacker News'te bu kadar ilgi görmesinin biraz tuhaf olduğunu söyledi. Bunun, iyi bir sunumun temel bir fikri ne kadar ileri taşıyabildiğini gösterdiğini düşündü.
• Bir kullanıcı, bu projenin sistem işaretçilerini kendi işaretçileriyle değiştirmekten ibaret olduğuna dikkat çekti.
• Başka bir kullanıcı, malloc çağrılarını azaltmak ve veri yerelliğini artırmak isteniyorsa, düğüm havuzu kullanan geleneksel bir ağaç uygulamasının denenmesini önerdi.
• Aaron Hsu'nun APL kullanarak yaptığı açıklamaya bakılmasını tavsiye eden bir yorum da vardı.
• Bir kullanıcı, bir düğümün tüm çocuklarını birlikte paketleyen bir yapısal değişiklik önerdi. Böylece ikili aramayla düğümün tüm çocuk listesinin bulunabileceğini ve bunun önbellek dostu özellikler taşıyacağını belirtti.
• Dizideki indekslere handle veya index-handle denmesiyle ilgili bir yorum vardı; ayrıca bu ağaç gösteriminin heap ve disjoint set gibi klasik veri yapılarını hatırlattığı söylendi.
• Son olarak bir yorumda, dizi indekslerinin de bir tür pointer sayılabileceği ve geleneksel ağaç uygulamalarında malloc gereksiniminin düğümlerin dinamik olarak eklenip çıkarılması ihtiyacından kaynaklandığı açıklandı. Ağacın boyutu sınırlıysa ve sık silme yapılmıyorsa, dizi uygulamasının uygun olabileceği belirtildi.