B-Tree di Factorio

 (razberry.substack.com)
4 poin oleh GN⁺ 2023-11-17 | 1 komentar | Bagikan ke WhatsApp
  • Setelah membaca bab B-Tree di klub buku Database Internals, penulis memverifikasi konsep struktur data secara visual dengan mengimplementasikannya bukan dalam kode, melainkan sebagai bangunan pabrik di Factorio
  • BST hanya dapat bercabang ke kiri dan kanan ketika kunci dapat diurutkan, dan jika nilai menumpuk di satu sisi, efisiensi pencarian bisa turun hingga setara daftar linear
  • Dalam penyimpanan berbasis disk, biaya penyeimbangan ulang BST dan kebutuhan membaca banyak halaman menjadi beban, sementara B-Tree mengurangi masalah ini dengan menyimpan banyak kunci dalam satu node
  • Implementasi di Factorio menggunakan peti kayu dan lengan filter ungu untuk merepresentasikan node dan operasi perbandingan, serta menetapkan urutan penyortiran item secara arbitrer untuk membentuk jalur pencarian
  • Versi B-Tree menggunakan 3 kunci dan 4 pointer per node, sehingga pada 2 tingkat dapat menampung jauh lebih banyak kunci daripada BST, meski masalah representasi nilai dan penyortiran manual masih tersisa

Perbedaan BST dan B-Tree

  • Pohon pencarian biner (BST) menyimpan satu kunci di setiap node, lalu mengirim kunci yang lebih kecil ke node kiri dan kunci yang lebih besar ke node kanan
    • Contohnya dimulai dari kunci akar 8, kiri 3, dan kanan 10
    • Hanya bekerja untuk nilai yang dapat diurutkan yang memungkinkan perbandingan besar-kecil
  • Jika banyak nilai ditambahkan hanya ke satu sisi, keseimbangan BST akan rusak
    • Dalam kasus terburuk, bentuknya hampir sama dengan daftar terurut linear seperti 8 -> 10 -> 14
    • Ketidakseimbangan dapat diperbaiki dengan menempatkan 10 sebagai akar pivot, lalu 8 dan 14 di kedua sisinya
  • Dalam penyimpanan berbasis disk, BST kurang menguntungkan
    • Menjaga penyeimbangan ulang berarti disk dan pointer harus sering diperbarui
    • Node yang bertetangga bisa tersimpan di halaman yang berbeda, sehingga satu pencarian pun dapat memerlukan pembacaan beberapa halaman
  • B-Tree menyimpan beberapa kunci dalam satu node, dan menunjuk node anak dengan jumlah kunci + 1 pointer
    • Node contoh [17 | 24] bercabang ke tiga node anak: berisi kunci yang lebih kecil dari 17, kunci di antara 17 dan 24, serta kunci yang lebih besar dari 24

Pohon pencarian yang diimplementasikan di dalam Factorio

  • Factorio adalah game pembangunan pabrik, dan dalam implementasi ini setiap node pohon direpresentasikan sebagai struktur di dalam game
  • Penulis terlebih dahulu membuat BST sederhana
    • Setiap node memiliki peti kayu yang menyimpan satu kunci dan dua jalur menuju node lain
    • Karena tidak ada metode perbandingan bawaan antar material, digunakan standar urutan arbitrer wood, coal, stone, brick, copper, iron, steel
    • Lengan filter ungu menangani pemeriksaan perbandingan
      • Pada node pertama, satu lengan memeriksa apakah item sama dengan brick
      • Lengan kedua memeriksa apakah nilainya lebih kecil dari brick, seperti wood, coal, stone
      • Lengan ketiga menyaring nilai yang lebih besar, seperti copper, iron, steel
    • Di kanan atas juga ada garbage collector untuk membersihkan item yang salah masuk ke ban berjalan
  • Implementasi B-Tree membutuhkan lebih banyak struktur dalam satu node
    • Setiap node memiliki 3 kunci, 3 lengan filter, 3 peti kayu, dan 4 pointer anak
    • Pada kedalaman yang sama, ia dapat memuat lebih banyak informasi
    • Pada 2 tingkat, BST hanya memuat 2 kunci, sedangkan B-Tree memuat 12 kunci
    • Pada 3 tingkat, B-Tree bertambah hingga 48 kunci
  • Karena penulis tidak ingin memilih dan mengurutkan 48 item secara manual di Factorio, bagian B-Tree dibiarkan kosong sampai ditemukan cara yang lebih baik untuk merepresentasikan nilai
  • BST dan B-Tree dibandingkan berdampingan, dan video YouTube juga disertakan

Bacaan terkait

