Pohon palsu: menggunakan indentasi untuk UI yang lebih sederhana

 (ratfactor.com)
4 poin oleh GN⁺ 2024-01-01 | 1 komentar | Bagikan ke WhatsApp
  • Meski UI hierarkis tampak diperlukan, hal pertama yang perlu diperiksa adalah apakah datanya benar-benar harus memiliki relasi induk-anak, atau cukup terlihat seperti itu saja
  • Jika tidak membutuhkan tree sungguhan, struktur yang terlihat di layar dapat direpresentasikan hanya dengan urutan sortir absolut dari seluruh daftar dan nilai indent, bukan ID induk
  • Editor game Hiss mengurutkan nama seperti banana.eat, lalu menampilkan bagian setelah titik (.) dengan indentasi, sehingga membuat UI yang tampak seperti namespace
  • Pendekatan ini lebih mirip pengeditan ala pengolah kata, di mana pengguna memindahkan item ke atas/bawah serta mengindentasi/mengurangi indentasi, sehingga mengurangi beban struktur data tree
  • Jika relasi antaritem memang harus dicari atau dipertahankan secara nyata, diperlukan model tree sungguhan, bukan indentasi atau trik simbol dalam string

Daftar yang terlihat seperti tree, bukan tree

  • Saat mencoba menampilkan daftar dinamis seperti Foo dan Bar sebagai tree view dalam aplikasi, biasanya yang terbayang adalah struktur yang menghubungkan setiap item ke item induknya
  • Dalam basis data relasional, misalnya, ID induk dapat disimpan dalam kolom parent
    • parent milik Foo adalah null
    • parent milik Foo 1 adalah Foo
    • parent milik Foo 1.a adalah Foo 1
  • Untuk mengambil data tree seperti ini dengan SQL, mungkin diperlukan pendekatan seperti recursive CTE
  • Namun pada banyak daftar, tampilan yang tertata agar mudah dilihat manusia bisa lebih penting daripada relasi yang sebenarnya

Cara menyimpan nilai indentasi sebagai data

  • Jika relasi induk-anak sungguhan tidak diperlukan, daftar dapat disimpan hanya dengan field berikut
    • id
    • sort
    • indent
    • name
  • sort merepresentasikan urutan absolut seluruh daftar, bukan urutan internal di dalam subitem
  • indent secara langsung merepresentasikan jumlah ruang yang ditempatkan di depan item, sehingga rendering layar menjadi sederhana
  • UI pengeditan juga bisa menjadi lebih sederhana dibanding manipulasi tree
    • Pengguna dapat memindahkan item ke atas dan ke bawah
    • Pengguna dapat mengindentasi atau mengurangi indentasi item
    • Jika perlu, aturan sederhana untuk memaksakan indentasi yang benar dapat ditambahkan
  • Hasilnya, pengalaman ini lebih mirip mengedit daftar di pengolah kata daripada memanipulasi langsung struktur data ala buku teks ilmu komputer

Namespace palsu berbasis titik (.) di Hiss

  • Editor game petualangan teks Hiss menampilkan nama seperti banana, banana.eat, dan banana.peel di UI seolah-olah berbentuk hierarki
  • Ini bukan implementasi fitur namespace sungguhan di HissScript
  • Cara implementasinya sederhana
    • Mengurutkan nama objek secara alfabetis
    • Jika ada titik (.) dalam nama, bagian depannya dipotong
    • Bagian yang tersisa ditampilkan dengan indentasi
  • Logika inti dalam kode contoh juga mengikuti alur yang sama
    • Mengurutkan things.keys
    • Untuk setiap nama yang memiliki titik, menambahkan indentasi lalu menghapus bagian sebelum titik sebelum ditampilkan
    • Jika tidak ada titik, menampilkan nama apa adanya
  • Setelah itu, beberapa baris pemeriksaan ditambahkan untuk memastikan apakah item “induk” dengan prefiks yang diberikan memang ada
  • Nesting dengan kedalaman arbitrer juga dapat ditambahkan, tetapi saat ini menunggu sampai benar-benar diperlukan
  • UI yang tampak seperti namespace ini penting bagi orang yang merapikan game, tetapi tidak memiliki makna khusus bagi editor game maupun pemain
    • Nama yang mengandung titik tetap hanyalah nama
    • Bagian yang tampak seperti namespace hanya berperan menjaga nama tetap unik

