Truy tìm kiểu dữ liệu đã biến mất

 (hillelwayne.com)
2 điểm bởi GN⁺ 2024-03-05 | 1 bình luận | Chia sẻ qua WhatsApp
  • Đồ thị xuất hiện khắp nơi trong phần mềm, như dependency, liên kết web, không gian trạng thái của model checker, khóa ngoại trong DB quan hệ, nhưng các ngôn ngữ lập trình phổ biến hầu như không có kiểu dựng sẵn hoặc hỗ trợ trong thư viện chuẩn
  • Lý do đầu tiên khiến việc tạo kiểu đồ thị dựng sẵn trở nên khó là có quá nhiều loại đồ thị như có hướng/vô hướng, đơn/đa đồ thị, siêu đồ thị, và các tính chất cụ thể có thể làm thay đổi lớn lựa chọn thuật toán cũng như hiệu năng
  • Mỗi cách biểu diễn như danh sách cạnh, danh sách kề, ma trận kề, cấu trúc tham chiếu có đặc tính bộ nhớ và hiệu năng truy vấn khác nhau, nên khó có một biểu diễn đa dụng đáp ứng mọi trường hợp sử dụng
  • Thuật toán đồ thị khó triển khai và thường chạy trên đầu vào lớn, nên như trong các trường hợp Nosey Parker và Gecode, biểu diễn và cách duyệt được tùy biến theo bài toán có thể trở nên quan trọng hơn thư viện đa dụng
  • Đồ thị hiếm xuất hiện trong thư viện chuẩn vì các đánh đổi về kiểu, biểu diễn, thuật toán, hiệu năng và gánh nặng bảo trì là rất lớn; thư viện bên thứ ba cũng có thể bị giới hạn hoặc chậm

Đồ thị phổ biến nhưng hỗ trợ từ ngôn ngữ còn thiếu

  • Đồ thị gồm các nút và cạnh; nút và cạnh có thể chứa dữ liệu
  • Trong kỹ nghệ phần mềm, đồ thị xuất hiện dưới nhiều dạng
    • Dependency giữa các package và import giữa các module tạo thành đồ thị có hướng
    • Internet là một đồ thị liên kết giữa các trang web
    • Model checker khám phá không gian trạng thái của mọi cấu hình khả dĩ; nút là trạng thái và cạnh là chuyển tiếp hợp lệ
    • Cơ sở dữ liệu quan hệ có thể được xem là các bản ghi là nút, khóa ngoại là cạnh
    • Đồ thị có thể được xem là sự tổng quát hóa của danh sách liên kết, cây nhị phân và bảng băm
  • Trong logic nghiệp vụ, đồ thị cũng thường xuất hiện, như quan hệ trích dẫn giữa các bài báo, tuyến đường trong mạng giao thông, kết nối trong mạng xã hội
  • Dù đồ thị thường xuyên cần đến, hầu hết ngôn ngữ phổ biến không cung cấp đồ thị như kiểu dựng sẵn, và cũng hiếm khi đưa vào thư viện chuẩn
  • Nhiều hệ sinh thái cũng thiếu thư viện đồ thị bên thứ ba đủ vững chắc, nên thường phải tự triển khai

Thiết kế kiểu đồ thị có quá nhiều lựa chọn

  • Ngoài đồ thị có hướng và đồ thị vô hướng, đồ thị còn có nhiều biến thể khác
    • Đồ thị đơn, trong đó giữa hai nút có tối đa một cạnh, và đa đồ thị, cho phép nhiều cạnh
    • Siêu đồ thị, trong đó một cạnh nối 3 nút trở lên
    • Ubergraph, trong đó cạnh có thể trỏ tới cạnh khác
  • Mỗi biến thể lại kéo theo các quyết định thiết kế bổ sung
    • Phải quyết định có gán ID cho cạnh hay chỉ gán cho nút
    • Cũng phải quyết định lưu dữ liệu gì trong nút và cạnh
  • Có thể cung cấp mọi đồ thị dưới dạng một kiểu đa dụng như “đa siêu ubergraph có hướng” rồi để người dùng tự giới hạn, nhưng ngay lập tức nảy sinh hai vấn đề
    • Giao diện thay đổi, chẳng hạn kết quả của một phép toán là một giá trị đơn hay một danh sách
    • Nếu không tận dụng được tính chất đặc biệt của đồ thị, hiệu năng thuật toán sẽ kém đi
  • Ví dụ, với maximum weight matching, nếu biết đồ thị là đồ thị hai phía thì có thể dùng thuật toán nhanh, nhưng với đồ thị tổng quát thì cần thuật toán đa dụng chậm hơn
  • Với một bài toán P, đồ thị G và các thuật toán A·B·C, cũng phát sinh vấn đề dispatch thuật toán: phải chọn thuật toán nào để chạy
  • Một thư viện đồ thị hoàn hảo cần hỗ trợ nhiều loại đồ thị, nhưng như vậy thời gian dành để triển khai các thuật toán mà người dùng thực sự muốn sẽ ít đi
  • Thuật toán đồ thị có độ khó triển khai cao
    • Thuật toán find_shortest_path do người sáng lập Python viết sau đó đã được sửa năm lần
    • Nicole nói rằng mọi triển khai PageRank mà cô so sánh đều sai
    • NetworkX cung cấp khoảng 500 thuật toán đồ thị, riêng mã thuật toán đã gần 60.000 dòng
    • Toàn bộ thư viện chuẩn Python có khoảng 300 package, dưới 600.000 dòng
  • Người quản lý thư viện chuẩn phải quyết định đưa vào kiểu đồ thị nào, xử lý đặc biệt cho topo nào, thuật toán nào, nên gánh nặng bảo trì rất lớn
  • Python cũng nổi tiếng với “batteries included”, nhưng với PEP 594 đang đi theo hướng loại bỏ 20 module thư viện chuẩn

