Cây giả: dùng thụt lề để có UI đơn giản hơn

 (ratfactor.com)
4 điểm bởi GN⁺ 2024-01-01 | 1 bình luận | Chia sẻ qua WhatsApp
  • Dù có vẻ cần UI phân cấp, điều cần kiểm tra trước tiên là dữ liệu có thật sự cần quan hệ cha-con hay chỉ cần trông giống như vậy
  • Nếu không cần cây thật, có thể biểu diễn cấu trúc trên màn hình chỉ bằng thứ tự sắp xếp tuyệt đối của toàn bộ danh sách và giá trị indent, thay vì ID cha
  • Trình biên tập game Hiss sắp xếp các tên như banana.eat, rồi hiển thị phần sau dấu chấm (.) với thụt lề để tạo ra UI trông như namespace
  • Cách này gần với kiểu chỉnh sửa như trong trình xử lý văn bản, nơi người dùng di chuyển mục lên xuống và tăng/giảm thụt lề, nên giảm gánh nặng của cấu trúc dữ liệu cây
  • Nếu thực sự cần truy vấn hoặc duy trì quan hệ giữa các mục, thì thay vì dùng thụt lề hay mẹo ký hiệu trong chuỗi, cần một mô hình cây thực thụ

Danh sách không phải cây nhưng trông như cây

  • Khi muốn hiển thị các danh sách động như Foo, Bar trong ứng dụng bằng tree view, ta thường nghĩ ngay đến cấu trúc nối mỗi mục với mục cha của nó
  • Trong cơ sở dữ liệu quan hệ, chẳng hạn có thể lưu ID cha bằng cột parent
    • Foo có parent là null
    • Foo 1 có parent là Foo
    • Foo 1.a có parent là Foo 1
  • Để lấy dữ liệu cây kiểu này bằng SQL, có thể cần cách như recursive CTE
  • Nhưng trong nhiều danh sách, điều quan trọng hơn quan hệ thực tế có thể là hình thức được sắp xếp gọn gàng để con người dễ nhìn

Cách lưu giá trị thụt lề như dữ liệu

  • Nếu không cần quan hệ cha-con thực sự, có thể lưu danh sách chỉ với các trường sau
    • id
    • sort
    • indent
    • name
  • sort không phải thứ tự bên trong từng mục con, mà là thứ tự tuyệt đối của toàn bộ danh sách
  • indent biểu thị trực tiếp lượng khoảng trắng đặt trước mục, nên việc render giao diện trở nên đơn giản
  • UI chỉnh sửa cũng có thể đơn giản hơn thao tác trên cây
    • Người dùng có thể di chuyển mục lên hoặc xuống
    • Có thể tăng hoặc giảm thụt lề cho mục
    • Nếu cần, có thể thêm các quy tắc đơn giản để ép thụt lề hợp lệ
  • Kết quả là, thay vì thao tác trực tiếp trên cấu trúc dữ liệu kiểu giáo trình khoa học máy tính, trải nghiệm này gần hơn với chỉnh sửa danh sách trong trình xử lý văn bản

Namespace giả dựa trên dấu chấm (.) của Hiss

  • Trình biên tập game phiêu lưu văn bản Hiss hiển thị các tên như banana, banana.eat, banana.peel theo kiểu phân cấp trong UI
  • Điều này không có nghĩa là HissScript đã triển khai tính năng namespace thực sự
  • Cách triển khai rất đơn giản
    • Sắp xếp tên đối tượng theo thứ tự chữ cái
    • Nếu tên có dấu chấm (.), cắt bỏ phần phía trước
    • In ra phần còn lại với thụt lề
  • Logic cốt lõi trong đoạn mã ví dụ cũng đi theo đúng luồng đó
    • Sắp xếp things.keys
    • Nếu mỗi tên có dấu chấm thì thụt lề rồi bỏ phần trước dấu chấm khi in ra
    • Nếu không có dấu chấm thì in nguyên tên
  • Sau đó có thêm vài dòng kiểm tra xem có tồn tại mục “cha” với tiền tố tương ứng hay không
  • Cũng có thể bổ sung lồng nhau với độ sâu tùy ý, nhưng hiện tại vẫn đang chờ đến khi thực sự cần
  • UI trông như namespace này quan trọng với người tổ chức game, nhưng không mang ý nghĩa đặc biệt với trình biên tập game hay người chơi
    • Tên có dấu chấm cũng chỉ là tên bình thường
    • Phần trông như namespace chỉ có vai trò giúp giữ cho tên là duy nhất