Contoh mirip tree yang ditangani sebagai daftar datar

  • Dave Long mengusulkan cara menyimpan path dan informasi dalam daftar datar sebagai “tree nyata berteknologi rendah”
  • Ini merupakan insight yang mirip dengan contoh banana.eat
  • Kita bisa membayangkan daftar path seperti output find berikut
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • Jika perlu traversal depth-first, cukup urutkan path secara leksikografis
  • Jika perlu traversal breadth-first, path dapat dibalik berdasarkan pemisah path, item kosong ditambahkan untuk menyamakan kedalaman, lalu diurutkan
  • Contoh ini bertujuan menunjukkan konsep; dalam praktiknya, pendekatan yang lebih alami adalah memecah baris berdasarkan pemisah lalu memprosesnya sebagai array
  • Secara umum daftar datar mudah ditangani, dan bila memungkinkan pendekatan yang disukai adalah memasukkan item ke dalam plain old lists

Analogi scrapbook di lantai

  • Dalam pekerjaan scrapbook pribadi, foto, catatan, kartu pos, tiket, dan sebagainya dapat disebar di lantai lalu dikelompokkan
  • Bagi manusia, relasi kelompoknya tampak jelas, tetapi lantai itu sendiri tidak memiliki perangkat fisik yang memaksakan relasi tersebut
  • Inti analogi ini adalah bahwa relasi yang direpresentasikan dan relasi struktural yang sebenarnya bisa berbeda
  • Daftar UI juga demikian: penataan yang bagi manusia tampak seperti hierarki belum tentu berarti hierarki nyata dalam model data internal

Kapan tree sungguhan diperlukan

  • Pendekatan berbasis indentasi atau simbol dalam string harus banyak disesuaikan dengan konteks, dan dalam konteks pemrograman umum kemungkinan akan dianggap sebagai hack
  • Jika relasi antaritem benar-benar perlu diketahui, gunakan struktur tree sungguhan yang sesuai dengan model data, seperti ID induk atau tabel join induk-anak
  • Jika membutuhkan tingkat organisasi setara lemari arsip fisik dan folder, seperti saat mengklasifikasikan proyek riset berskala besar, “cara lantai” tidak cocok
  • Jika sebuah proyek nantinya benar-benar perlu mengetahui relasi antaritem, meniru struktur dengan indentasi atau jumlah simbol di dalam string dapat menjadi jalan yang menyakitkan sepanjang usia proyek dan masa pemeliharaannya

Bacaan terkait

