Factorio’da B-Tree

 (razberry.substack.com)
4 puan yazan GN⁺ 2023-11-17 | 1 yorum | WhatsApp'ta paylaş
  • Database Internals kitap kulübünün B-Tree bölümünü okuduktan sonra, veri yapısını kodla değil Factorio fabrika yapılarıyla uygulayarak kavramı görsel olarak doğruluyor
  • BST, yalnızca anahtarlar sıralanabilir olduğunda sol·sağ dallanmaya izin verir; değerler bir tarafa yığılırsa arama verimliliği doğrusal liste seviyesine düşebilir
  • Disk tabanlı depolamada BST’nin yeniden dengeleme maliyeti ve birden çok sayfa okuma yük oluşturur; B-Tree ise tek bir düğümde birden çok anahtar tutarak bu sorunu azaltan bir yapıdır
  • Factorio uygulaması, düğümleri ve karşılaştırma işlemlerini ahşap sandıklar ve mor filtre kolluyla temsil eder; rastgele bir öğe sıralama düzeni belirleyerek arama yolu oluşturur
  • B-Tree sürümü, düğüm başına 3 anahtar ve 4 işaretçi kullanarak 2 seviyede BST’ye göre çok daha fazla anahtar barındırır; ancak değer gösterimi ve elle sıralama sorunları devam eder

BST ile B-Tree arasındaki fark

  • İkili arama ağacı (BST) her düğümde tek bir anahtar tutar; daha düşük anahtarları sol düğüme, daha yüksek anahtarları sağ düğüme gönderir
    • Örnek, kök anahtar 8, sol 3, sağ 10 ile başlar
    • Yalnızca anahtar değerlerinin büyüklük-küçüklük açısından karşılaştırılabildiği sıralanabilir değerlerde çalışır
  • Değerler çoğunlukla tek tarafa eklenirse BST’nin dengesi bozulur
    • En kötü durumda 8 -> 10 -> 14 gibi bir doğrusal sıralı listeye neredeyse eşdeğer olur
    • Dengesizlik, pivot olarak 10u köke koyup 8 ve 14ü iki tarafa yerleştirme şeklinde düzeltilebilir
  • Disk tabanlı depolamada BST dezavantajlıdır
    • Dengeyi sürekli korumak, diski ve işaretçileri sık sık güncellemeyi gerektirir
    • Komşu düğümler farklı sayfalarda saklanabildiğinden, tek bir aramada bile birden çok sayfa okunabilir
  • B-Tree, tek bir düğümde birden çok anahtar tutar ve anahtar sayısı + 1 adet işaretçiyle çocuk düğümleri gösterir
    • Örnekteki [17 | 24] düğümü, 17den küçük anahtarlar, 17 ile 24 arasındaki anahtarlar ve 24ten büyük anahtarlar içeren üç çocuk düğüme dallanır

Factorio içinde uygulanan arama ağacı

  • Factorio bir fabrika kurma oyunudur; uygulamada her ağaç düğümü oyun içindeki yapılarla temsil edilir
  • Önce basit bir BST yapılır
    • Her düğüm, tek bir anahtar tutan ahşap sandık ve diğer düğümlere giden iki yola sahiptir
    • Malzemeler arasında varsayılan bir karşılaştırma yöntemi olmadığından wood, coal, stone, brick, copper, iron, steel sırasıyla rastgele bir sıralama ölçütü belirlenir
    • Mor filtre kollu, karşılaştırma kontrolünü üstlenir
      • İlk düğümde bir kol, öğenin brick ile aynı olup olmadığını kontrol eder
      • İkinci kol, wood, coal, stone gibi brickten küçük olup olmadığını denetler
      • Üçüncü kol, copper, iron, steel gibi daha büyük değerleri filtreler
    • Sağ üstte, konveyör bandına yanlışlıkla giren öğeleri temizleyen bir garbage collector da bulunur
  • B-Tree uygulaması, tek bir düğüm için daha fazla yapı gerektirir
    • Her düğümde 3 anahtar, 3 filtre kollu, 3 ahşap sandık ve 4 çocuk işaretçisi bulunur
    • Aynı derinlikte daha fazla bilgi tutabilir
    • 2 seviyede BST 2 anahtar tutarken, B-Tree 12 anahtar tutar
    • 3 seviyede ise B-Tree 48 anahtara kadar çıkar
  • Factorio’da 48 öğeyi elle seçip sıralamak istemediği için, daha iyi bir değer gösterim yöntemi bulunana kadar B-Tree boş bırakılır
  • BST ile B-Tree yan yana karşılaştırılır ve YouTube videosu da eklenir

İlgili okumalar

