Sahte ağaçlar: Daha basit bir UI için girinti kullanmak

 (ratfactor.com)
4 puan yazan GN⁺ 2024-01-01 | 1 yorum | WhatsApp'ta paylaş
  • Hiyerarşik bir UI gerekli gibi görünse bile önce verinin gerçekten ebeveyn-çocuk ilişkisine sahip olması gerekip gerekmediğini, yoksa yalnızca öyle görünmesinin yeterli olup olmadığını kontrol etmek gerekir
  • Gerçek bir ağaca ihtiyaç yoksa, ekrandaki yapı ebeveyn ID’si yerine tüm listenin mutlak sıralama düzeni ve indent değeriyle ifade edilebilir
  • Hiss oyun editörü, banana.eat gibi adları sıraladıktan sonra noktanın (.) sonrasını girintili göstererek ad alanı gibi görünen bir UI oluşturur
  • Bu yaklaşım, kullanıcının öğeleri yukarı-aşağı taşıdığı ve girintiyi artırıp azalttığı kelime işlemci tarzı düzenlemeye daha yakındır; ağaç veri yapısı yükünü azaltır
  • Öğeler arasındaki ilişkiyi gerçekten sorgulamak veya korumak gerekiyorsa, girinti ya da dizge sembolü hileleri yerine gerçek bir ağaç modeli gerekir

Ağaç değil, ağaç gibi görünen liste

  • Bir uygulamada Foo, Bar gibi dinamik bir listeyi ağaç görünümü olarak göstermek istediğinizde, genellikle her öğeyi bir ebeveyn öğeye bağlayan bir yapı düşünülür
  • İlişkisel veritabanlarında, örneğin parent sütunuyla ebeveyn ID’si saklanabilir
    • Foo öğesinin parent değeri null
    • Foo 1 öğesinin parent değeri Foo
    • Foo 1.a öğesinin parent değeri Foo 1
  • Bu tür ağaç verisini SQL ile almak için özyinelemeli CTE gibi yöntemler gerekebilir
  • Ancak birçok listede, gerçek ilişkiden çok insanların rahat görebileceği düzenli bir görünüm daha önemli olabilir

Girinti değerini veri olarak saklama yöntemi

  • Gerçek bir ebeveyn-çocuk ilişkisine ihtiyaç yoksa liste yalnızca şu alanlarla saklanabilir
    • id
    • sort
    • indent
    • name
  • sort, alt öğeler içindeki sıra değil, tüm listenin mutlak sırasını ifade eder
  • indent, öğenin önüne konacak boşluk miktarını doğrudan gösterdiği için ekranda render etmek basitleşir
  • Düzenleme UI’si de ağaç manipülasyonundan daha basit hale gelebilir
    • Kullanıcı öğeleri yukarı ve aşağı taşıyabilir
    • Öğelerin girintisini artırabilir veya azaltabilir
    • Gerekirse doğru girintiyi zorunlu kılan basit kurallar eklenebilir
  • Sonuç olarak, bilgisayar bilimi ders kitabı tarzı veri yapılarını doğrudan manipüle etmekten çok, bir kelime işlemcide liste düzenleme deneyimine yaklaşır

Hiss’in nokta (.) tabanlı sahte ad alanı

  • Metin macerası oyunu editörü Hiss, banana, banana.eat, banana.peel gibi adları UI’da hiyerarşi gibi gösterir
  • HissScript’e gerçek bir ad alanı özelliği uygulanmış değildir
  • Uygulama yöntemi basittir
    • Nesne adları alfabetik olarak sıralanır
    • Adda nokta (.) varsa baştaki kısım kesilip çıkarılır
    • Kalan kısım girintili olarak yazdırılır
  • Örnek koddaki temel mantık da aynı akışı izler
    • things.keys sıralanır
    • Her adda nokta varsa, girinti eklendikten sonra noktanın öncesindeki kısım kaldırılarak yazdırılır
    • Nokta yoksa ad olduğu gibi yazdırılır
  • Daha sonra, verilen öneke sahip bir “ebeveyn” öğenin var olup olmadığını kontrol eden birkaç satır daha eklenir
  • Keyfi derinlikte iç içe geçme de eklenebilir, ancak gerçek ihtiyaç ortaya çıkana kadar bekletilmektedir
  • Bu ad alanı gibi görünen UI, oyunu düzenleyen kişi için önemlidir; ancak oyun editörü ve oyuncu açısından özel bir anlam taşımaz
    • Nokta içeren ad da sadece bir addır
    • Ad alanı gibi görünen kısım yalnızca adları benzersiz tutma işlevi görür