1 komentar

 
GN⁺ 2024-01-01
Komentar di Hacker News

  • Cara pertama, yaitu cara yang terlihat seperti “tentu saja cuma cara ini”, disebut adjacency list
    Cara kedua yang “jauh lebih sederhana” rasanya belum pernah saya lihat sebelumnya, dan memang punya kekurangan yang jelas, tetapi dalam beberapa kasus tampaknya sudah cukup
    Cara ketiga, “namespacing”, disebut materialized path, dan ada juga nested sets sebagai cara lain untuk merepresentasikan tree: https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    Dulu, ketika orang masih menangani basis data relasional secara serius, semua ini adalah hal yang sudah dikenal luas; misalnya ada tulisan seperti http://www.dbazine.com/oracle/or-articles/tropashko4/
    Sekarang rasanya seperti pengetahuan yang terlupakan

    • Salah satu momen yang paling saya benci di tempat kerja dulu adalah ketika saya sudah berusaha keras menjelaskan suatu masalah, lalu ada orang yang mengenalinya sebagai konsep yang sudah ada—sudah punya nama dan sudah diteliti
      Saat sedang mencoba memahami berbagai sisi masalahnya sendiri, rasanya sangat sulit menemukan nama lama untuk konsep itu
    • Benar. Lulusan muda yang direkrut belakangan ini cenderung memaksakan semuanya ke dalam dokumen NoSQL dan hampir tidak mau memikirkan pemodelan data
      Akhirnya semua logika untuk menampilkan tree ditangani di kode, padahal dengan basis data relasional modern dan beberapa CTE saja, banyak use case bisa ditangani secara elegan dan nyaris gratis; sayang sekali
    • Sulit menyebutnya pengetahuan yang terlupakan. Ada juga buku berjudul “Joe Celko's Trees and Hierarchies in SQL”
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • Kalau tertarik dengan topik ini, saya sarankan mulai dengan mencari buku-buku dari https://en.m.wikipedia.org/wiki/Joe_Celko

  • Postgres punya tipe data ltree dan operator pencarian yang bekerja secara native seperti ini: https://www.postgresql.org/docs/current/ltree.html
    Misalnya, masukkan seperti CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy');
    lalu dengan SELECT path FROM test WHERE path <@ 'Top.Science'; Anda bisa menemukan Top.Science dan Top.Science.Astronomy

    • Catatan untuk programmer: salah satu keunikan ltree adalah jalur perantara yang akan menjadi node induk jika digambar sebagai tree tidak harus benar-benar ada
      Pada contoh di atas, sekalipun record Top.Science dihapus, record Top.Science.Astronomy tidak ikut terpotong
      Label pada nilai ltree mengisyaratkan tree logis melalui materialized path, tetapi tidak memaksa keberadaan record untuk semua node induk yang tersirat
      Tergantung aplikasinya, ini bisa persis perilaku yang diinginkan, atau justru kebalikannya. Jika yang terakhir, Anda perlu menyediakan mekanisme terpisah untuk menjaga integritas
    • Saya penasaran apakah bisa memakai / sebagai delimiter untuk menyimpan path file
    • Saya penasaran apakah ada yang punya pengalaman performanya. Sepertinya banyak pemrosesan regex
    • SQL Server juga punya fitur yang sangat mirip[1], dan dari pengalaman saya, fiturnya bekerja cukup baik
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • Saya penasaran apakah hal yang sama bisa dilakukan dengan kolom JSON. Dengan begitu, node bisa memakai tipe data selain string
      Namun ada kekhawatiran bahwa indeks JSON mungkin tidak bekerja sebaik indeks ltree

  • Masalahnya di sini adalah nilai dalam struktur biasanya bukan pada tree untuk tampilan, melainkan pada hierarki data
    Kemungkinan besar Anda akan melakukan hal-hal seperti menelusuri data, menampilkan relasi, atau mengurutkan ulang
    Menaruh informasi visual dalam struktur data basis data terasa berbahaya dan berpandangan pendek

    • Penulis sudah secara eksplisit mengatakan, “orang selalu berpikir bahwa relasi induk-anak harus dienkode secara formal, tetapi dalam praktiknya tidak selalu begitu, dan kadang yang dibutuhkan hanya tampilan bertingkat,” jadi agak aneh jika ini dijadikan tanggapan
      Apakah jawabannya, “Tidak, itu tidak mungkin”?
      Ada alasan mengapa YAGNI menjadi heuristik desain yang terkenal. “Anggap selalu akan dibutuhkan” itu tidak tepat
    • Ironisnya, tetap saja menggunakan ID induk di dalam data
      Hanya saja bukan disimpan di kolom khusus dengan tipe data yang dioptimalkan, melainkan ditempelkan di depan string data
      Mungkin bukan angka dan mungkin bukan kolom ID, tetapi tetap merupakan identifier yang menunjuk ke nilai lain yang diharapkan, jadi perubahan format tidak membuatnya bukan ID induk
    • Dalam metode encoding urutan/indentasi pada artikel asli pun, relasi induk-anak seharusnya mudah direkonstruksi
      Tentu saja harus dijamin agar indentasi keliru seperti anak tanpa induk tidak tersimpan
      Jadi menurut saya cara termudah adalah menyimpannya terlebih dahulu sebagai urutan/kedalaman, lalu saat fitur yang diperlukan diimplementasikan, migrasikan ke model induk/anak
      Namun, “indentasi” sebaiknya didefinisikan lebih abstrak sebagai kedalaman dalam tree, bukan jumlah spasi yang dirender. Ini memudahkan menemukan data yang salah, memudahkan migrasi berikutnya, dan memberi fleksibilitas rendering per pengguna seperti / bertingkat, tab, 8 spasi, 4 spasi, atau 1 spasi
    • Jika ada struktur data seperti struct item_t { char key[255]; char display_value[255]; }, dan key memiliki pemisah path yang konsisten seperti a/b/c, menemukan induk dan anak sangat mudah
      Dalam kasus terburuk cukup lakukan pencarian linear pada array, dan jika sudah terurut, cukup lihat item sebelumnya sampai mencapai induk
    • Sangat setuju. Denormalisasi kadang bisa menjadi pilihan yang baik, tetapi saya tidak melihat kasus ini sebagai pembenaran yang masuk akal

  • Saya pernah memulai perusahaan yang punya banyak data berbentuk tree. Mengubah struktur tree menjadi daftar berindentasi bisa dilakukan dalam waktu O(n)
    Itu salah satu pertanyaan wawancara saat itu, dan ada berbagai cara menyimpannya di beberapa basis data SQL agar sebagian tree bisa diambil dan dirender dengan cepat tanpa query rekursif
    Setelah memahami konsep seperti ini, menyimpan data dengan benar sebagai tree punya jauh lebih banyak keunggulan dibanding indentasi semacam ini

    • Kalau keunggulan itu tidak dibutuhkan, ya tidak terlalu penting

  • “Salah satu cara mengambil data berstruktur tree dari basis data relasional dengan query SQL adalah memakai recursive CTE (Common Table Expressions), yang sama menyenangkannya dengan namanya”
    CTE, bahkan termasuk recursive CTE, bukan sesuatu yang menakutkan, dan saya jamin setelah terbiasa justru benar-benar menyenangkan

    • CTE tidak terlalu menyenangkan. Menyalin dan menempel seluruh menara CTE ke jendela SQL lain untuk men-debug bagian yang saya minati bukan hiburan yang saya cari
    • Saat merakit data tree dari representasi yang ternormalisasi, recursive CTE sangat lambat
      Untuk merakit path node dengan kedalaman hierarki d, waktu untuk mendapatkan hasil query setidaknya menjadi d kali lebih lambat
      Keuntungannya adalah operasi pengeditan tree menjadi murah, tetapi itu jauh lebih jarang terjadi dibanding pembacaan
    • CTE baik-baik saja. Alih-alih memasukkan informasi ini langsung ke tabel, penulis juga bisa membuat view dengan nama yang sudah diformat menggunakan CTE

  • Dari gagasan bahwa “orang sering kali sebenarnya tidak menginginkan atau membutuhkan tree, mereka hanya membutuhkan sesuatu yang terlihat seperti tree,” terlihat perbedaan antara HN dan Reddit
    Di HN, komentar anak adalah nextSibling dari komentar induk, dan dibuat tampak seperti tree dengan menambahkan 1 ke nilai indentasi induknya
    Di Reddit, setidaknya di old.reddit.com, komentar anak benar-benar disarangkan di dalam komentar induk. Saya tidak tahu soal situs yang baru

    • Maksudnya struktur HTML, bukan tampilan aktual, kan? Yang terlihat di layar hampir sama
    • Sulit membayangkan backend benar-benar menyimpannya seperti ini
      Semua operasi atas data akan menjadi kekacauan rumit yang harus menyimpulkan struktur tree lalu menerjemahkannya kembali ke format tree implisit
    • Kalau begitu, saya penasaran bagaimana collapse bekerja

  • Ide utama tulisan itu sederhana: gunakan struktur yang sesuai dengan masalah
    Namun menurut saya narasinya keliru. Untuk mengambil tree dari basis data, CTE tidak selalu diperlukan; kita bisa mengambil daftar datar lalu membangun tree secara lokal. Untuk manipulasi berikutnya pun kemungkinan besar memang harus begitu
    Dengan logika yang sama, orang yang memakai basis data relasional untuk menyimpan daftar juga bisa disuruh menyimpannya di file teks. Untuk apa membayar biaya latensi jaringan?
    Sebaliknya, struktur yang diusulkan tidak bekerja baik jika harus memindahkan cabang dan mengubah kedalaman pada tree yang cukup besar, karena biayanya linear
    Seharusnya niatnya dinyatakan sejak awal. Jangan menjelaskan tiga contoh lalu membatalkannya di kesimpulan dengan “kalau butuh tree, pakailah tree.” Namun kalau itu ditaruh di depan, tulisannya pasti jauh kurang clickbait

  • Beberapa tahun lalu saya mendapat pencerahan serupa tentang OpenGL. Yang perlu digambar bukanlah dunia objek 3D hierarkis, melainkan daftar segitiga terurut
    Pemikiran itu menyalakan semacam sakelar di kepala saya, dan berbagai optimisasi menjadi sangat mudah

    • Benar. Dalam game 3D setelah tahun 2000, kesederhanaan menjadi kekuatan besar
      Bahkan pada game dengan hierarki entitas yang kompleks, saat dimasukkan ke render queue, sering kali harus diratakan karena alasan seperti pengurutan transparansi
      “Daftar datar benda-benda” juga merupakan dasar ECS/DOD

  • Ada satu buku utuh yang membahas pekerjaan semacam ini di basis data
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • Katanya semua buku itu untuk pemula, baguslah

  • Cara lain membuat tree palsu adalah menyimpan blob JSON
    Jika data hanya memiliki relasi internal, ini bisa lebih mudah daripada berusaha menjaga nomor urut tetap unik dan berurutan

    • Tree yang direpresentasikan sebagai JSON bersarang justru bisa dibilang lebih “nyata” sebagai tree dibanding tree virtual yang diperoleh dengan menyimpan referensi induk di basis data