Cũng khó chọn một cách biểu diễn đồ thị duy nhất

  • Ngay cả khi chỉ xét đồ thị có hướng đơn giản nhất, vẫn có nhiều cách biểu diễn nội bộ
    • Danh sách cạnh: [[a, b], [b, c], [c, a], [c, b]]
    • Danh sách kề: [[b], [c], [a, b]]
    • Ma trận kề: [0 1 0; 0 0 1; 1 1 0]
    • Tập hợp các struct tham chiếu lẫn nhau
  • Hiệu năng thao tác thay đổi tùy cách biểu diễn
    • Nếu biểu diễn đồ thị có 100 nút, 200 cạnh bằng ma trận kề, ma trận 100×100 sẽ chứa 200 số 1 và 9.800 số 0
    • Nếu biểu diễn cùng đồ thị bằng danh sách cạnh, chỉ cần 200 cặp nút
    • Tùy ngôn ngữ và mức tối ưu hóa, chênh lệch bộ nhớ có thể hơn 20 lần
  • Ngược lại, với đồ thị có 100 nút, 8.000 cạnh, khi tìm cạnh giữa nút 0 và 93 thì kết quả khác đi
    • Ma trận kề có thể truy vấn O(1) bằng graph[0][93]
    • Danh sách cạnh phải duyệt 8.000 cạnh, nên mất thời gian O(|edge|)
  • Đồ thị có ít cạnh là đồ thị thưa, còn đồ thị có gần như mọi cạnh là đồ thị dày đặc
  • Một chương trình dựng đồ thị từ dữ liệu bên ngoài ban đầu có thể là đồ thị thưa rồi về sau trở thành đồ thị dày đặc, nên không có “lựa chọn luôn tốt” cho biểu diễn nội bộ
  • Nếu hỗ trợ dữ liệu nút, dữ liệu cạnh, nhiều loại nút và cạnh, độ phức tạp triển khai còn tăng thêm
  • Thư viện bên thứ ba thường chọn một trong hai hướng
    • Cung cấp một kiểu đơn giàu tính năng bao quát mọi trường hợp sử dụng, nhưng hy sinh hiệu quả
    • Cung cấp các kiểu đồ thị riêng theo từng cách biểu diễn và để người dùng tự quản lý dữ liệu nút/cạnh

Các đánh đổi được NetworkX và Petgraph thể hiện

  • NetworkX lưu đồ thị dưới dạng cấu trúc dict của dict của dict để có thể gắn dữ liệu tùy ý vào nút và cạnh
  • Nó cung cấp hàm chuyển đổi sang biểu diễn khác, nhưng không cung cấp cách làm việc trực tiếp trên chính biểu diễn đó
  • Thư viện đồ thị tiêu biểu của Rust, Petgraph, cung cấp các kiểu theo từng trường hợp sử dụng như graph, graphmap, matrix_graph
  • Bradford dùng Petgraph trong công cụ bảo mật Nosey Parker để tìm secret trong toàn bộ lịch sử repository git
    • Đồ thị benchmark là CPython, gồm 250.000 commit và 1.300.000 object
    • Mỗi nút commit chỉ có vài cạnh, nên đã chọn danh sách kề
  • Hỗ trợ nhiều biểu diễn làm tăng chi phí thêm thuật toán
    • Nếu viết thuật toán riêng cho từng biểu diễn, gánh nặng bảo trì tăng 3–4 lần
    • Nếu viết bằng abstraction đa dụng trên kiểu đa hình, hiệu năng giảm
  • Một người được phỏng vấn ước tính thuật toán đồ thị tự viết có thể nhanh hơn thuật toán đa dụng hơn 20 lần

Ràng buộc hiệu năng là vấn đề cốt lõi của thư viện đồ thị

  • Trong thuật toán đồ thị có nhiều bài toán NP-complete hoặc khó hơn
    • 14 trong 21 bài toán NP-complete canonical của Karp là bài toán đồ thị
  • Bài toán đồ thị có thể chạy trên đầu vào rất lớn, nên cách biểu diễn và chi tiết triển khai quyết định liệu có thể chạy được hay không
  • Trong Nosey Parker, Bradford phải duyệt object graph để tái dựng snapshot filesystem cho từng commit
    • Bốn graph walker của Petgraph không mở rộng phù hợp với trường hợp sử dụng đó
    • Anh đã thiết kế ngay một thuật toán duyệt đồ thị “semi-novel”, giảm mức dùng bộ nhớ xuống còn 1/1.000
  • Zayenz nêu 15 puzzle như một trường hợp đồ thị quá lớn để xử lý toàn bộ
    • Tìm lời giải là chạy A* search trên không gian trạng thái
    • Không gian trạng thái có hơn 20 nghìn tỷ trạng thái
    • Nếu sinh tất cả nút thì đã là trạng thái thất bại
  • Trong dự án nghiên cứu thêm đồ thị vào constraint solver Gecode mà Zayenz tham gia, kiểu đồ thị đa dụng cũng không thể cạnh tranh với lựa chọn biểu diễn phù hợp bài toán
  • Cơ sở dữ liệu đồ thị cũng được thiết kế để chạy các thuật toán đồ thị phức tạp, nhưng vấn đề hiệu năng vẫn còn
    • Theo Nicole, nếu không giới hạn độ sâu khi duyệt, cuối cùng sẽ thăm toàn bộ đồ thị
    • Ngay cả tìm kiếm theo độ sâu kiểu “đi ra ngoài 3 bước và tìm nếu có đường đi” cũng sẽ thăm rất nhiều dữ liệu
  • Trong tư vấn hiệu năng truy vấn đồ thị, Nicole chủ yếu thực hiện các migration rời khỏi cơ sở dữ liệu đồ thị
    • Ở một dự án, chỉ giữ nguyên một phép tính, còn lại viết lại thành quy trình MapReduce
    • Khó hiểu hơn, nhưng thực sự có thể hoàn tất qua một đêm