Düz liste olarak ele alınan ağaç benzeri örnekler

  • Dave Long, “düşük teknolojili gerçek ağaç” olarak yol ve bilgiyi düz listede saklama yöntemini önerir
  • Bu, banana.eat örneğine benzer bir içgörüdür
  • find çıktısı gibi şu biçimde bir yol listesi düşünülebilir
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • Derinlik öncelikli dolaşma gerekiyorsa yolları sözlük sırasına göre sıralamak yeterlidir
  • Genişlik öncelikli dolaşma gerekiyorsa, yolları yol ayırıcıya göre ters çevirmek, derinliği eşitlemek için boş öğeler eklemek ve sonra sıralamak mümkündür
  • Bu örnek kavramı göstermek içindir; pratikte ayırıcıya göre satırları bölüp dizi olarak işlemek daha doğaldır
  • Düz listeler genel olarak ele alması kolaydır ve mümkünse öğeleri plain old lists içine koyan yaklaşım tercih edilir

Yerdeki albüm benzetmesi

  • Kişisel albüm çalışmalarında fotoğraflar, notlar, kartpostallar ve biletler yere yayılıp gruplar oluşturulabilir
  • İnsanlar için grup ilişkisi açık görünse de zeminin kendisinde bu ilişkiyi zorunlu kılan fiziksel bir düzenek yoktur
  • Bu benzetmenin özü, ifade edilen ilişkinin ve gerçek yapısal ilişkinin farklı olabileceğidir
  • UI listeleri de benzer şekilde, insana hiyerarşi gibi görünen bir yerleşimin iç veri modelinde gerçek bir hiyerarşi anlamına gelmeyebileceğini gösterir

Gerçek bir ağacın gerekli olduğu durumlar

  • Girinti ya da dizge sembolü tabanlı yöntemler duruma göre ciddi biçimde uyarlanmalıdır ve genel programlama bağlamında hack olarak görülme olasılığı vardır
  • Öğeler arasındaki ilişkiyi gerçekten bilmek gerekiyorsa, ebeveyn ID’si, ebeveyn-çocuk join tablosu gibi veri modeline uygun gerçek bir ağaç yapısı kullanılmalıdır
  • Büyük ölçekli bir araştırma projesini sınıflandırmak gibi fiziksel dosya dolabı ve klasör düzeyinde organizasyon gücü gereken durumlarda “zemin yöntemi” uygun değildir
  • Öğeler arasındaki ilişkiyi daha sonra gerçekten bilmesi gereken bir projede, girintiyle ya da dizge içindeki sembol sayısıyla yapıyı taklit etmek, projenin ömrü ve bakım süresi boyunca acı verici bir yol haline gelebilir

İlgili okumalar