1 komentar

 
GN⁺ 2023-11-17
Opini Hacker News

  • Desainnya tidak efisien, tetapi mengimplementasikan teori ilmu komputer di Factorio pada dasarnya juga berarti bermain dengan cara yang tidak optimal
    Factorio bukan game yang dibuat untuk memamerkan B-Tree; alat-alatnya pun pada akhirnya dirancang agar Anda tetap bermain Factorio

    1. Inti dari pohon penyeimbang diri seperti 2-3 tree, red-black tree, dan B-Tree bukanlah struktur pohon tunggal itu sendiri, melainkan bagian yang menyeimbangkan diri. Di Factorio, pohon tidak bisa dibuat untuk merekonstruksi dirinya sendiri, jadi fitur terbesarnya hilang
    2. Dari sudut pandang optimisasi, inserter lebih lambat daripada belt. Bahkan jika memakai 4 inserter per belt, hanya sekitar 12 item per detik yang bisa dipindahkan, sementara blue belt dapat mendorong 45 item per detik. Jika desain optimal hanya memakai belt, seharusnya menggunakan splitter yang bekerja pada 45 item per detik
    3. Jadi titik temu antara splitter dan ilmu komputer di Factorio adalah splitter Factorio dan jaringan Benes. Jika ingin mempelajari jaringan yang hanya dibuat dari crossbar 2-input 2-output, mulai dari https://en.wikipedia.org/wiki/Clos_network. Jaringan Benes hanyalah jaringan Clos berukuran 2-input 2-output, dan jaringan Clos juga bisa memiliki ukuran arbitrer seperti 5-ke-7
      Meta yang bisa dicari di Factorio tampaknya adalah desain “mixed belt”
    • Bentuk yang lebih spesifik adalah sushi belt, yaitu satu belt yang memuat berbagai material secara seimbang dan berputar mengelilingi dirinya sendiri
      Sebagian desain hanya menerima item baru dengan rasio yang sudah ditentukan, sementara sebagian desain lain benar-benar menyeimbangkan ulang ketika komposisinya kacau. Secara pribadi, ini yang paling saya suka: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      Contoh ini memakai logika sirkuit dalam game, tetapi forum Factorio juga punya bagian tanpa sirkuit: https://forums.factorio.com/viewforum.php?f=202
      Menariknya, objek “fish” di Factorio adalah item lelucon yang tidak berguna, dan karena tidak dipakai di mana pun, kadang digunakan sebagai nilai null, flag bahwa belt telah menyelesaikan satu putaran, atau alat debugging: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • Saya bertanya-tanya bagaimana kalau ada ekstensi Factorio seperti “Scriptorio” yang memungkinkan JSON diletakkan di atas conveyor belt. Semacam pabrik fungsi JavaScript atau Lua juga dipakai bersama
      Dengan begitu, bukan hanya objek yang akan disisipkan dan dicari, tetapi B-Tree itu sendiri juga bisa dipindahkan dengan conveyor belt dan inserter
      Anda juga bisa menulis fungsi pencarian rekursif sebagai loop conveyor belt yang melewati pabrik: mengupas tree satu level demi satu level hingga mencapai leaf, lalu memutus loop dan mengeluarkan hasilnya
      Ini model eksekusi yang menarik, lebih dekat ke aliran data daripada JavaScript standar. Haruskah kita mengizinkan “quantum tunneling” atau “aksi jarak jauh” dengan membuat conveyor belt, inserter, dan pabrik yang berbeda menunjuk ke objek JSON dasar yang sama melalui beberapa referensi? Itu bisa berguna, tetapi Factorio secara tradisional memperlakukan setiap item fisik sebagai memiliki identitas unik, jadi tidak mendukung banyak referensi mungkin lebih “realistis”. Atau bisa juga, setelah meneliti teknologi “Quantum Tunneling JSON”, beberapa referensi hanya bisa dibuat di “JSON Reference Entangler Factory”
    • Setelah melihat sekilas artikel tentang jaringan Clos, kalau jaringan seperti itu bisa dibuat di Factorio, tampaknya desain jaringan saraf sederhana seperti yang terlihat di sini juga memungkinkan: [1]
      Sepertinya juga mungkin mengubah output dengan memberi bobot pada kepadatan resource yang tiba di lokasi tertentu. Melihat mekanisme yang ditunjukkan di sini [2], penggabungan, pemisahan, dan tiga kecepatan belt tampaknya bisa dipakai untuk membuat pengambilan keputusan berbobot kepadatan
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • Berikutnya saya ingin melihat apakah penyeimbangan diri juga bisa diimplementasikan. Saya sempat berpikir bot akan berguna di sini, tetapi saya tidak yakin apakah bot bisa dibuat membangun blueprint secara dinamis
    • Karena itulah saya tidak bermain Factorio. Sumber daya otak sebesar itu bisa dipakai untuk kepentingan umat manusia, dan jika hasilnya ditunjukkan, bisa juga mendapat respons di media sosial
      Game yang menuntut otak sebagai imbalan untuk angka-angka di layar berada di urutan paling bawah dalam daftar saya. Saya ingin belajar sesuatu yang baru
      Mungkin ada unsur teka-teki dan kita bisa memutuskan bahwa itu menyenangkan, tetapi bukankah kita juga bisa memutuskan bahwa belajar itu menyenangkan?

  • Karya yang keren
    Katanya ia sedang membaca “Database Internals” di klub buku, dan minggu ini adalah bab 2 yang membahas B-Tree
    Sebagai referensi, pendaftarannya sudah ditutup, tetapi jika mau, Anda bisa mendapatkan Database Internals dan mengikutinya secara “read-only” sesuai jadwal dan catatan di sini: https://eatonphil.com/2023-database-internals.html

  • Alasan bahwa “pohon pencarian biner tidak cocok untuk penyimpanan berbasis disk” juga berlaku untuk penyimpanan memori
    Mencari satu node B-Tree lebih cepat daripada mengikuti jumlah pointer yang sama di pohon biner. Tentu kompleksitas implementasinya naik, tetapi kalau tidak memakai C, biasanya kita tidak akan mengimplementasikan sendiri map berbasis pohon
    Variasi seperti memasukkan lebih banyak entri di node internal dan menyimpan nilai hanya di leaf juga memungkinkan. Selama yang dibuat bukan hanya set, bukan map. Jika ditambah tautan ke node tetangga, pada dasarnya ini menjadi mirip skip list

  • Entah kenapa justru konten Factorio seperti ini muncul di sini dan membuat saya ingin terseret lagi sekitar 100 jam. Tahun ini saja sudah terlalu banyak game bagus yang layak dimainkan

    • Menjelang akhir tahun depan dijadwalkan ada penyeimbangan ulang besar-besaran dan ekspansi Space Age, jadi mungkin tidak ada salahnya menunggu sampai saat itu

  • Semua ini juga bisa dilakukan dengan splitter, dan sepertinya tidak perlu peti atau filter inserter. Penjelasannya bagus

    • Saya tidak tahu caranya
      Ini bukan sekadar membagi output ke beberapa jalur. Peti di sini mewakili item yang disimpan pada “node” B-Tree yang disusun secara dua dimensi ini
      Saya belum sempat menonton videonya, tetapi dari tulisan dan screenshot, ada logika yang terkait dengan inserter sehingga item dikirim ke jalur node anak yang tepat untuk mempertahankan sifat “terurut” dari pohon
      Melihat pilihan nilai kunci di artikel aslinya, membaginya dengan splitter memang mungkin, tetapi seingat saya splitter hanya bisa menerima satu filter, jadi di setiap titik percabangan dibutuhkan beberapa splitter. Artinya jumlahnya sebanyak item di titik percabangan itu. Filter inserter mengizinkan beberapa filter, jadi di sini agak lebih baik, dan itu juga terlihat di screenshot pertama
      Tentu saja bisa saja meninggalkan seluruh desain B-Tree dan mengurutkan ke n peti dengan n splitter, tetapi itu tidak seru dan tampaknya bukan maksud artikel aslinya
    • Setiap inserter diberi beberapa item
      Filter splitter hanya mengirim satu jenis item ke satu sisi dan sisanya ke sisi lain. Namun contoh ini berbeda karena beberapa jenis masuk ke satu sisi, dan beberapa jenis lain masuk ke sisi lainnya
    • Perlu mengurutkan dan memfilter beberapa item. Misalnya di node pertama, kayu, batu bara, dan batu harus dikirim ke kiri, sementara logam ke kanan, tetapi filter splitter hanya bisa memfilter satu item

  • Saya penasaran apakah Factorio memang sebagus itu. Semua orang bilang bagus, tetapi tema membangun pabrik tampak agak membosankan dan saya khawatir gamenya terlalu repetitif

    • Sebelum mencobanya, saya juga cukup skeptis dan punya kekhawatiran yang sama. Tapi tanpa sadar saya sudah menaruh lebih dari 100 jam di dalamnya
    • Semua pemain Factorio yang saya kenal menghabiskan lebih dari 1.000 jam

  • Benar-benar keren, tetapi sebagai sesama orang yang ingin menulis, tidak memakai huruf kapital di awal kalimat terasa cukup mengganggu

  • Saya kira ini akan diimplementasikan dengan sistem circuit Factorio