Vì sao đồ thị hiếm có trong thư viện chuẩn

  • Hỗ trợ đồ thị trên diện rộng hiếm gặp vì nhiều yếu tố chồng lên nhau
    • Có nhiều loại đồ thị
    • Mỗi loại đồ thị có nhiều cách biểu diễn
    • Có nhiều loại thuật toán đồ thị
    • Hiệu năng thuật toán nhạy với biểu diễn và chi tiết triển khai
    • Người ta chạy các thuật toán rất đắt trên các đồ thị rất lớn
  • Thư viện chuẩn của ngôn ngữ phải gánh quá nhiều quyết định thiết kế, đánh đổi và gánh nặng bảo trì
  • Lập trình viên cũng có lý do để tránh thư viện đồ thị bên thứ ba
    • Thư viện có thể quá hạn chế
    • Thư viện đa dụng có thể không đáp ứng yêu cầu hiệu năng
  • Đồ thị hữu ích cho phân tích hệ thống, nhưng ở giai đoạn triển khai, thường cần tự kiểm soát biểu diễn dữ liệu và lựa chọn thuật toán

Phụ lục: Các ngôn ngữ và công cụ liên quan cung cấp kiểu đồ thị

  • Ngôn ngữ truy vấn đồ thị (GQL) đóng vai trò tương tự SQL trong cơ sở dữ liệu đồ thị
    • Chưa có chuẩn được dùng rộng rãi, nhưng các ví dụ tiêu biểu gồm SPARQL và Cypher của Neo4j
    • GQL ở đây không nên bị nhầm với ngôn ngữ chuẩn GQL đang được phát triển
  • GraphQL không phải ngôn ngữ truy vấn đồ thị; tên gọi bắt nguồn từ mối liên hệ với Facebook Graph Search
  • Khác biệt chính giữa GQL và SQL là quan hệ, tức “join”, là thực thể hạng nhất
    • Trong dataset phim và con người, SQL triển khai các quan hệ “diễn xuất”, “đạo diễn”, “sản xuất” dưới dạng các bảng many-to-many riêng
    • Trong SPARQL, quan hệ là cạnh, nên có thể dễ dàng truy vấn “những người đảm nhận bất kỳ vai trò nào trong phim Y và vai trò của họ”
  • GQL cũng có thể hỗ trợ thao tác cạnh như đảo cạnh, hợp thành và bao đóng bắc cầu
    • SPARQL không cung cấp độ dài đường đi hay tính toán trong đường đi, chẳng hạn thu thập chuỗi phim nối hai diễn viên
    • GQL hỗ trợ những điều này sẽ trở nên phức tạp hơn nhiều
  • Ngôn ngữ đặc tả hình thức Alloy có các primitive duyệt đồ thị hữu ích cho kiểu dữ liệu relation, nên xử lý biểu diễn đồ thị dễ hơn so với ngôn ngữ lập trình thông thường
    • Tuy nhiên các primitive này dựa trên cạnh có nhãn và có thể không phù hợp với các biểu diễn đồ thị khác
  • Python đã thêm graphlib vào năm 2020
    • Không có phương thức nào ngoài TopologicalSorter
    • Đồ thị chỉ được nhận dưới dạng dict các nút
    • Biểu diễn đồ thị a -> b bằng dict hướng ngược như {b: [a]}
  • Tính đến năm 2023, nội bộ CPython không dùng graphlib
    • Trên GitHub, các file tham chiếu graphlib chưa tới 900
    • zoneinfo được thêm cùng năm xuất hiện trong hơn 6.000 file
    • Biểu thức def topological_sort( xuất hiện trong 4.000 file
    • Các topological sort tự triển khai thường dùng biểu diễn đồ thị khác với graphlib, nên khó chuyển đổi
  • Các trường hợp khác có kiểu đồ thị trong thư viện chuẩn gồm Erlang và SWI-Prolog
  • Cũng có những ngôn ngữ lập trình trong đó “mọi thứ đều là đồ thị”
    • Ví dụ gồm GP2 và Grape
    • Hiện đây là lĩnh vực mang tính học thuật cao
  • Các ngôn ngữ phần mềm toán học như Mathematica, MATLAB, Maple cũng có thư viện đồ thị dưới một hình thức nào đó
  • Bản cập nhật ngày 18/3/2024 đã tập hợp một số bình luận về bài viết ở trang riêng

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-03-05
Ý kiến trên Hacker News

  • Graphviz có thư viện đồ thị nền tảng riêng mà các dự án khác không dùng, và nó có cả ưu lẫn nhược điểm
    Dựa trên trải nghiệm đó, chúng tôi cũng đã trải qua một dạng hội chứng hệ thống thứ hai điển hình. Chúng tôi muốn tạo ra một thư viện đồ thị dạng mô-đun, an toàn kiểu và hiệu quả, nhưng rốt cuộc có lẽ đó chỉ là một biến thể của “tốt, nhanh, rẻ — chỉ được chọn hai”
    Mô-đun nghĩa là chúng tôi muốn có thể phát triển và biên dịch độc lập một tập hợp các thư viện thuật toán đồ thị; còn an toàn kiểu nghĩa là muốn bắt lỗi lập trình ở thời điểm biên dịch, hoặc muộn nhất là lúc liên kết, thay vì các lỗi runtime kiểu “nút không có thuộc tính color”
    Hiệu quả nghĩa là chi phí truy cập thuộc tính đồ thị phải rẻ như truy cập trường trong struct C; chúng tôi không muốn phải mang theo các bảng băm bên ngoài hay làm nhiều phép chuyển đổi chuỗi
    Các mục tiêu này có đáng trả giá hay có hợp lý không thì còn có thể tranh luận, nhưng khi đó đó là điều chúng tôi muốn. Trong phòng thí nghiệm có những người sáng tạo C++ nổi tiếng, và chúng tôi cũng từng định cho C++ thêm một cơ hội
    Gordon Woodhull, ban đầu là thực tập sinh rồi tiếp tục làm việc cùng chúng tôi, là một lập trình viên xuất sắc và đã viết một bản hiện thực thư viện đồ thị như vậy bằng C++ template. Mã nguồn cũng được đăng tại https://www.dynagraph.org/
    Những người còn lại không chắc liệu cuối cùng mình có thể hiểu được mã đó hoạt động ra sao hay không, nên đã review code cùng các nhà phát minh C++ nổi tiếng; sau rất nhiều màn hình mã và sự im lặng, kết luận là “có lẽ nó sẽ chạy”. Khi đó chúng tôi đã biết có thể mình đã vượt qua vách đá của độ phức tạp
    Lỗi template ở thời điểm biên dịch khiến một lỗi lấp đầy cả màn hình và tuôn ra những chi tiết mà có lẽ chỉ nhà phát minh C++ mới yêu nổi. Lỗi là ở chúng tôi, còn Gordon vẫn tiếp tục đẩy tới và làm cho cả layout đồ thị động chạy được trong Microsoft OLE
    Nhìn lại thì đó giống như Project Xanadu của riêng chúng tôi, và trong lúc chúng tôi lạc lối ở đó, những thứ như Gephi (Java), NetworkX, NetworKit (Python) đã xuất hiện. John Ellson, một kỹ sư phần mềm xuất sắc từng viết một phần Graphviz, đã hồi sinh công việc dòng chính

    • Có thể phân tích cú pháp cú pháp dot của Graphviz bằng NetworkX để lập kế hoạch chạy các công cụ đắt đỏ, và nhờ cấu trúc đồ thị mà có thể tự động song song hóa

  • Từ góc nhìn của người đã làm nhiều việc với đồ thị, tôi đã được hỏi vô số lần: “Tại sao ngôn ngữ lập trình không có kiểu dữ liệu đồ thị tích hợp?”
    Giờ tôi mừng vì không chỉ phải nói “làm cho tốt thật sự rất khó” rồi bảo họ tin mình, mà còn có thể chỉ tới một phân tích sâu hơn như bài này

    • Điều hơi buồn cười trong câu hỏi đó là nó bỏ qua sự thật rằng phần lớn ngôn ngữ thậm chí còn không có cấu trúc dữ liệu cây
      Những gì đa số ngôn ngữ cung cấp dưới dạng kiểu cấu trúc chỉ là mảng tĩnh, mảng động và danh sách liên kết. Những thứ như cây tìm kiếm nhị phân hay bảng băm là các trừu tượng ngữ nghĩa che giấu một phần năng lực của cấu trúc nền bên dưới, chứ không phải biểu diễn cấu trúc thuần túy
    • Đồ thị là một cấu trúc dữ liệu rộng, có cách biểu diễn thay đổi rất nhiều tùy yêu cầu, nên tôi từng nghĩ triển khai ở cấp domain là hợp lý hơn
      Phần trong bài nói “có quá nhiều lựa chọn triển khai” cũng đang nói điều tương tự. Rồi tôi thấy Petgraph [0] và lần đầu xem xét nghiêm túc một thư viện đồ thị đa dụng, thấy khá thú vị, nhưng đến nay tôi vẫn triển khai đồ thị ở cấp domain
      [0] https://github.com/petgraph/petgraph
    • Tôi cũng có trải nghiệm ngược lại. Khi lần đầu làm việc với đồ thị trong Tcl, tôi mặc nhiên nghĩ thư viện chuẩn sẽ không có thuật toán đồ thị, nhưng hóa ra là có, nhờ vậy không phải phát minh lại bánh xe
      https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
    • Quan trọng hơn “làm cho tốt thật sự rất khó” là việc có rất nhiều trade-off
      Gần như mọi ngôn ngữ đều cung cấp hash map, và dù trong một số tình huống tự triển khai có thể nhanh hơn, bản triển khai mặc định nhìn chung hoạt động tốt. Với đồ thị thì khó làm như vậy, và nếu có thể thì có lẽ cần cung cấp nhiều kiểu đồ thị
      Nói thêm, HashMap của Java hơi đặc biệt ở chỗ có thể điều chỉnh load factor, khác với đa số ngôn ngữ khác
    • Có thể đây là suy nghĩ rất ngây thơ, nhưng tôi xem con trỏ về cơ bản là kiểu đồ thị native
      Thứ mọi người muốn không hẳn là bản thân kiểu đồ thị, mà gần với các công cụ để duyệt đồ thị hơn

  • Tôi nghĩ đồ thị là một trừu tượng hơn là một cấu trúc dữ liệu hay kiểu dữ liệu
    Về căn bản, thứ cần để định nghĩa đồ thị chỉ là tập đỉnh v \in V và hàm Neighbors(v), và với phần lớn thuật toán đồ thị cơ bản thì thật sự chỉ cần chừng đó là đủ
    Phần còn lại là các ràng buộc tùy trường hợp. A->B có hàm ý B->A hay không, tập nút có thể được phân hoạch dưới các ràng buộc nhất định hay không, có màu hay nhãn hay không, v.v.
    Khái quát hơn nữa thì có thể đi tới hypergraph; trong trường hợp này chỉ cần tập đỉnh và tập hợp các tập đỉnh. Tùy mối quan tâm mà có thể biểu diễn theo vô số cách, còn đồ thị thông thường chỉ là một trường hợp đặc biệt
    Từ góc nhìn cơ sở dữ liệu, cũng có thể xem đây là vấn đề tối ưu hóa truy vấn và lập chỉ mục. Tùy bạn muốn đặt câu hỏi gì cho đồ thị mà cách biểu diễn giúp trả lời tốt hơn sẽ khác nhau. Cũng như không chỉ có một cách biểu diễn trừu tượng “bảng”, “đồ thị” cũng không thể kết thúc bằng một cách duy nhất

    • Lý do đồ thị có mặt ở khắp nơi là vì nó trừu tượng đến vậy
      Nó ở cùng mức trừu tượng với những con số thuần túy. Có thể nói rằng có các thư viện “số học” hữu ích cũng như các thư viện “mang tính đồ thị” hữu ích, nhưng không thật sự có nhiều thư viện “số” hay thư viện “đồ thị”. Những khái niệm như vậy quá trừu tượng để tạo thành API
    • Chỉ với tập đỉnh và Neighbors(v) thì đã bị ràng buộc khá mạnh rồi, vì nó không cho phép đa cạnh đi tới cùng một hàng xóm
    • Nếu hypergraph là tập đỉnh và tập hợp các tập đỉnh, thì nghe cũng hơi giống hệ thống tệp
      Tệp là đỉnh, còn thư mục là các tập đỉnh có thể lồng nhau

  • Có hai trở ngại cốt lõi
    Với các bài toán đồ thị đơn giản và nhỏ, chỉ cần tự viết danh sách kề bằng vector của vector là đã đủ dễ; còn với các bài toán đồ thị phức tạp và khổng lồ, muốn có hiệu năng thì buộc phải tùy biến phần triển khai đồ thị theo chi tiết của bài toán cần giải
    Vì vậy khó thấy kiểu hỗ trợ nào từ ngôn ngữ sẽ hữu ích. Trừ khi có một trình biên dịch siêu thông minh có thể phân tích mã và quyết định cái gì là tối ưu — danh sách kề, ma trận, mảng 3 chiều, v.v. — thì rất khó. Có lẽ còn lâu mới thấy loại tối ưu hóa như vậy trong trình biên dịch
    Đây là một ví dụ khác về hiện tượng mà Stroustrup đã thấy. Chúng ta chia sẻ mã tốt với những thứ nhỏ như vector và những thứ lớn như hệ điều hành, nhưng lại không chia sẻ tốt các bài toán cỡ trung

    • Ngay cả những thứ nhỏ cũng khó nói là thật sự được chia sẻ tốt. Vì mỗi ngôn ngữ lập trình lại có một triển khai vector riêng
      Trong một hệ sinh thái ngôn ngữ, API của vector nhỏ, nên có vẻ dễ chia sẻ. Hệ điều hành có API tương đối nhỏ so với độ phức tạp bên trong, và các thư viện tính toán số cũng vậy, nên chúng được chia sẻ tốt
      Ngược lại, với những thứ càng muốn tùy biến nhiều hơn như cấu trúc dữ liệu phức tạp, API càng phức tạp và càng khó chia sẻ. Rốt cuộc khả năng chia sẻ dường như phụ thuộc vào diện tích bề mặt của thứ được chia sẻ, tức kích thước tương đối của API
    • Việc nhìn vào một thuật toán được viết cho một kiểu đồ thị trừu tượng, rồi điền phần triển khai để tối ưu hóa cho thuật toán cụ thể đó, có vẻ khá phù hợp với lĩnh vực LLM chuyên biệt hóa mã

  • Electric Clojure dùng chính s-expression của Clojure làm cú pháp viết đồ thị, và dùng macro để cụ thể hóa luồng dữ liệu của hệ thống client/server phản ứng
    Ở đây use case là giao diện người dùng full-stack, nhưng ý tưởng có thể khái quát hóa. https://github.com/hyperfiddle/electric Tôi là nhà sáng lập
    Tôi cho rằng câu trả lời cho “các kiểu đồ thị đã đi đâu hết?” là: DSL để viết đồ thị phải biểu đạt được scope, luồng điều khiển và trừu tượng hóa; khi đó về thực chất nó trở nên đẳng cấu với một ngôn ngữ lập trình đã được giải phóng khỏi mô hình đánh giá. Trong Python và TypeScript, việc nhúng một ngôn ngữ lập trình hoàn chỉnh vào là khá khó
    Bài blog “Four problems preventing visual flowchart programming from expressing web applications” cũng đáng tham khảo
    https://www.dustingetz.com/#/page/four%20problems%20preventi...

  • Bài viết này chủ yếu trả lời câu hỏi “vì sao ngôn ngữ lập trình không hỗ trợ thuật toán đồ thị tốt hơn”, và dường như tập trung vào xử lý đồ thị “big data” hơn là hỗ trợ đồ thị nói chung
    Nếu nhìn rộng hơn về hỗ trợ đồ thị, còn có những câu hỏi rộng hơn như “vì sao OGM (Object Graph Mapper) không phổ biến như ORM”, “vì sao JSON được dùng rộng rãi còn RDF hay các dạng tuần tự hóa đồ thị cấp thấp khác thì không”
    Cuối cùng, tôi cho rằng lý do lịch sử đóng vai trò lớn. RDF ra đời hơi quá sớm, không tiến hóa đúng cách, và đã tích tụ một hệ sinh thái tiêu chuẩn học thuật cùng triển khai rất tệ. Thêm vào đó, đồ thị vốn phức tạp hơn một chút về triển khai và đường cong học tập, nên không mở rộng tốt tới nhiều lập trình viên
    Tôi sẽ không đặt quá nhiều trọng lượng vào phần “Graph Querying Language” của bài. Có những đoạn đọc giống khẩu hiệu marketing do một người hâm mộ Neo4J hoặc SPARQL viết mà chưa thực sự xây sản phẩm
    Bài nói rằng “khác biệt chính giữa mọi GQL và SQL là join, tức quan hệ là thực thể hạng nhất”, nhưng trong SQL join cũng là thực thể hạng nhất. Thậm chí còn có từ khóa JOIN
    Khi đi xuống tầng thấp hơn của ngôn ngữ truy vấn đồ thị và nhìn vào kế hoạch truy vấn, không có nhiều khác biệt đáng kể so với truy vấn dựa trên SQL. Việc chuẩn hóa GQL[0] đang được tiến hành như một phần mở rộng của SQL là bằng chứng cho điều đó
    SPARQL dễ dùng khi cần duyệt đường đi chính xác, nhưng nếu cố làm những việc phức tạp hơn một chút kiểu backend webapp, bạn sẽ nhanh chóng gặp các bẫy như join với giá trị chưa được binding, có thể vô tình làm bay toàn bộ tập kết quả
    [0]: https://en.wikipedia.org/wiki/Graph_Query_Language

    • Việc có từ khóa riêng thực ra gần như là bằng chứng mạnh rằng thứ đó không phải đối tượng hạng nhất
      Ví dụ, type class của Haskell không phải hạng nhất, và trong hầu hết ngôn ngữ lập trình, luồng điều khiển cũng không phải hạng nhất
    • JOIN, đặc biệt là join trong truy vấn RECURSIVE, là phần cốt lõi của cơ sở dữ liệu đồ thị, nên cơ sở dữ liệu quan hệ SQL nói chung cũng xử lý khá tốt
      Chỉ là không có lối tắt cú pháp; còn ngôn ngữ truy vấn đồ thị về bản chất tập trung vào việc bổ sung các lối tắt đó

  • Công cụ vẽ đồ thị cũng khá đáng thất vọng. Với đồ thị nhỏ thì hoạt động tốt, nhưng khi số nút vượt khoảng 500, kết quả trở nên hoàn toàn không thể hiểu nổi hoặc rất khó xem
    Nó thiếu khả năng tự động sắp xếp đồ thị thành cấu trúc phân cấp và cung cấp một giao diện thuận tiện để khám phá. Nếu nghĩ đến việc chúng ta quen nhìn mọi thứ xung quanh, ở mức độ nào đó, như một cấu trúc phân cấp, thì có lẽ khi xây dựng một kiểu dữ liệu đồ thị dùng chung cũng phải giải quyết cùng loại vấn đề
    Việc này có thể cần được triển khai ở cấp trình biên dịch, để các thuật toán đồ thị dùng chung thích nghi với hệ thống phân cấp cấu trúc được tạo ra. Nếu thêm vào đó một trình chứng minh định lý để xác nhận rằng một đồ thị con nhất định luôn có một cấu trúc nhất định, thì thủ tục tương ứng có thể được tạo tĩnh, còn phần đồ thị cấp cao còn lại có thể được tạo động lúc runtime
    Vì vậy, ai giải được bài toán vẽ đồ thị tổng quát có lẽ cũng sẽ có năng lực hoặc trực giác để triển khai điều này

    • Vẽ đồ thị là việc khó
      Một thư viện vẽ đồ thị tổng quát kiểu Graphviz, cung cấp nhiều tùy chọn và quyền kiểm soát hơn
      https://eclipse.dev/elk/
      Thí nghiệm do nhóm phát triển ELK tại Đại học Kiel thực hiện
      https://github.com/kieler/KLighD
      Wiki của dự án Kieler
      https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
      Thư viện vẽ đồ thị dựa trên ràng buộc
      https://www.adaptagrams.org/
      Bản triển khai JavaScript
      https://ialab.it.monash.edu/webcola/
      Một tài liệu thú vị: HOLA: Human-like Orthogonal Network Layout
      https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
      Demo Confluent Graphs giúp các cạnh dễ đọc hơn
      https://www.aviz.fr/~bbach/confluentgraphs/
      Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
      https://arxiv.org/pdf/1408.4626.pdf
      Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs
      https://arxiv.org/pdf/1311.6996v1.pdf
    • Một số thuật toán xử lý vấn đề này tốt hơn, nhưng trong trường hợp tổng quát, yêu cầu “hãy tạo một sơ đồ tốt cho đồ thị” gần như là một bài toán AI-complete
      Ngay cả với hai đồ thị giống nhau về mặt cấu trúc, hai người vẫn có thể render chúng hoàn toàn khác nhau để nhấn mạnh những khía cạnh dữ liệu khác nhau. Điều này cũng tương tự các vấn đề “thuật toán đồ thị tổng quát” và “cấu trúc dữ liệu đồ thị tổng quát”
      Đồ thị nằm trên ranh giới giữa mã và dữ liệu. Chẳng hạn, bất kỳ chương trình nào cũng có call graph, nên theo một nghĩa nào đó, “thuật toán đồ thị tổng quát” chính là bản thân phép tính toán
    • Những thứ lý tưởng thường trông giống cây, nhưng cấu trúc trong thế giới thực, dù được tổ chức tốt, thường là đồ thị có hướng không chu trình
      Chỉ cần vượt quá vài chục nút, việc làm cho nó phẳng, hoặc giảm số giao cắt và nhóm tốt các nút liên quan để trông gần như phẳng, thường đã khó
    • Tôi cho rằng vấn đề lớn hơn là chúng ta đã quen với ảo tưởng rằng mọi thứ đều có tính phân cấp
      Trên thực tế, việc vẽ đồ thị phải dung hòa những thứ hầu như không hề phân cấp, và rất khó vạch ra một ranh giới toán học chặt chẽ cho việc nên xem đến đâu là phân cấp. Càng đặt ít giả định về cấu trúc đồ thị nền, như tính liên thông, có chu trình hay không, độ thưa, thì vấn đề này càng tệ hơn
      Trong thực tế, khi làm UI để tương tác với đồ thị, thường có thể xác định hoặc áp đặt một, hai tầng meta để phân cụm; nhờ vậy có thể giảm tác động của các nút hairball làm hỏng layout, đồng thời giảm số nút để cải thiện hiệu năng render. Có thể dùng fCOSE cho layout, và cũng có bản triển khai trên Cytoscape.js
    • Nhìn vào hình vẽ mạng nơ-ron sẽ thấy rõ trực quan hóa đồ thị quy mô lớn có thể trở nên hoàn toàn khó hiểu đến mức nào

  • Tôi cho rằng quan sát cốt lõi rằng “có quá nhiều lựa chọn triển khai” không hoàn toàn đúng
    Trên thực tế, một thư viện có thể triển khai mọi cách biểu diễn đồ thị phù hợp, cung cấp thuật toán có hiệu năng tốt nhất cho từng cách biểu diễn, và cung cấp chuyển đổi giữa các cách biểu diễn. Các chuyển đổi này tỷ lệ với số lượng cách biểu diễn, việc triển khai lẫn sử dụng đều đơn giản, nên là gánh nặng khá hợp lý cho cả người bảo trì lẫn người dùng
    Thêm nữa, cũng có thể cung cấp chuyển đổi nhập/xuất từ các kiểu dữ liệu và idiom của thư viện chuẩn. Bộ nhớ và chi phí chuyển đổi đều rẻ, và 99% trường hợp sử dụng có khả năng có thể bỏ qua overhead chuyển đổi dữ liệu ở cả RAM lẫn CPU
    Tôi cũng nhớ đến câu “sự thật khắc nghiệt khi làm việc ở Google rốt cuộc là bạn chỉ đang chuyển protobuf từ chỗ này sang chỗ khác”
    https://news.ycombinator.com/item?id=20132880

    • Làm vậy có vẻ sẽ thành một thư viện khổng lồ, và tôi không chắc trong công việc của mình có dùng không. Tôi dùng đồ thị rất nhiều, nhưng trải nghiệm của tôi giống với những người mà tác giả đã phỏng vấn
      Cuối cùng lúc nào cũng phải tự triển khai lại đồ thị. Hiệu năng là quan trọng, và các thư viện đồ thị có sẵn mà tôi từng thấy không tận dụng được tính quy luật của dataset của chúng tôi. Ví dụ, chúng tôi dùng DAG append-only, trong đó gần như mọi nút chỉ có một cạnh trỏ đến mục được thêm gần nhất, nên bên trong có thể dùng mã hóa độ dài chuỗi chạy
      Tôi cũng chưa thấy thư viện đồ thị tổng quát nào hỗ trợ các truy vấn cần thiết. Đặc biệt phần lớn là hàm diff đồ thị con
      Hơn nữa, triển khai tùy chỉnh không tốn quá nhiều công. Đồ thị dễ triển khai lại hơn B-tree rất nhiều, và một triển khai đơn giản chỉ cần vài chục dòng. Ngay cả thư viện đã tối ưu cao của chúng tôi, gồm cả các thuật toán hỗ trợ, cũng chỉ khoảng vài trăm dòng
      Nếu có cách xuất dữ liệu sang định dạng chuẩn thì tiện, nhưng trong trường hợp sử dụng của chúng tôi, kéo thêm một thư viện vào có vẻ sẽ tạo ra nhiều vấn đề hơn là giải quyết

  • Ứng dụng còn thiếu mà tôi thường nghĩ đến là Excel cho đồ thị
    Giống như Excel cho dữ liệu dạng bảng, nó xử lý dữ liệu ở quy mô vừa đủ để nằm trong RAM, tức là cần máy tính nhưng chưa đến mức cần datacenter; triển khai “đủ tốt” nhiều thuật toán và trực quan hóa; và có thể dùng mà không cần kiến thức lập trình
    Như bài viết nói, rất nhiều vấn đề trong thực tế là vấn đề đồ thị, vậy tại sao chỉ lập trình viên mới có công cụ để giải chúng

    • Tôi có cảm giác bài viết kết luận hơi vội. Rất nhiều vấn đề khác cũng có thể trở nên phức tạp và khó khăn tùy ý nếu thêm yêu cầu
      Dù vậy, vẫn tồn tại các cấu trúc dữ liệu và thư viện chuẩn đủ phù hợp với phần lớn trường hợp sử dụng; nếu có yêu cầu đặc biệt “cay” thì có thể làm giải pháp tùy chỉnh
      Bài viết nói rằng đồ thị thường quá lớn, nhưng nếu hỏi những người thực sự làm việc với thuật toán đồ thị thì họ dễ có trải nghiệm như vậy. Phần lớn lập trình viên và người dùng có lẽ chỉ xử lý các đồ thị thật sự nhỏ
    • Tôi nghĩ chỉ lập trình viên và nhà toán học mới mô hình hóa các vấn đề như thế này thành đồ thị
      Tôi không nghĩ người dùng phổ thông nhìn thấy đồ thị trong các vấn đề ngẫu nhiên ngoài đời. Điều tôi học được khi làm ở các công ty lớn là, nếu đủ cố gắng, mọi thứ đều có thể trở thành bảng tính Excel
    • Không hẳn đúng thứ được yêu cầu, nhưng https://gephi.org/ triển khai nhiều thuật toán trực quan hóa đồ thị
      https://strlen.com/treesheets/ thì gần với Excel cho dữ liệu cây hơn
    • Bài viết không chứng minh thỏa đáng điểm “nhiều vấn đề thực tế là vấn đề đồ thị”
      Ví dụ, có thể mô hình hóa Internet thành đồ thị, nhưng dù điều đó đúng thì vẫn không rõ nó dẫn đến gì. Internet có thể được biểu diễn theo nhiều cách, và không rõ việc biểu diễn bằng đồ thị nhìn chung có hàm ý kỹ thuật hữu ích nào
      Có thể nói, với mức độ thuyết phục tương tự, rằng biểu diễn lý tưởng để thu được thông tin hữu ích lại là một hàm mã hóa ma trận hộp đen ánh xạ input tùy ý thành output nhất quán, tức là mạng nơ-ron
      Ở những nơi như Google, đó có thể là một ý tưởng trị giá hàng chục tỷ đô la, nhưng toàn bộ Internet không phải là vấn đề đồ thị đối với nhiều người, và biểu diễn nó bằng đồ thị không giải quyết được nhiều thứ
      Hiếm có người giải các vấn đề thực tế trên giấy bằng đồ thị. Bảng thì lúc nào cũng được dùng. Đồ thị thì phổ biến, nhưng vấn đề đồ thị thì không
    • Tôi nghĩ điểm cốt lõi ở đây là VR
      Các bình luận khác cũng nói rằng trực quan hóa đồ thị khó, nhưng giao diện 3D cho nhiều không gian hơn rất nhiều. Khi làn sóng VR bắt đầu, tôi đã nghĩ “Excel của VR sẽ là gì?”, và câu trả lời của Microsoft là “bảng tính 2D lơ lửng trong không gian 3D”. Tôi thấy thật vô lý. Tôi nghĩ đó sẽ là đồ thị
      Nếu có ai muốn cùng khám phá, có thể gửi email cho tôi theo dạng tên người dùng của tôi at gmail.com

  • Kiểu đồ thị đã tồn tại từ khá lâu rồi
    Erlang có https://www.erlang.org/doc/man/digraph.html và https://www.erlang.org/doc/man/digraph_utils, và nếu muốn làm các thao tác theo kiểu lý thuyết tập hợp thì cũng có https://www.erlang.org/doc/man/sofs.html

    • Erlang được nhắc ngắn gọn ở phần cuối bài
      Nội dung là: “Tôi tìm thấy hai ngôn ngữ khác có kiểu đồ thị là Erlang và SWI-Prolog. Vì không rành cả hai nên tôi không thể nói chúng được thêm vào khi nào, nhưng Erlang đã có ít nhất từ trước năm 2008. Tôi đã liên hệ với một người trong ủy ban ngôn ngữ lõi Erlang nhưng không nhận được câu trả lời”
    • Elixir cũng có một thư viện đồ thị khá ổn: https://hexdocs.pm/libgraph/api-reference.html
      Tôi từng dùng nó để giải quyết phụ thuộc nhằm xác định thứ tự công việc
    • Tôi tò mò không biết nó linh hoạt và có hiệu năng tốt đến mức nào trong nhiều tình huống khác nhau