Biểu diễn đồ thị, và cái giá của mỗi cách
Biểu diễn đồ thị, và cái giá của mỗi cách
Trước khi chạy bất kỳ thuật toán nào trên đồ thị, bạn phải quyết định cất nó ra sao. Quyết định đó không trung tính: nó ấn định trước cái gì rẻ, cái gì đắt, và cái gì không chạy nổi.
Một đồ thị là một tập đỉnh và một tập cạnh nối chúng. Định nghĩa hết đúng một dòng, và nó không nói gì về việc máy tính phải cất thứ đó thế nào. Chỗ trống ấy mới là bài học: cùng một đồ thị có ít nhất ba cách viết ra, chúng chứa đúng cùng một lượng thông tin, mà chi phí thì chênh nhau tới hàng nghìn lần.
Bài này chỉ nói về chuyện cất giữ. Nó không dạy lại BFS, DFS, đường đi ngắn nhất hay minimax: những thứ đó bạn đã học kỹ ở học phần Trí tuệ nhân tạo, tại tìm kiếm theo bề rộng, tìm kiếm theo chiều sâu và định tuyến sống với Dijkstra. Ở đây ta hỏi câu đứng trước chúng: khi bạn viết for (v : hàng xóm của u) trong một thuật toán duyệt, dòng đó tốn bao nhiêu? Câu trả lời phụ thuộc hoàn toàn vào cách bạn đã cất đồ thị, và nó chênh nhau rất xa.
Ba cách trong sim dưới đây:
- Ma trận kề: một bảng
n × n, ô(u, v)ghi 1 nếu có cạnh. Đơn giản nhất, và tốnn²ô bất kể đồ thị có bao nhiêu cạnh. - Danh sách kề: mỗi đỉnh giữ một danh sách các đỉnh mà nó nối tới. Tốn theo
n + m. - Danh sách cạnh: một mảng các cặp. Gọn nhất về byte, và vô dụng nhất khi phải trả lời một câu hỏi cụ thể.
1 · Một đồ thị, ba cách viết ra ✎ sửa được
| u \ v | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 2 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 3 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 4 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
| 6 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
2 · Ba thao tác, đếm thật ✎ sửa được
| thao tác | ◆ ma trận kề | ● danh sách kề | ▲ danh sách cạnh |
|---|---|---|---|
| hỏi có cạnh 0-3 không | 1 ✓ | 2 | 2 |
| duyệt mọi hàng xóm của đỉnh 0 (bậc 4) | 8 | 4 ✓ | 9 |
| duyệt toàn bộ cạnh | 28 | 26 | 9 ✓ |
3 · Độ thưa: mốc mà ma trận kề bắt đầu tốn ít hơn ✎ sửa được
| số cạnh | ◆ ma trận kề | ● danh sách kề | phán quyết |
|---|---|---|---|
| 223 (một dưới mốc) | 4.00 KiB | 3.98 KiB | ● danh sách kề rẻ hơn |
| 224 (đúng mốc) | 4.00 KiB | 4.00 KiB | = hai bên bằng nhau khít |
| 225 (một trên mốc) | 4.00 KiB | 4.02 KiB | ◆ ma trận kề rẻ hơn |
4 · Nửa ma trận bị lặp
Ma trận vô hướng đối xứng, nên nửa dưới đường chéo chỉ lặp lại nửa trên. Ở 64 đỉnh, ma trận vuông có 4.096 ô còn tam giác trên chỉ cần 2.080 ô, tức tiết kiệm 2.016 ô, đúng bằng n(n-1)/2, tương ứng 1.97 KiB và 49.2%.
Chú ý phần tiết kiệm chưa bao giờ đủ một nửa: nó bằng (n-1)/(2n), tiệm cận 50% mà không chạm, vì đường chéo không hề bị lặp nên không có gì để bỏ ở đó. Giữ lại đường chéo là một quy ước của sim này, để một khuyên vẫn còn chỗ mà lưu; bỏ hẳn đường chéo thì tiết kiệm thêm 64 ô nữa nhưng đồ thị mất khả năng biểu diễn khuyên.
Cái giá của thủ thuật này không nằm ở bộ nhớ mà ở chỗ khác: mỗi lần đọc ô (u, v) bạn phải nhớ đổi chỗ u và v khi u lớn hơn v, và phải tính chỉ số vào một mảng một chiều. Sim không đếm chi phí đó, và bạn nên biết là nó có.
5 · Quy mô thật: một mạng xã hội ✎ sửa được
- Nó đếm ô, đếm mục, đếm byte, đếm bước. Nó không đo giây. Một cấu trúc ít bước hơn vẫn có thể chậm hơn trên máy thật, vì bộ nhớ đệm thưởng cho việc đọc liên tiếp và phạt việc nhảy lung tung, mà danh sách liên kết thì nhảy rất nhiều.
- Bốn con số byte là mô hình đơn giản hoá. Một cài đặt thật còn có phần đầu của mỗi khối cấp phát, còn căn lề, còn phần dư của mảng động. Byte thật thường nhiều hơn con số ở đây, và nhiều hơn không đều nhau giữa ba cách.
- Đồ thị ở mục 1 được sinh bằng bộ sinh có hạt giống, nên nó tất định: cùng hạt giống thì cùng đồ thị, lần nào cũng vậy. Nhưng nó là đồ thị ngẫu nhiên đều, còn đồ thị thật ngoài đời thì không: mạng xã hội có vài đỉnh bậc rất lớn, và điều đó ảnh hưởng tới chi phí thật mà sim không mô hình hoá.
- Bài này không dạy thuật toán duyệt. Chi phí của BFS, DFS hay đường đi ngắn nhất phụ thuộc vào cách biểu diễn bạn chọn ở đây, nhưng bản thân các thuật toán đó là nội dung của học phần Trí tuệ nhân tạo, và sim này không chạy chúng.
Ba cách, cùng một đồ thị
Ở trạng thái mở bài, sim dựng một đồ thị vô hướng 8 đỉnh với 9 cạnh, sinh từ hạt giống 7. Chín cạnh đó là 0-1, 0-3, 0-4, 0-6, 1-6, 2-3, 4-5, 5-6, 6-7, và dãy bậc là 4 2 1 2 2 2 4 1, cộng lại bằng 18, đúng hai lần số cạnh. Đồ thị này không phải thứ tôi bịa ra rồi dán vào bài: nó là đầu ra của một bộ sinh có hạt giống viết ngay trong phần tính, và hạt giống là núm bạn sửa được. Đổi 7 thành 8 thì cả ba bảng đổi theo, đổi ngược về 7 thì mọi con số quay lại y nguyên.
Nhìn ba khung cạnh nhau và để ý một chuyện: chúng nói cùng một điều. Cổng kiểm số của bài canh đúng chỗ đó, bằng cách quy cả ba về một tập cặp rồi so, trên 224 đồ thị dựng thật. Nếu ba khung có lúc nào bất đồng thì cổng đỏ.
Về byte, ở cỡ này ma trận đang thắng: 64 byte so với 208 byte của danh sách kề và 72 byte của danh sách cạnh. Đừng vội rút ra kết luận gì từ đó. Với 8 đỉnh, riêng 8 con trỏ đầu danh sách đã tốn 8 × 8 = 64 byte, tức đúng bằng cả ma trận. Đây là cỡ mà mọi cách đều rẻ và mọi lựa chọn đều không quan trọng.
Ba thao tác, và ai trả tiền cho cái gì
Mục 2 của sim là chỗ tôi muốn bạn ngồi lâu. Ba con số ở đó là số bước đã đếm được khi phần tính đi bộ qua từng cấu trúc và cộng một mỗi lần chạm vào một ô, một mục hay một bản ghi. Không con số nào đến từ việc thay số vào công thức.
Ở trạng thái mở bài, với u = 0 và v = 3:
- Hỏi có cạnh
0-3không. Ma trận đọc đúng 1 ô. Danh sách kề đọc 2 mục, vìadj[0] = 1, 3, 4, 6và số 3 nằm ở vị trí thứ hai. Danh sách cạnh đọc 2 bản ghi. Ba con số gần nhau, và điều đó chỉ vì đồ thị bé. - Duyệt mọi hàng xóm của đỉnh 0. Ma trận đọc 8 ô, tức cả hàng. Danh sách kề đọc 4, đúng bằng bậc. Danh sách cạnh phải quét cả 9 cạnh, vì không có gì gom các cạnh của cùng một đỉnh lại.
- Duyệt toàn bộ cạnh. Ma trận quét tam giác trên, 28 ô. Danh sách kề đọc 8 đầu cộng 18 mục, tổng 26. Danh sách cạnh đọc đúng 9.
Hãy đổi u sang đỉnh 2, đỉnh chỉ có một hàng xóm. Danh sách kề tụt xuống 1 bước. Ma trận vẫn đọc 8 ô, không rẻ hơn một chút nào. Đó là điểm cốt lõi: chi phí duyệt hàng xóm bằng ma trận bằng n ở mọi đỉnh, không quan tâm đỉnh đó thưa hay dày. Trên đồ thị 8 đỉnh thì lãng phí 4 ô. Trên mạng xã hội một triệu người, nó là lãng phí 999.900 ô cho một người có 100 bạn, và đó là mỗi lần bạn hỏi về một người.
Còn chuyện ngược lại cũng đúng và cũng phải nói: hỏi có cạnh giữa hai đỉnh không thì ma trận đọc đúng 1 ô kể cả trên đồ thị 14 đỉnh đầy đủ, trong khi danh sách kề có thể phải đi hết một danh sách dài. Đó chính là thứ ma trận bán, và nó bán thật.
Điểm chính: độ thưa là một con số, không phải một cảm giác
Chữ thưa bị dùng rất lỏng lẻo. Người ta nói "đồ thị này thưa nên dùng danh sách kề", và dừng ở đó. Hỏi lại một câu là mọi thứ sụp: thưa tới mức nào? Câu trả lời tính được, và nó là điểm dạy học chính của bài.
Hoá đơn của ma trận phẳng: n² ô nhân số byte mỗi ô, không đổi khi thêm cạnh. Hoá đơn của danh sách kề là một đường thẳng theo m: n đầu danh sách, cộng mỗi cạnh thêm một mục nếu có hướng hoặc hai mục nếu vô hướng. Một đường phẳng và một đường dốc lên thì cắt nhau đúng một chỗ, và chỗ đó là
m* = trần của (n² × byte_ô − n × byte_đầu) / (k × byte_mục)
với k = 1 cho đồ thị có hướng và k = 2 cho vô hướng.
Ở trạng thái mở bài, quy mô kế toán là 64 đỉnh, 1 byte mỗi ô, 8 byte mỗi đầu danh sách, 8 byte mỗi mục. Thay số: ma trận tốn 64 × 64 × 1 = 4096 byte; đầu danh sách tốn 64 × 8 = 512 byte; mỗi cạnh vô hướng thêm 2 × 8 = 16 byte. Vậy (4096 − 512) / 16 = 3584 / 16 = 224 khít, không phải làm tròn. Mốc là 224 cạnh, tức 11,1% của đồ thị đầy đủ 2016 cạnh.
Sim đặt sẵn số cạnh đúng bằng 224, nên bảng ở mục 3 đang cho thấy hai bên hoà nhau khít ở 4096 byte. Kéo xuống 223 thì danh sách kề tốn 4080 byte và thắng. Kéo lên 225 thì nó tốn 4112 byte và thua. Ba dòng trong bảng nằm đó chính vì chuyện này: một mốc mà chỉ khẳng định "có tồn tại" thì không phân biệt được 224 với 223, và cái lệch một đơn vị ấy là toàn bộ nội dung của mục này. Cổng kiểm số của bài khoá cả ba vị trí, trên 288 cấu hình byte, hướng và cách xếp ma trận.
Mốc đó không phải hằng số của vũ trụ, nó là hệ quả của những con số bạn vừa chọn. Kéo núm byte mỗi ô mà xem:
| byte mỗi ô ma trận | mốc (ở 64 đỉnh) | mật độ |
|---|---|---|
| 1 (mặc định) | 224 cạnh | 11,1% |
| 2 | 480 cạnh | 23,8% |
| 4 | 992 cạnh | 49,2% |
| 8 | 2016 cạnh | 100,0% |
Dòng cuối đáng dừng lại. Ở 8 byte mỗi ô, mốc rơi đúng vào đồ thị đầy đủ: ma trận chỉ hoà đúng ở lúc mọi đỉnh nối với mọi đỉnh, và không bao giờ thắng thật. Chỉnh thêm một chút nữa, giữ 8 byte mỗi ô nhưng hạ đầu danh sách xuống 4 byte, thì mốc thành 2032 cạnh, tức vượt ra ngoài đồ thị đầy đủ, và lúc đó ma trận không bao giờ rẻ hơn danh sách kề dù bạn nhồi cạnh tới đâu. Sim nói thẳng câu đó chứ không in ra một con số mốc mà bạn không bao giờ với tới được.
Đi theo hướng ngược lại cũng có một mốc đáng nhớ. Ở 8 đỉnh với 8 byte mỗi đầu danh sách, mốc là 0: ma trận thắng từ đồ thị rỗng trở đi, vì riêng phần đầu danh sách đã đắt bằng cả ma trận. Nói cách khác, với đồ thị đủ nhỏ thì cãi nhau về biểu diễn là vô ích.
Đồ thị vô hướng lãng phí đúng một nửa, gần như thế
Ma trận của đồ thị vô hướng đối xứng: ô (u, v) và ô (v, u) luôn ghi cùng một thứ. Trong sim, nửa dưới đường chéo được tô sọc để bạn thấy phần lặp đó. Bật núm ở mục 4 và sim chỉ giữ tam giác trên: ở 64 đỉnh, 4096 ô rút xuống 2080 ô, tiết kiệm 2016 ô, đúng bằng n(n-1)/2, tức 49,2%.
Chú ý con số đó chưa bao giờ đủ một nửa. Phần tiết kiệm bằng (n-1)/(2n), tiệm cận 50% mà không chạm tới, vì đường chéo không hề bị lặp nên không có gì để bỏ ở đó. Ở 1000 đỉnh nó là 49,95%, vẫn dưới, dù ô hiển thị làm tròn một chữ số nên bạn sẽ đọc thấy 50,0%. Đây là loại chi tiết mà một câu nói suông kiểu "tiết kiệm một nửa" sẽ nuốt mất.
Hai điều phải nói rõ. Thứ nhất, việc giữ lại đường chéo là một quy ước của sim, để một khuyên còn chỗ mà lưu; bỏ hẳn đường chéo thì tiết kiệm thêm n ô nữa nhưng mất khả năng biểu diễn khuyên. Thứ hai, thủ thuật này không miễn phí: mỗi lần đọc ô (u, v) bạn phải nhớ đổi chỗ u và v khi u lớn hơn v, rồi tính chỉ số vào một mảng một chiều. Sim không đếm chi phí đó, và bạn nên biết là nó có.
Bấm sang có hướng thì núm tam giác biến mất, vì ma trận có hướng không đối xứng: ô (u, v) nói về cung đi từ u sang v, còn (v, u) nói về cung ngược lại, và đó là hai chuyện khác nhau. Một núm hiện ra mà không đổi được con số nào là một lời nói dối, nên nó được giấu đi thay vì để đó cho đẹp.
Con số làm mọi lý luận về hằng số trở nên thừa
Tới đây bạn có thể vẫn nghĩ đây là chuyện tiết kiệm vài phần trăm. Mục 5 tồn tại để dập cái ý đó.
Một mạng xã hội 1 triệu người, mỗi người 100 bạn. Vô hướng, nên đó là 50 triệu cạnh và 100 triệu mục danh sách kề. Ma trận kề cần 10⁶ × 10⁶ = 10¹² ô, tức một nghìn tỉ ô.
| cách cất | kích cỡ | byte |
|---|---|---|
| ma trận kề, 1 byte mỗi ô | 10¹² ô | 931,3 GiB |
| cùng ma trận đó, nén 1 bit mỗi ô | 10¹² bit | 116,4 GiB |
| danh sách kề | 10⁸ mục | 770,6 MiB |
| danh sách cạnh | 5 × 10⁷ bản ghi | 381,5 MiB |
Ma trận tốn gấp 1.238 lần danh sách kề. Nhưng con số tỉ lệ vẫn còn nói nhẹ quá. Điều đáng nói là 931,3 GiB không phải là "chậm hơn", nó là không có máy nào của bạn chứa nổi. Và nếu bạn định cãi rằng chỉ cần một bit mỗi ô là đủ vì ô chỉ có 0 hoặc 1, thì hàng thứ hai trả lời: nén hết cỡ vẫn còn 116,4 GiB bộ nhớ liền mạch. Trong khi đó danh sách kề nằm gọn trong 770,6 MiB và chạy được trên chiếc máy bạn đang ngồi.
Đây là chỗ ký hiệu O cuối cùng cũng có ích, và bạn nên đọc kèm bài các bậc tăng. Ma trận là O(n²) bộ nhớ, danh sách là O(n + m). Ở 8 đỉnh thì hai bậc đó không phân biệt được. Ở 10.000 người tỉ lệ mới là 12 lần, ở 100.000 người là 124 lần, ở 1 triệu người là 1.238 lần. Tỉ lệ lớn lên theo n, và đó mới là lập luận, chứ không phải con số 1.238 đứng một mình.
Ngược lại, cũng phải công bằng với ma trận. Nếu đồ thị của bạn dày, ví dụ một ma trận khoảng cách giữa 200 thành phố mà thành phố nào cũng nối thành phố nào, thì n² ô là đúng cái bạn cần và không hề lãng phí gì, mà đổi lại bạn tra một khoảng cách bất kỳ trong một bước. Sim cho phép bạn tự tới trạng thái đó bằng cách kéo số cạnh lên đồ thị đầy đủ.
Danh sách kề trong bộ nhớ trông ra sao
Trong sim, một danh sách kề vẽ ra thành đỉnh → các hàng xóm. Trong bộ nhớ thật nó có ít nhất hai cách cài, và chúng khác nhau đáng kể:
- Mảng các danh sách liên kết: mỗi mục là một nút có trường đỉnh và một con trỏ sang nút kế. Đây là lý do sim tính 8 byte mỗi mục thay vì 4. Cách này thêm cạnh rất rẻ nhưng duyệt thì nhảy khắp bộ nhớ, và bạn đã gặp cái giá đó ở bài danh sách liên kết.
- Mảng các mảng động: mỗi đỉnh giữ một vector các đỉnh kề. Duyệt liên tiếp nên nhanh hơn hẳn trên máy thật, đổi lại thỉnh thoảng phải cấp phát lại và chép, đúng như bài mảng động đã đếm.
Sim này không phân biệt hai cách đó: nó chỉ có một núm byte mỗi mục, và bạn tự đặt con số phản ánh cách cài của mình. Nói thẳng ra như vậy còn hơn để bạn tưởng con số 770,6 MiB kia là một phép đo trên một cài đặt cụ thể.
Đếm ô không phải đo giây
Chỗ này phải nói thẳng, vì đây là hiểu nhầm dễ mắc nhất sau một bài như bài này.
- Sim đếm ô, mục, byte và bước. Nó không đo giây. Bộ nhớ đệm của máy quyết định phần lớn thời gian thật, và nó thưởng cho việc đọc liên tiếp, phạt việc nhảy lung tung. Rất thường xuyên, cấu trúc ít bước hơn lại chậm hơn khi bấm đồng hồ.
- Bốn con số byte là mô hình đơn giản hoá. Một cài đặt thật còn phần đầu của mỗi khối cấp phát, còn căn lề, còn phần dư của mảng động. Byte thật thường nhiều hơn, và nhiều hơn không đều nhau giữa ba cách.
- Đồ thị ngẫu nhiên đều không giống đồ thị ngoài đời. Mạng xã hội thật có vài đỉnh bậc cực lớn và rất nhiều đỉnh bậc nhỏ. Con số "mỗi người 100 bạn" ở mục 5 là một mức trung bình đặt ra để thấy quy mô, không phải một phép đo trên mạng xã hội nào cả.
- Bài này không chạy thuật toán duyệt nào. Chi phí của BFS, DFS hay Dijkstra phụ thuộc vào cách biểu diễn bạn chọn ở đây, nhưng bản thân chúng là nội dung của học phần Trí tuệ nhân tạo và sim không cài chúng. Nếu bạn muốn thấy chúng chạy, hãy sang BFS, DFS và Dijkstra trên mạng sống.
Vậy đếm để làm gì? Để bạn có một con số kiểm chứng được thay cho một cảm giác. Nó cho biết mốc nằm ở 224 chứ không phải "đâu đó khoảng một phần mười", cho biết phần tiết kiệm của tam giác trên là 49,2% chứ không phải "một nửa", và cho biết 931,3 GiB là con số khiến lựa chọn kia không còn là lựa chọn. Không cảm giác nào cho bạn những thứ đó.
Ba cách biểu diễn chứa đúng cùng một thông tin và chênh nhau ở chỗ cái gì rẻ. Ma trận kề trả n² ô bất kể có bao nhiêu cạnh, đổi lại hỏi một cạnh chỉ mất 1 bước; danh sách kề trả theo n + m và duyệt hàng xóm đúng bằng bậc; danh sách cạnh gọn nhất về byte nhưng mọi câu hỏi cụ thể đều phải quét cả m. Độ thưa không phải cảm giác mà là một con số: với 64 đỉnh, 1 byte mỗi ô và 8 byte mỗi mục, mốc nằm đúng ở 224 cạnh, một cạnh dưới thì danh sách thắng, một cạnh trên thì ma trận thắng, và mốc đó chạy đi khi bạn đổi số byte. Ở quy mô thật thì chuyện không còn là nhanh chậm: 1 triệu người với 100 bạn cần 10¹² ô ma trận, tức 931,3 GiB, hay 116,4 GiB nếu nén xuống 1 bit, trong khi danh sách kề chỉ cần 770,6 MiB. Đó là ranh giới giữa chạy được và không chạy được.
- 1Một đồ thị vô hướng có 64 đỉnh và 224 cạnh. Với 1 byte mỗi ô ma trận, 8 byte mỗi đầu danh sách và 8 byte mỗi mục, cách nào tốn ít bộ nhớ hơn giữa ma trận kề và danh sách kề?
- 2Đỉnh u trong một đồ thị 1000 đỉnh chỉ có 3 hàng xóm. Bạn cần duyệt hết hàng xóm của u. Chi phí trên ma trận kề là bao nhiêu, và vì sao?
- 3Có người nói: mạng xã hội 1 triệu người mỗi người 100 bạn thì ma trận kề chỉ chậm hơn danh sách kề khoảng một nghìn lần thôi, chịu khó chờ là được. Sai ở đâu?