Những trường hợp giống cây nhưng được xử lý như danh sách phẳng

  • Dave Long đề xuất một cách “cây thật công nghệ thấp”, trong đó đường dẫn và thông tin được lưu trong danh sách phẳng
  • Đây là một nhận định tương tự ví dụ banana.eat
  • Có thể hình dung danh sách đường dẫn theo dạng như đầu ra của find
    • ./foo/zonk
    • ./foo/bonk
    • ./bar/boop/bop
    • ./bar/boop/bleep
  • Nếu cần duyệt theo chiều sâu, chỉ cần sắp xếp từ điển các đường dẫn
  • Nếu cần duyệt theo chiều rộng, có thể đảo ngược đường dẫn theo dấu phân cách, thêm các mục rỗng để cân bằng độ sâu rồi sắp xếp
  • Ví dụ này nhằm minh họa khái niệm; trên thực tế, cách tự nhiên hơn là tách chuỗi theo dấu phân cách thành các mảng rồi xử lý
  • Nhìn chung, danh sách phẳng dễ làm việc hơn, và nếu có thể thì nên ưu tiên đưa các mục vào plain old lists

Ẩn dụ scrapbook trên sàn nhà

  • Khi làm scrapbook cá nhân, bạn có thể trải ảnh, ghi chú, bưu thiếp, vé và các thứ khác ra sàn rồi tạo thành các nhóm
  • Với con người, quan hệ nhóm có thể nhìn rất rõ, nhưng bản thân sàn nhà không có cơ chế vật lý nào để ép buộc các quan hệ đó
  • Điểm cốt lõi của ẩn dụ này là quan hệ được biểu đạt và quan hệ cấu trúc thực tế có thể khác nhau
  • Danh sách trong UI cũng vậy: cách sắp xếp khiến con người thấy có phân cấp không nhất thiết có nghĩa là mô hình dữ liệu bên trong thật sự có phân cấp