1 yorum

 
GN⁺ 2024-01-01
Hacker News yorumları

  • İlk yöntem, yani “elbette tek yol bu” gibi görünen yöntem, komşuluk listesi (adjacency list) olarak adlandırılır.
    İkinci “çok daha basit yöntem”i daha önce gördüğümü hatırlamıyorum; bariz dezavantajları var ama bazı durumlarda yeterli görünüyor.
    Üçüncü “ad alanına ayırma” yöntemi somutlaştırılmış yol (materialized path) olarak adlandırılır; ağaçları temsil etmenin bir başka yolu da iç içe kümelerdir (nested sets): https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    İnsanların ilişkisel veritabanlarını ciddiye aldığı dönemlerde bunların hepsi iyi bilinen şeylerdi; örneğin http://www.dbazine.com/oracle/or-articles/tropashko4/ gibi yazılar da var.
    Şimdilerde unutulmuş bilgi gibi görünüyor.

    • Eski iş yerimde en sevmediğim anlardan biri, bir sorunu açıklamak için epey uğraştıktan sonra birinin bunun zaten adı olan ve üzerine çalışılmış mevcut bir kavram olduğunu fark ettiği anlardı.
      Sorunun çeşitli yönlerini bizzat anlamaya çalışırken o kavramın mevcut adını bulmanın gerçekten zor olduğunu düşünüyorum.
    • Doğru. Bugünlerde işe aldığımız genç mezunlar her şeyi NoSQL belgelerine tıkıştırıyor ve veri modellemeyi neredeyse hiç düşünmek istemiyor.
      Sonunda ağacı gösteren tüm mantığı kodda ele alıyorlar; oysa modern ilişkisel veritabanları ve birkaç CTE ile birçok kullanım senaryosu zarif biçimde ve neredeyse bedavaya çözülebiliyor, bu yüzden üzücü.
    • Buna unutulmuş bilgi demek zor. “Joe Celko's Trees and Hierarchies in SQL” diye bir kitap da var.
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • Bu konuyla ilgileniyorsanız önce https://en.m.wikipedia.org/wiki/Joe_Celko sayfasındaki kitaplara bakmanızı öneririm.

  • Postgres’te bu şekilde yerel olarak çalışan bir ltree veri türü ve arama operatörleri var: https://www.postgresql.org/docs/current/ltree.html
    Örneğin CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy'); şeklinde ekleyip
    SELECT path FROM test WHERE path <@ 'Top.Science'; ile Top.Science ve Top.Science.Astronomy bulunabilir.

    • Programcılara not: ltree’nin tuhaf yanlarından biri, ağaç olarak çizildiğinde ebeveyn düğüm olacak ara yolların gerçekten var olmasının gerekmemesidir.
      Yukarıdaki örnekte Top.Science kaydını silseniz bile Top.Science.Astronomy kaydı budanmaz.
      Bir ltree değerinin etiketleri, somutlaştırılmış yol üzerinden mantıksal bir ağacı ima eder; ancak ima edilen tüm ebeveyn düğümlere karşılık gelen kayıtların varlığını zorunlu kılmaz.
      Uygulamaya göre bu tam olarak istediğiniz davranış da olabilir, tam tersi de. İkincisiyse bütünlüğü koruyacak ayrı bir mekanizma koymanız gerekir.
    • Dosya yollarını saklamak için ayırıcı olarak / kullanılıp kullanılamayacağını merak ediyorum.
    • Performans deneyimi olan var mı merak ediyorum. Çok fazla regex işleme varmış gibi görünüyor.
    • SQL Server’da da buna çok benzer bir özellik var[1] ve deneyimime göre oldukça iyi çalışıyor.
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • Aynı şeyin JSON sütunuyla da yapılıp yapılamayacağını merak ediyorum. Böylece düğümlerde string dışındaki veri türleri de kullanılabilir.
      Ancak JSON indekslerinin ltree indeksleri kadar iyi çalışmayabileceğinden endişeleniyorum.

  • Buradaki sorun şu: yapının içindeki değer çoğu zaman gösterim amaçlı ağaçta değil, verinin hiyerarşik yapısındadır
    Veriyi dolaşmak, ilişkileri göstermek veya yeniden sıralamak gibi işler yapma olasılığınız yüksektir
    Veritabanındaki veri yapısına görsel bilgi koymak tehlikeli ve kısa görüşlü görünüyor

    • Yazar zaten “insanlar her zaman ebeveyn-çocuk ilişkisini resmen kodlamaları gerektiğini düşünür, ama gerçekte bunun gerekmediği, yalnızca iç içe bir gösterimin gerekli olduğu durumlar da vardır” diye açıkça belirtmişken, buna verilen tepki biraz tuhaf
      Cevap “Hayır, böyle bir şey olamaz” mı?
      YAGNI’nin ünlü bir tasarım sezgiseli olmasının bir nedeni var. “Her zaman gerekeceğini varsay” doğru değil
    • İronik biçimde, verinin içinde hâlâ ebeveyn ID kullanılıyor
      Sadece optimize edilmiş bir veri tipinin özel sütununda saklamak yerine veri dizesinin başına eklenmiş
      Sayı olmayabilir ve ID sütunu olmayabilir, ama başka bir beklenen değere işaret eden bir tanımlayıcı olma özelliği değişmediği için biçimi değişti diye ebeveyn ID olmaktan çıkmıyor
    • Özgün metindeki sıra/girinti kodlama yönteminde de ebeveyn-çocuk ilişkisi kolayca yeniden kurulabilmeli
      Elbette ebeveynsiz çocuk gibi geçersiz girintilerin kaydedilmediği garanti edilmeli
      Bu yüzden en kolay yolun önce sıra/derinlik olarak saklamak, gerekli işlevler uygulanırken de ebeveyn/çocuk modeline geçiş yapmak olduğunu düşünüyorum
      Ancak “girinti”yi render edilecek boşluk sayısı olarak değil, ağaçtaki derinlik olarak daha soyut tanımlamak daha iyi. Hatalı veriyi bulmak kolaylaşır, sonraki geçiş de kolay olur; ayrıca iç içe /, sekme, 8 boşluk, 4 boşluk, 1 boşluk gibi kullanıcıya göre render esnekliği de sağlar
    • struct item_t { char key[255]; char display_value[255]; } gibi bir veri yapısı varsa ve anahtar a/b/c gibi tutarlı bir yol ayırıcısı içeriyorsa ebeveynleri ve çocukları bulmak çok kolaydır
      En kötü durumda diziyi doğrusal tararsınız; sıralıysa ebeveyne ulaşana kadar yalnızca önceki öğelere bakmanız yeterlidir
    • Kesinlikle katılıyorum. Denormalizasyon bazen iyi bir seçenek olabilir, ama bu durumda bunun makul bir gerekçe olduğunu düşünmüyorum

  • Ağaç biçimli verisi çok olan bir şirket kurmuştum. Bir ağaç yapısını girintili listeye dönüştürmek O(n) zamanda yapılabilir
    O zamanlar mülakat sorularımızdan biriydi ve çeşitli SQL veritabanlarında yinelemeli sorgular olmadan da ağacın bir bölümünü hızlıca alıp render edebilecek şekilde saklama yöntemleri var
    Bu kavramları anladıktan sonra veriyi düzgün biçimde ağaç olarak saklamanın, bu tür girintilere göre çok daha fazla avantajı var

    • Bu avantajlara ihtiyacınız yoksa pek önemli değil

  • “İlişkisel bir veritabanından SQL sorgusuyla ağaç yapılı veri almanın bir yolu recursive CTE’ler (Common Table Expressions) kullanmaktır; adı kadar eğlencelidir”
    CTE’ler, recursive CTE’ler dahil, korkulacak şeyler değildir; alışınca gerçekten eğlenceli olduklarını garanti ederim

    • CTE’ler pek de eğlenceli değil. İlgilendiğim kısmı debug etmek için tüm CTE kulesini başka bir SQL penceresine kopyalayıp yapıştırmak benim aradığım eğlence değil
    • Normalleştirilmiş bir temsilden ağaç verisini birleştirirken recursive CTE çok yavaştı
      Hiyerarşi derinliği d olan bir düğüm yolunu birleştirmek için sorgu sonucunu alma süresi en az d kat yavaşlıyordu
      Avantajı ağaç düzenleme işlemlerinin ucuz olmasıydı, ama bunlar okumalara kıyasla çok daha seyrek gerçekleşiyordu
    • CTE’ler gayet iyi. Yazar bu bilgiyi tabloya gömmek yerine, CTE ile biçimlendirilmiş ad içeren bir view da oluşturabilirdi

  • “İnsanlar aslında ağaç istemiyor veya buna ihtiyaç duymuyor; çoğu zaman yalnızca ağaç gibi görünen bir şeye ihtiyaç duyuyorlar” noktasında HN ile Reddit arasındaki farkı görüyoruz
    HN’de çocuk yorum, ebeveyn yorumun nextSibling’idir ve ebeveynin girinti değerine 1 eklenerek ağaç gibi görünmesi sağlanır
    Reddit’te, en azından old.reddit.com’da, çocuk yorum gerçekten ebeveyn yorumun içine iç içe yerleştirilir. Yeni siteyi bilmiyorum

    • Gerçek gösterimden değil, HTML yapısından bahsediyorsun, değil mi? Ekranda görünen hâli neredeyse aynı
    • Backend’de gerçekten böyle saklandığını hayal etmek zor
      Veri üzerindeki tüm işlemler, ağaç yapısını çıkarıp sonra yeniden örtük ağaç biçimine çevirmeyi gerektiren karmaşık bir keşmekeşe dönüşürdü
    • Öyleyse daraltmanın nasıl çalıştığını merak ediyorum

  • Yazının ana fikri basit: probleme uygun yapıyı kullanalım
    Ancak anlatının yanlış olduğunu düşünüyorum. Veritabanından ağaç almak için CTE şart değil; düz bir liste alıp ağacı yerelde kurabilirsiniz. Sonraki işlemler için de zaten muhtemelen bunu yapacaksınız
    Aynı mantıkla, liste saklamak için ilişkisel veritabanı kullanan birine de bunu metin dosyasında saklamasını söyleyebilirsiniz. Neden ağ gecikmesi maliyetine katlanasınız?
    Buna karşılık önerilen yapı, yeterince büyük bir ağaçta dalları taşımak ve derinliği değiştirmek gerektiğinde iyi davranmaz. Çünkü doğrusal maliyeti vardır
    Niyeti en baştan söylemeliydi. Üç örneği açıklayıp sonuçta “ağaca ihtiyacınız varsa ağaç kullanın” diyerek bunları boşa düşürmemeliydi. Ama bunu yazının başına koysaydı çok daha az clickbait olurdu

  • Birkaç yıl önce OpenGL hakkında benzer bir aydınlanma yaşamıştım. Hiyerarşik 3D nesnelerden oluşan bir dünyayı çizmem gerekmiyordu; sıralı üçgen listesi çizmem yeterliydi
    Bu düşünce kafamdaki düğmeyi açtı ve birçok optimizasyon çok kolaylaştı

    • Evet. 2000 sonrası 3D oyunlarda sadelik büyük güç hâline geldi
      Karmaşık entity hiyerarşileri olan oyunlarda bile render kuyruğuna koyarken, saydamlık sıralaması gibi nedenlerle çoğu zaman düz bir yapıya katlamak gerekir
      “Nesnelerin düz listesi” aynı zamanda ECS/DOD’nin temelidir

  • Veritabanlarında bu tür işleri ele alan koca bir kitap var
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • Bütün kitaplar başlangıç seviyesine yönelik derlerdi; güzelmiş

  • Sahte ağaç yapmanın başka bir yolu da JSON blob saklamaktır
    Veri yalnızca iç ilişkilere sahipse, sıralama numarasını benzersiz ve sıralı tutmaya çalışmaktan daha kolay olabilir

    • İç içe JSON ile ifade edilen bir ağaç, veritabanında ebeveyn referansı saklayarak elde edilen sanal ağaçtan aksine daha “gerçek” bir ağaç olarak da görülebilir