1 yorum

 
GN⁺ 2023-11-17
Hacker News yorumları

  • Verimsiz bir tasarım ama Factorio’da bilgisayar bilimi teorisini hayata geçirmek, kaçınılmaz olarak oyunu optimal olmayan bir şekilde oynamak anlamına da geliyor.
    Factorio, B-Tree sergilemek için yapılmış bir oyun değil; araçlar da en nihayetinde Factorio oynansın diye tasarlanmış.

    1. 2-3 ağaçları, kırmızı-siyah ağaçlar, B-Tree gibi kendini dengeleyen ağaçların özü tekil ağaç yapısının kendisi değil, kendi kendini dengeleme kısmıdır; Factorio’da ise ağacın kendini yeniden yapılandırmasını sağlayamazsınız, dolayısıyla en büyük özellik eksik kalıyor.
    2. Optimizasyon açısından yerleştiriciler bantlardan daha yavaştır. Bant başına 4 yerleştirici kullansanız bile saniyede yaklaşık 12 öğeden fazlasını taşıyamazsınız; mavi bant ise saniyede 45 öğeyi itebilir. Yalnızca bant kullanan optimal bir tasarımda saniyede 45 öğe ile çalışan ayırıcılar kullanılmalı.
    3. Bu yüzden ayırıcılar ile bilgisayar biliminin kesiştiği nokta Factorio’nun ayırıcıları ve Benes ağıdır. Yalnızca 2 girişli 2 çıkışlı çapraz anahtarlardan oluşan ağları incelemek istiyorsanız https://en.wikipedia.org/wiki/Clos_network ile başlayabilirsiniz. Benes ağı, 2 girişli 2 çıkışlı boyuttaki bir Clos ağından ibarettir; Clos ağları ise 5’e 7 gibi keyfi boyutlarda da olabilir.
      Factorio’da bakılacak metanın “karışık bant” tasarımları olduğu anlaşılıyor.
    • Daha somut bir biçimi, tek bir bandın birden fazla malzemeyi dengeli biçimde taşıyıp kendi etrafında döndüğü suşi bandıdır.
      Bazı tasarımlar yalnızca yeni öğeleri belirli oranlarda kabul ederken, bazıları denge bozulduğunda gerçekten yeniden denge kurar. Şahsen en çok bunu beğeniyorum: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      Bu örnek oyun içi devre mantığını kullanıyor, ancak Factorio forumunda devresiz bir bölüm de var: https://forums.factorio.com/viewforum.php?f=202
      İlginç olan, Factorio’daki “fish” nesnesinin işe yaramayan bir şaka öğesi olması; hiçbir yerde kullanılmadığı için bazen null değer, bandın bir turu tamamladığını gösteren bayrak veya hata ayıklama aracı olarak kullanılıyor: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • Konveyör bantlarının üzerine JSON koymayı sağlayan “Scriptorio” gibi bir Factorio eklentisi olsa nasıl olur diye düşünüyorum. JavaScript veya Lua fonksiyon fabrikalarıyla birlikte kullanmak gibi.
      O zaman yalnızca eklenecek/aranacak nesneleri değil, B-Tree’nin kendisini de konveyör bantları ve yerleştiricilerle hareket ettirebilirsiniz.
      Fabrikadan geçen bir konveyör bant döngüsüyle özyinelemeli arama fonksiyonu yazıp, yaprağa ulaşana kadar ağacı seviye seviye soyarak döndürebilir ve döngüyü kırıp sonucu çıktı olarak verebilirsiniz.
      Standart JavaScript’ten ziyade veri akışına daha yakın, ilginç bir yürütme modeli. Farklı konveyör bantlarının, yerleştiricilerin ve fabrikaların aynı temel JSON nesnesine birden fazla referansla işaret etmesini sağlayıp “kuantum tünelleme” veya “uzaktan etki”ye izin vermeli miyiz? Kullanışlı olabilir; ancak Factorio geleneksel olarak her fiziksel öğenin benzersiz bir kimliğe sahip olduğunu varsayar, bu yüzden çoklu referans desteği vermemek daha “gerçekçi” de olabilir. Ya da “Quantum Tunneling JSON” teknolojisini araştırdıktan sonra çoklu referansların yalnızca “JSON Reference Entangler Factory”de oluşturulmasına izin verilebilir.
    • Clos ağı yazısına şöyle bir göz attım; Factorio’da böyle ağlar yapılabiliyorsa, burada görünenler gibi basit sinir ağı tasarımları da mümkün görünüyor: [1]
      Belirli bir konuma ulaşan kaynak yoğunluğuna ağırlık vererek çıktıyı değiştirmek de mümkün olabilir. Burada görülen mekanizmaya [2] bakınca, birleştirme/ayırma ve üç farklı bant hızıyla yoğunluk ağırlıklı karar verme yapılabilecek gibi duruyor.
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • Sırada kendini dengelemeyi de uygulayıp uygulayamayacaklarını görmek isterim. Botların burada işe yarayabileceğini düşündüm ama botlara planları dinamik olarak inşa ettirmek mümkün mü pek emin değilim.
    • Bu yüzden Factorio oynamıyorum. O kadar zihinsel kaynağı insanlık için kullanmak mümkün; ortaya çıkan sonucu gösterdiğinizde sosyal medyadan da tepki alabilirsiniz.
      Ekrandaki sayılar karşılığında beynimi talep eden oyunlar listemin en dibinde. Ben yeni bir şey öğrenmek istiyorum.
      Bulmaca unsurları olabilir ve biz bunun eğlenceli olduğuna karar verebiliriz; ama çalışmanın da eğlenceli olduğuna karar veremez miyiz diye düşünüyorum.

  • Harika bir çalışma.
    “Database Internals”ı bir kitap kulübünde okuyorum ve bu hafta B-Tree’leri ele alan 2. bölüme gelmiştik.
    Bu arada kayıtlar kapanmış olsa da, isterseniz Database Internals’ı edinip buradaki takvim ve notları takip ederek “salt okunur” şekilde eşlik edebilirsiniz: https://eatonphil.com/2023-database-internals.html

  • “İkili arama ağaçları disk tabanlı depolama için iyi değildir” gerekçeleri bellek içi depolama için de geçerlidir.
    Tek bir B-Tree düğümünde arama yapmak, ikili ağaçta aynı sayıda işaretçiyi takip etmekten daha hızlıdır. Elbette uygulama karmaşıklığı artar; ama C kullanmıyorsanız genelde ağaç tabanlı bir map’i kendiniz yazmazsınız.
    İç düğümlere daha fazla öğe koyup değerleri yalnızca yapraklarda saklamak gibi varyasyonlar da mümkün. Tabii sadece bir küme değil de bir map yapıyorsanız. Buna komşu düğümleri de bağlarsanız, fiilen bir skip list’e oldukça yaklaşır.

  • Neden özellikle burada Factorio içeriği karşıma çıkıp beni yine yaklaşık 100 saat gömülme dürtüsüne sürükledi bilmiyorum. Bu yıl zaten oynanacak çok fazla iyi oyun var.

    • Gelecek yılın sonlarına doğru büyük bir yeniden dengeleme ve Space Age genişleme paketi planlanıyor; o zamana kadar beklemek de fena olmayabilir.

  • Bunun tamamı splitter’larla da yapılabilir; sandıklara ya da filtreli inserter’lara gerek yok gibi. Açıklama iyi.

    • Nasıl yapılacağını bilmiyorum.
      Amaç sadece çıktıyı birden fazla hatta bölmek değil. Sandıklar, burada iki boyutlu olarak yerleştirilmiş B-Tree’nin ilgili “düğümünde” saklanan öğeleri temsil ediyor.
      Videoyu izleyecek vaktim olmadı, ama yazı ve ekran görüntülerine bakınca mantığın inserter’lara bağlandığı ve ağacın “sıralı” özelliğini korumak için öğeleri uygun çocuk düğüm yoluna gönderdiği anlaşılıyor.
      Orijinal yazıdaki anahtar değer seçimine bakınca splitter’larla ayırmak da mümkün olurdu; ama hatırladığım kadarıyla splitter yalnızca tek bir filtre alabiliyor, bu yüzden her dallanma noktasında birden fazlası gerekir. Yani o dallanma noktasındaki öğe sayısı kadar gerekir. Filtreli inserter’lar birden fazla filtreye izin verdiğinden burada biraz daha iyi; ilk ekran görüntüsünde de görülebiliyor.
      Elbette B-Tree tasarımından tamamen vazgeçip n adet splitter ile n adet sandığa sıralama yapabilirsiniz; ama bu eğlenceli değil ve asıl yazının amaçladığı şey de bu değil gibi.
    • Her inserter’a birden fazla öğe atanıyor.
      Splitter filtresi yalnızca tek bir öğeyi bir tarafa gönderir, geri kalanları diğer tarafa yollar. Ama bu örnekte birden fazla tür bir tarafa, birden fazla tür de diğer tarafa gittiği için durum farklı.
    • Birden fazla öğeyi sıralamak/filtrelemek gerekiyor. Örneğin ilk düğümde odun, kömür ve taş sola; metaller sağa gitmeli, ama splitter filtresi yalnızca tek bir öğeyi filtreleyebiliyor.

  • Factorio’nun gerçekten o kadar iyi bir oyun olup olmadığını merak ediyorum. Herkes iyi diyor ama fabrika kurma teması biraz sıkıcı görünüyor ve oyunun fazla tekrara düşmesinden endişeliyim.

    • Denemeden önce ben de oldukça şüpheciydim ve aynı kaygıları taşıyordum. Ama bir baktım, 100 saatten fazla oynamışım.
    • Tanıdığım Factorio oyuncularının hepsi 1.000 saatten fazla gömmüş durumda.

  • Gerçekten harika, ama yazı yazanlar arasında söylenebilecek bir şey olarak, cümle başlarında büyük harf kullanmamak epey dikkat dağıtıcı geliyor.

  • Factorio’nun devre sistemiyle uygulanacağını sanmıştım.