Khi nào cần cây thực sự

  • Cách dựa trên thụt lề hoặc ký hiệu trong chuỗi cần được điều chỉnh rất nhiều tùy từng tình huống, và trong ngữ cảnh lập trình nói chung có thể bị xem là một kiểu hack
  • Nếu thực sự cần biết quan hệ giữa các mục, nên dùng cấu trúc cây thực thụ phù hợp với mô hình dữ liệu, như ID cha hoặc bảng join cha-con
  • Nếu cần mức tổ chức như tủ hồ sơ vật lý và các cấp thư mục để phân loại những dự án nghiên cứu quy mô lớn, thì “cách trên sàn” sẽ không phù hợp
  • Nếu một dự án về sau thực sự cần biết quan hệ giữa các mục mà ngay từ đầu lại giả lập cấu trúc bằng thụt lề hay số lượng ký hiệu trong chuỗi, đó có thể trở thành con đường đau đớn suốt vòng đời và thời gian bảo trì của dự án

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-01-01
Các ý kiến trên Hacker News

  • Cách thứ nhất, tức cách trông như “hiển nhiên chỉ có cách này”, được gọi là danh sách kề (adjacency list)
    Cách thứ hai, “đơn giản hơn nhiều”, tôi không nhớ đã từng thấy trước đây; nó có những nhược điểm rõ ràng, nhưng trong một số trường hợp có vẻ là đủ dùng
    Cách thứ ba, “đặt namespace”, được gọi là đường dẫn cụ thể hóa (materialized path); còn có một cách khác để biểu diễn cây là tập lồng nhau (nested sets): https://www.ibase.ru/files/articles/programming/dbmstrees/sq...
    Thời người ta còn nghiêm túc làm việc với cơ sở dữ liệu quan hệ, những điều này đều rất quen thuộc; chẳng hạn cũng có bài như http://www.dbazine.com/oracle/or-articles/tropashko4/
    Giờ thì có vẻ như kiến thức đã bị lãng quên

    • Một trong những khoảnh khắc tôi ghét nhất ở chỗ làm cũ là khi tôi phải rất vất vả giải thích một vấn đề, rồi có ai đó nhận ra đó là một khái niệm đã có sẵn, đã có tên và đã được nghiên cứu
      Khi đang tự mình nắm bắt nhiều mặt của vấn đề, tôi thấy thật sự rất khó tìm ra tên gọi đã có của khái niệm đó
    • Đúng vậy. Các sinh viên mới tốt nghiệp trẻ được tuyển gần đây có xu hướng nhồi nhét mọi thứ vào tài liệu NoSQL và hầu như không muốn nghĩ đến mô hình hóa dữ liệu
      Cuối cùng họ xử lý toàn bộ logic hiển thị cây trong code, trong khi chỉ với cơ sở dữ liệu quan hệ hiện đại và một vài CTE cũng đã có thể xử lý rất nhiều use case một cách gọn gàng mà gần như miễn phí, nên khá đáng tiếc
    • Khó có thể gọi là kiến thức bị lãng quên. Cũng có cuốn sách “Joe Celko's Trees and Hierarchies in SQL”
      https://www.oreilly.com/library/view/joe-celkos-trees/978155...
    • Nếu quan tâm đến chủ đề này, tôi khuyên trước hết nên tìm đọc các sách của https://en.m.wikipedia.org/wiki/Joe_Celko

  • Postgres có kiểu dữ liệu ltree và các toán tử tìm kiếm hoạt động native theo kiểu này: https://www.postgresql.org/docs/current/ltree.html
    Ví dụ, có thể thêm dữ liệu như CREATE TABLE test (path ltree);, INSERT INTO test VALUES ('Top');, INSERT INTO test VALUES ('Top.Science');, INSERT INTO test VALUES ('Top.Science.Astronomy');
    rồi dùng SELECT path FROM test WHERE path <@ 'Top.Science'; để tìm Top.Science và Top.Science.Astronomy

    • Lưu ý cho lập trình viên: một điểm đặc biệt của ltree là các đường dẫn trung gian, vốn sẽ trở thành nút cha nếu vẽ thành cây, không nhất thiết phải thực sự tồn tại
      Trong ví dụ trên, dù xóa bản ghi Top.Science, bản ghi Top.Science.Astronomy cũng không bị cắt bỏ
      Các label của giá trị ltree gợi ra một cây logic thông qua đường dẫn cụ thể hóa, nhưng không bắt buộc phải có bản ghi tương ứng với mọi nút cha được ngụ ý
      Tùy ứng dụng, đây có thể chính xác là hành vi bạn muốn, hoặc hoàn toàn ngược lại. Nếu là trường hợp sau, cần có cơ chế riêng để duy trì tính toàn vẹn
    • Tôi thắc mắc liệu khi lưu đường dẫn tệp có thể dùng / làm dấu phân cách không
    • Tôi thắc mắc liệu có ai có kinh nghiệm về hiệu năng không. Trông có vẻ xử lý regex khá nhiều
    • SQL Server cũng có chức năng rất giống vậy[1], và theo trải nghiệm của tôi thì hoạt động khá tốt
      [1] https://learn.microsoft.com/en-us/sql/relational-databases/h...
    • Tôi thắc mắc liệu có thể làm điều tương tự bằng cột JSON không. Khi đó có thể dùng cả các kiểu dữ liệu không phải chuỗi cho node
      Tuy nhiên cũng lo rằng index JSON có thể không hoạt động tốt bằng index ltree

  • Vấn đề ở đây là giá trị trong cấu trúc thường không nằm ở cây dùng để hiển thị, mà nằm ở cấu trúc phân cấp của dữ liệu
    Rất có thể bạn sẽ phải làm những việc như duyệt dữ liệu, thể hiện quan hệ, sắp xếp lại, v.v.
    Đưa thông tin trực quan vào cấu trúc dữ liệu của cơ sở dữ liệu có vẻ nguy hiểm và thiển cận

    • Tác giả đã nói rõ rằng “mọi người luôn nghĩ phải mã hóa quan hệ cha-con một cách chính thức, nhưng thực tế không phải lúc nào cũng vậy, đôi khi chỉ cần cách hiển thị lồng nhau”, nên phản ứng như vậy hơi lạ
      Câu trả lời là “Không, không thể thế được” sao?
      YAGNI là một heuristic thiết kế nổi tiếng là có lý do. “Hãy luôn giả định là sẽ cần” không đúng
    • Trớ trêu là vẫn đang dùng ID cha trong dữ liệu
      Chỉ là thay vì lưu trong một cột chuyên dụng với kiểu dữ liệu được tối ưu, nó được gắn vào đầu chuỗi dữ liệu
      Nó có thể không phải số và cũng có thể không phải cột ID, nhưng vẫn là một định danh trỏ tới một giá trị kỳ vọng khác, nên việc đổi định dạng không khiến nó không còn là ID cha
    • Ngay cả trong cách mã hóa thứ tự/thụt lề của bài gốc, vẫn phải có thể tái dựng quan hệ cha-con một cách dễ dàng
      Tất nhiên cần đảm bảo không lưu các thụt lề sai kiểu như con không có cha
      Vì vậy tôi nghĩ cách dễ nhất là trước hết lưu theo thứ tự/độ sâu, rồi khi triển khai các tính năng cần thiết thì migrate sang mô hình cha/con
      Tuy nhiên, “thụt lề” nên được định nghĩa trừu tượng hơn là độ sâu trong cây, chứ không phải số khoảng trắng để render. Như vậy dễ tìm dữ liệu sai, dễ migrate về sau, và cũng có độ linh hoạt render theo từng người dùng như dùng / lồng nhau, tab, 8 dấu cách, 4 dấu cách, 1 dấu cách, v.v.
    • Nếu có cấu trúc dữ liệu như struct item_t { char key[255]; char display_value[255]; }, và key có dấu phân cách đường dẫn nhất quán như a/b/c, thì việc tìm cha và con rất dễ
      Trường hợp tệ nhất thì quét tuyến tính mảng là được; nếu đã được sắp xếp, chỉ cần nhìn các mục trước đó cho tới khi tới cha
    • Rất đồng ý. Phi chuẩn hóa đôi khi có thể là lựa chọn tốt, nhưng tôi không thấy trường hợp này là một biện minh hợp lý

  • Tôi từng bắt đầu một công ty có rất nhiều dữ liệu dạng cây. Chuyển cấu trúc cây thành danh sách thụt lề có thể làm trong thời gian O(n)
    Đó từng là một trong các câu hỏi phỏng vấn khi ấy, và có nhiều cách lưu trữ trong các cơ sở dữ liệu SQL để có thể lấy nhanh một phần cây và render mà không cần truy vấn đệ quy
    Khi đã hiểu các khái niệm này, việc lưu dữ liệu đúng nghĩa là cây có nhiều lợi thế hơn hẳn so với kiểu thụt lề như thế này

    • Nếu không cần những lợi thế đó thì cũng không quan trọng lắm

  • “Một cách để lấy dữ liệu cấu trúc cây từ cơ sở dữ liệu quan hệ bằng truy vấn SQL là dùng CTE (Common Table Expressions) đệ quy, và nó thú vị đúng như cái tên của nó”
    CTE, kể cả CTE đệ quy, không có gì đáng sợ; khi quen rồi tôi đảm bảo là nó thực sự thú vị

    • CTE cũng chẳng thú vị lắm. Việc copy cả tháp CTE sang một cửa sổ SQL khác để debug phần mình quan tâm không phải kiểu giải trí tôi theo đuổi
    • Khi lắp ráp dữ liệu cây từ biểu diễn đã chuẩn hóa, CTE đệ quy cực kỳ chậm
      Để dựng đường dẫn nút có độ sâu phân cấp là d, thời gian nhận kết quả truy vấn chậm hơn ít nhất d lần
      Ưu điểm là thao tác chỉnh sửa cây rẻ, nhưng chuyện đó xảy ra hiếm hơn nhiều so với đọc
    • CTE thì ổn. Thay vì nhúng sẵn thông tin này vào bảng, tác giả cũng có thể tạo một view chứa tên đã được định dạng bằng CTE

  • Có thể thấy sự khác biệt giữa HN và Reddit ở điểm “thường thì mọi người không thực sự muốn hay cần một cây, mà chỉ cần thứ trông giống cây”
    Trên HN, bình luận con là nextSibling của bình luận cha, và được làm cho trông như cây bằng cách cộng thêm 1 vào giá trị thụt lề của cha
    Còn Reddit, ít nhất là old.reddit.com, thì bình luận con thực sự được lồng bên trong bình luận cha. Trang mới thì tôi không rõ

    • Ý là cấu trúc HTML, chứ không phải phần hiển thị thực tế đúng không? Nhìn trên màn hình thì gần như giống hệt nhau
    • Khó tưởng tượng backend lại thực sự lưu như vậy
      Mọi thao tác trên dữ liệu sẽ trở thành một mớ phức tạp: suy luận cấu trúc cây rồi dịch ngược lại sang định dạng cây ngầm định
    • Nếu vậy thì chức năng thu gọn hoạt động thế nào nhỉ

  • Ý chính của bài rất đơn giản: hãy dùng cấu trúc phù hợp với vấn đề
    Tuy nhiên tôi cho rằng phần kể chuyện bị sai. Không nhất thiết phải dùng CTE để lấy cây từ cơ sở dữ liệu; có thể lấy một danh sách phẳng rồi dựng cây cục bộ. Dù sao sau đó cũng rất có thể phải làm vậy để thao tác tiếp
    Theo cùng logic đó, có thể bảo người dùng cơ sở dữ liệu quan hệ để lưu danh sách rằng hãy lưu vào file văn bản. Tại sao phải chịu chi phí độ trễ mạng?
    Ngược lại, cấu trúc được đề xuất hoạt động không tốt khi cần di chuyển nhánh và thay đổi độ sâu trong một cây đủ lớn, vì nó tốn chi phí tuyến tính
    Lẽ ra nên nói rõ ý định ngay từ đầu. Đừng giải thích ba ví dụ rồi đến kết luận lại vô hiệu hóa bằng câu “nếu cần cây thì hãy dùng cây”. Dù vậy, nếu đặt điều đó ở đầu bài thì đã đỡ clickbait hơn nhiều

  • Vài năm trước tôi có một nhận ra tương tự về OpenGL. Điều cần vẽ không phải là một thế giới các đối tượng 3D phân cấp, mà là một danh sách tam giác đã sắp xếp
    Ý nghĩ đó như bật công tắc trong đầu tôi, và nhiều tối ưu hóa trở nên rất dễ dàng

    • Đúng vậy. Trong game 3D sau năm 2000, sự đơn giản là một sức mạnh lớn
      Ngay cả trong các game có hệ phân cấp entity phức tạp, khi đưa vào render queue thì thường vẫn phải làm phẳng vì các lý do như sắp xếp theo độ trong suốt
      “Danh sách phẳng các sự vật” cũng là nền tảng của ECS/DOD

  • Có hẳn cả một cuốn sách về cách xử lý những việc như vậy trong cơ sở dữ liệu
    https://www.oreilly.com/library/view/joe-celkos-trees/978155...

    • Người ta cứ nói mọi cuốn sách đều dành cho người mới bắt đầu, hay đấy

  • Một cách khác để tạo cây giả là lưu blob JSON
    Nếu dữ liệu chỉ có các quan hệ nội bộ, cách này có thể dễ hơn việc cố giữ số thứ tự vừa duy nhất vừa có thứ tự

    • Cây biểu diễn bằng JSON lồng nhau thậm chí có thể được xem là “thật” hơn so với cây ảo có được bằng cách lưu tham chiếu cha trong cơ sở dữ liệu