B-Tree trong Factorio

 (razberry.substack.com)
4 điểm bởi GN⁺ 2023-11-17 | 1 bình luận | Chia sẻ qua WhatsApp
  • Sau khi đọc chương B-Tree của câu lạc bộ sách Database Internals, tác giả đã triển khai cấu trúc dữ liệu không bằng mã nguồn mà bằng các cấu trúc nhà máy trong Factorio để kiểm chứng khái niệm một cách trực quan
  • BST chỉ có thể rẽ nhánh trái/phải khi các khóa có thể sắp xếp được; nếu giá trị dồn về một phía, hiệu quả tìm kiếm có thể giảm xuống mức của danh sách tuyến tính
  • Với lưu trữ dựa trên đĩa, chi phí tái cân bằng của BST và việc phải đọc nhiều trang là gánh nặng; B-Tree giảm vấn đề này bằng cách chứa nhiều khóa trong một nút
  • Bản triển khai trong Factorio dùng rương gỗ và tay máy lọc màu tím để biểu diễn nút và phép so sánh, đồng thời đặt ra một thứ tự sắp xếp tùy ý cho các vật phẩm để tạo đường tìm kiếm
  • Phiên bản B-Tree dùng 3 khóa và 4 con trỏ cho mỗi nút, nên ở 2 tầng chứa được nhiều khóa hơn BST rất nhiều, nhưng vẫn còn vấn đề về cách biểu diễn giá trị và sắp xếp thủ công

Khác biệt giữa BST và B-Tree

  • Cây tìm kiếm nhị phân (BST) là cấu trúc trong đó mỗi nút chứa một khóa; khóa nhỏ hơn được gửi sang nút bên trái, còn khóa lớn hơn được gửi sang nút bên phải
    • Ví dụ bắt đầu với khóa gốc 8, bên trái là 3, bên phải là 10
    • Chỉ hoạt động với giá trị có thể sắp xếp, tức là có thể so sánh lớn nhỏ giữa các giá trị khóa
  • Nếu nhiều giá trị chỉ được thêm vào một phía, BST sẽ mất cân bằng
    • Trong trường hợp xấu nhất, nó gần như trở thành một danh sách sắp xếp tuyến tính kiểu 8 -> 10 -> 14
    • Có thể sửa mất cân bằng bằng cách dùng 10 làm pivot ở gốc và đặt 8, 14 ở hai bên
  • Trong lưu trữ dựa trên đĩa, BST bất lợi
    • Nếu liên tục duy trì tái cân bằng, phải thường xuyên cập nhật đĩa và con trỏ
    • Các nút lân cận có thể được lưu ở những trang khác nhau, nên một lần tìm kiếm cũng có thể phải đọc nhiều trang
  • B-Tree chứa nhiều khóa trong một nút và dùng số khóa + 1 con trỏ để trỏ đến các nút con
    • Nút [17 | 24] trong ví dụ rẽ nhánh tới ba nút con: các khóa nhỏ hơn 17, các khóa nằm giữa 17 và 24, và các khóa lớn hơn 24

Cây tìm kiếm được triển khai trong Factorio

  • Factorio là trò chơi xây dựng nhà máy, và trong bản triển khai này, mỗi nút của cây được biểu diễn bằng một cấu trúc trong game
  • Trước hết là tạo một BST đơn giản
    • Mỗi nút có một rương gỗ chứa một khóa và hai đường dẫn nối tới các nút khác
    • Vì giữa các nguyên liệu không có cách so sánh mặc định, tác giả đặt tiêu chí sắp xếp tùy ý theo thứ tự wood, coal, stone, brick, copper, iron, steel
    • Tay máy lọc màu tím đảm nhiệm việc kiểm tra so sánh
      • Ở nút đầu tiên, một tay máy kiểm tra xem vật phẩm có bằng brick hay không
      • Tay máy thứ hai kiểm tra xem vật phẩm có nhỏ hơn brick hay không, chẳng hạn wood, coal, stone
      • Tay máy thứ ba lọc ra các giá trị lớn hơn, chẳng hạn copper, iron, steel
    • Ở phía trên bên phải còn có bộ thu gom rác để dọn các vật phẩm đi nhầm vào băng chuyền
  • Bản triển khai B-Tree cần nhiều cấu trúc hơn trong một nút
    • Mỗi nút có 3 khóa, 3 tay máy lọc, 3 rương gỗ và 4 con trỏ con
    • Có thể chứa nhiều thông tin hơn ở cùng độ sâu
    • Ở 2 tầng, BST chứa 2 khóa, còn B-Tree chứa 12 khóa
    • Ở 3 tầng, B-Tree tăng lên tới 48 khóa
  • Vì không muốn chọn và sắp xếp thủ công 48 vật phẩm trong Factorio, B-Tree được để trống cho đến khi tìm được cách biểu diễn giá trị tốt hơn
  • So sánh BST và B-Tree cạnh nhau, đồng thời kèm cả video YouTube

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-11-17
Ý kiến trên Hacker News

  • Đây là một thiết kế kém hiệu quả, nhưng việc triển khai lý thuyết khoa học máy tính trong Factorio cũng tất yếu có nghĩa là chơi theo một cách không tối ưu
    Factorio không phải là trò chơi được tạo ra để khoe B-Tree; các công cụ cuối cùng cũng được thiết kế để chơi Factorio

    1. Điểm cốt lõi của các cây tự cân bằng như cây 2-3, cây đỏ-đen, B-Tree không nằm ở bản thân cấu trúc một cây đơn lẻ, mà ở phần nó tự cân bằng; trong Factorio thì không thể khiến cây tự tái cấu trúc chính nó, nên đặc trưng lớn nhất bị thiếu
    2. Xét từ góc độ tối ưu hóa, inserter chậm hơn băng chuyền. Dù dùng 4 inserter cho mỗi băng chuyền thì cũng chỉ chuyển được khoảng 12 món mỗi giây, còn băng chuyền xanh có thể đẩy 45 món mỗi giây. Nếu là thiết kế tối ưu chỉ dùng băng chuyền, cần dùng splitter hoạt động ở mức 45 món mỗi giây
    3. Vì vậy, điểm giao nhau giữa splitter và khoa học máy tính trong Factorio là splitter của Factorio và mạng Benes. Nếu muốn tìm hiểu các mạng chỉ được tạo từ crossbar 2 đầu vào 2 đầu ra, có thể bắt đầu từ https://en.wikipedia.org/wiki/Clos_network. Mạng Benes chỉ là mạng Clos kích thước 2 đầu vào 2 đầu ra, còn mạng Clos có thể có các kích thước tùy ý như 5 đấu 7
      Có vẻ meta đáng tìm trong Factorio là thiết kế “băng chuyền hỗn hợp”
    • Một dạng cụ thể hơn là băng chuyền sushi, trong đó một băng chuyền chở cân bằng nhiều nguyên liệu và chạy vòng lại chính nó
      Một số thiết kế chỉ nhận vật phẩm mới theo tỷ lệ định sẵn, một số thiết kế thì thực sự tái cân bằng khi bị lệch. Cá nhân tôi thích cái này nhất: https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      Ví dụ này dùng logic mạch trong game, nhưng diễn đàn Factorio cũng có mục không dùng mạch: https://forums.factorio.com/viewforum.php?f=202
      Điểm thú vị là đối tượng “fish” trong Factorio là một vật phẩm đùa vô dụng, và vì nó không được dùng vào đâu nên đôi khi được dùng làm giá trị null, cờ đánh dấu rằng băng chuyền đã hoàn tất một vòng, hoặc công cụ gỡ lỗi: https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • Tôi tự hỏi sẽ thế nào nếu có một bản mở rộng Factorio kiểu “Scriptorio” cho phép đặt JSON lên băng chuyền. Kèm theo đó là các nhà máy hàm JavaScript hoặc Lua
      Khi đó không chỉ các đối tượng để chèn/tìm kiếm, mà cả chính B-Tree cũng có thể được di chuyển bằng băng chuyền và inserter
      Ta cũng có thể viết một hàm tìm kiếm đệ quy bằng một vòng băng chuyền chạy qua nhà máy: bóc cây từng tầng một cho tới khi chạm lá, rồi ngắt vòng lặp để xuất kết quả
      Đây là một mô hình thực thi thú vị, gần với luồng dữ liệu hơn là JavaScript chuẩn. Có nên cho phép “đường hầm lượng tử” hay “tác động từ xa” bằng cách để nhiều tham chiếu từ các băng chuyền, inserter và nhà máy khác nhau cùng trỏ tới một đối tượng JSON nền tảng không? Có thể sẽ hữu ích, nhưng Factorio theo truyền thống xem mỗi vật phẩm vật lý có một danh tính riêng, nên không hỗ trợ nhiều tham chiếu có lẽ sẽ “thực tế” hơn. Hoặc cũng có thể nghiên cứu công nghệ “Quantum Tunneling JSON”, rồi chỉ cho phép tạo nhiều tham chiếu trong “JSON Reference Entangler Factory”
    • Đọc lướt bài về mạng Clos, có vẻ nếu có thể xây dựng một mạng như vậy trong Factorio thì cũng có thể tạo các thiết kế mạng nơ-ron đơn giản như thấy ở đây: [1]
      Có vẻ cũng có thể thay đổi đầu ra bằng cách gán trọng số cho mật độ tài nguyên đến một vị trí nhất định. Nhìn vào cơ chế ở đây [2], có lẽ có thể dùng việc hợp nhất/tách và ba tốc độ băng chuyền để tạo ra quyết định giả lập theo trọng số mật độ
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • Lần tới tôi muốn xem liệu có thể triển khai cả tự cân bằng không. Tôi nghĩ bot có thể hữu ích ở đây, nhưng không rõ có thể khiến bot xây dựng bản thiết kế một cách động hay không
    • Vì thế nên tôi không chơi Factorio. Mức tài nguyên não bộ đó có thể được dùng cho nhân loại, và nếu trình bày kết quả thì còn có thể nhận phản hồi trên mạng xã hội
      Những trò chơi đòi hỏi chất xám để đổi lấy các con số trên màn hình nằm ở cuối danh sách của tôi. Tôi muốn học điều gì đó mới
      Có thể có yếu tố giải đố và ta có thể quyết định rằng nó thú vị, nhưng chẳng phải ta cũng có thể quyết định rằng học tập cũng thú vị sao

  • Công trình tuyệt vời
    Có người nói họ đang đọc “Database Internals” trong câu lạc bộ sách, và tuần này là chương 2 về B-Tree
    Nhân tiện, dù đăng ký đã đóng, nếu muốn bạn vẫn có thể lấy Database Internals và theo dõi lịch trình cùng ghi chú ở đây theo kiểu “chỉ đọc”: https://eatonphil.com/2023-database-internals.html

  • Các lý do cho rằng “cây tìm kiếm nhị phân không phù hợp với lưu trữ dựa trên đĩa” cũng áp dụng cho lưu trữ trong bộ nhớ
    Tìm kiếm trong một nút B-Tree nhanh hơn việc đi theo cùng lượng con trỏ trong cây nhị phân. Tất nhiên độ phức tạp triển khai sẽ tăng, nhưng nếu không dùng C thì thường cũng sẽ không tự triển khai map dựa trên cây
    Cũng có thể có biến thể kiểu đưa nhiều mục hơn vào các nút trong và chỉ lưu giá trị ở lá. Nếu không phải chỉ tạo tập hợp thay vì map. Nếu nối thêm cả các nút lân cận thì về cơ bản nó gần với danh sách bỏ qua (skip list)

  • Không hiểu sao đúng lúc này lại có nội dung Factorio xuất hiện, làm mình lại muốn lao vào thêm khoảng 100 giờ nữa. Năm nay đã có quá nhiều game hay đáng chơi rồi

    • Khoảng cuối năm sau dự kiến sẽ có đợt cân bằng lại quy mô lớn và bản mở rộng Space Age, nên đợi đến lúc đó cũng có thể là lựa chọn ổn

  • Toàn bộ chuyện này có thể làm bằng splitter, và có vẻ không cần rương hay filter inserter. Phần giải thích thì hay

    • Tôi không biết làm thế nào
      Đây không chỉ đơn giản là chia đầu ra thành nhiều dòng. Các rương đại diện cho item được lưu trong “nút” tương ứng của B-Tree được bố trí hai chiều ở đây
      Tôi không có thời gian xem video, nhưng nhìn bài viết và ảnh chụp màn hình thì logic liên quan được gắn với inserter, để gửi item theo đúng đường dẫn đến nút con phù hợp nhằm duy trì tính chất “đã sắp xếp” của cây
      Nhìn cách chọn giá trị khóa trong bài gốc thì dùng splitter để chia cũng có thể được, nhưng theo tôi nhớ splitter chỉ nhận được một bộ lọc, nên ở mỗi điểm rẽ sẽ cần nhiều splitter. Nghĩa là cần số lượng splitter bằng số item ở điểm rẽ đó. Filter inserter cho phép nhiều bộ lọc nên trong trường hợp này tốt hơn một chút, và cũng có thể thấy điều đó trong ảnh chụp màn hình đầu tiên
      Tất nhiên cũng có thể bỏ hẳn thiết kế B-Tree và dùng n splitter để sắp xếp vào n rương, nhưng như thế không thú vị và có vẻ cũng không phải điều bài gốc hướng tới
    • Họ đang gán nhiều item cho mỗi inserter
      Bộ lọc của splitter chỉ gửi một loại item sang một phía và phần còn lại sang phía kia. Nhưng ví dụ này khác, vì nhiều loại đi sang một phía và nhiều loại khác đi sang phía còn lại
    • Cần sắp xếp/lọc nhiều item. Ví dụ ở nút đầu tiên, gỗ, than và đá phải được gửi sang trái, còn kim loại sang phải, nhưng bộ lọc splitter chỉ có thể lọc một item

  • Tôi tò mò Factorio có thực sự là một game hay đến vậy không. Ai cũng khen, nhưng chủ đề xây nhà máy trông hơi nhàm chán và tôi lo game sẽ quá lặp lại

    • Trước khi chơi tôi cũng khá hoài nghi và có cùng nỗi lo. Nhưng đến lúc nhận ra thì đã đổ vào đó hơn 100 giờ rồi
    • Những người chơi Factorio mà tôi biết đều đã đổ vào đó hơn 1.000 giờ

  • Thật sự rất tuyệt, nhưng nói giữa những người muốn viết lách với nhau thì việc không dùng chữ hoa ở đầu câu khiến tôi thấy khá mất tập trung

  • Tôi đã tưởng họ sẽ triển khai bằng hệ thống mạch của Factorio