Danh sách liên kết so với mảng
Danh sách liên kết so với mảng
Cùng một thao tác, hai cấu trúc, và một bảng đếm từng bước. Ai thắng ở đâu, thua ở đâu, và câu 'chèn vào giữa là O(1)' đúng trong điều kiện nào.
Hai cấu trúc này hay được dạy cạnh nhau, rồi được tóm tắt bằng một câu mà ai cũng thuộc: mảng truy cập nhanh, danh sách liên kết chèn xoá nhanh. Câu đó đúng, nhưng nó bỏ mất phần quan trọng nhất là bao nhiêu, và ở chỗ nào. Chèn vào đâu? Xoá phần tử thứ mấy? Bạn đã cầm sẵn con trỏ tới chỗ đó chưa?
Sim dưới đây không tóm tắt gì cả. Nó đặt cùng một thao tác lên cả hai cấu trúc rồi đếm: bao nhiêu lần đi theo một liên kết, bao nhiêu phần tử phải dời chỗ, bao nhiêu ô nhớ bị đọc, bao nhiêu ô nhớ bị ghi. Mọi tham số đều sửa được, kể cả những tham số làm đảo ngược kết luận.
1 · Cấu hình ✎ sửa được
k đếm từ 0. Với 1.000 phần tử thì chỉ số hợp lệ chạy từ 0 tới 999, còn vị trí chèn chạy tới 1.000 vì chèn vào ngay sau phần tử cuối là hợp lệ. Đặt k ra ngoài dải thì sim báo ra chứ không kéo về, và k vẫn giữ nguyên giá trị bạn đặt.2 · Sáu thao tác, đếm từng bước
| thao tác | mảng | danh sách liên kết, phải đi tìm | danh sách liên kết, đã có con trỏ | ai rẻ hơn, hơn bao nhiêu |
|---|---|---|---|---|
| chèn vào đầu (k = 0) | 1.001 | 2 | 2 | ▼ danh sách liên kết rẻ hơn, 500,50 lần |
| chèn vào cuối (k = 1.000) | 1 | 1.001 | 2 | ▲ mảng rẻ hơn, 1.001,00 lần |
| chèn vào giữa, tại vị trí k (k = 500) | 501 | 501 | 2 | = hoà, cùng 501 bước |
| xoá phần tử thứ k (k = 500) | 500 | 502 | 501 | ▲ mảng rẻ hơn, chênh 2 bước |
| truy cập phần tử thứ k (k = 500) | 1 | 501 | 1 | ▲ mảng rẻ hơn, 501,00 lần |
| tìm một giá trị | 501 | 1.001 | không có nghĩa | ▲ mảng rẻ hơn, 2,00 lần |
3 · Cái bẫy: “chèn giữa là O(1)”
O(n).4 · Điểm hoà vốn giữa hai loại thao tác
5 · Bộ nhớ: cái giá của mỗi con trỏ
Đổi một chiều thành hai chiều ở thanh trên: mỗi nút thêm một con trỏ nữa, từ 12 byte lên 20 byte. Đó là cùng một cái giá mua về việc xoá rẻ hơn ở mục 3 và việc đi được từ hai đầu ở mục 2. Cả hai vế đều là số, và bạn đọc được cả hai cùng lúc.
- Nó đếm bước, không đo giây. Trong máy thật, mảng nằm liền một khối nên bộ nhớ đệm nạp cả một dòng là có sẵn nhiều phần tử, còn các nút của danh sách liên kết nằm rải rác ở đâu tuỳ bộ cấp phát, nên mỗi lần nhảy có thể là một lần chờ bộ nhớ. Vì vậy mảng thường nhanh hơn cả ở những chỗ phép đếm này nói nó thua. Đây là một trong những chỗ lý thuyết và thực tế lệch nhau nhiều nhất, và sim không đo được nó.
- Nó bỏ qua chi phí nới mảng. Cột “chèn cuối” của mảng giả định còn chỗ trống. Cái giá của việc hết chỗ đã tính ở bài mảng động và nó là một hằng số khi chia đều, nên nó không đổi kết luận nào ở đây, nhưng nó không phải bằng không.
- Nó bỏ qua chi phí cấp phát một nút. Mỗi lần chèn vào danh sách liên kết là một lần xin bộ nhớ, và việc đó tốn hơn hẳn vài phép ghi. Núm “byte phụ trội mỗi nút” chỉ mô hình hoá phần chỗ nhớ mà bộ cấp phát ăn thêm, không mô hình hoá thời gian nó bỏ ra.
- Nó không đếm vài byte hằng số mà cả hai bên đều phải giữ: biến kích thước của mảng, biến con trỏ đầu và con trỏ cuối của danh sách. Chúng không lớn theo
nnên bỏ ra ngoài để tỉ lệ khỏi bị lệch, chứ không phải vì chúng bằng không. - Nó dùng tìm tuần tự cho cả hai bên. Nếu dãy đã sắp xếp thì mảng còn tìm nhị phân được, còn danh sách liên kết thì không, vì tìm nhị phân cần nhảy thẳng tới giữa. Đó là một lợi thế nữa của mảng mà bảng này không hề tính tới.
Quy ước đếm, nói trước cho rõ
Trước khi đọc con số nào, phải thống nhất đang đếm cái gì:
- đi qua một liên kết
nexthoặcprev: tính 1. Biếnheadđã trỏ sẵn vào nút đầu, nên đứng ở nút số 0 tốn 0 bước, và tới nút thứjtốn đúngjbước. - dời một phần tử sang ô bên cạnh: tính 1.
- đọc một ô nhớ để nhìn giá trị: tính 1.
- ghi một ô nhớ, dù đó là một phần tử, một trường
next, hay chính biếnhead: tính 1.
Một hệ quả nhỏ nhưng rất quan trọng: đi qua một nút của danh sách liên kết tốn hai lần chạm bộ nhớ, một lần cho con trỏ next và một lần cho giá trị. Đó không phải là bàn tay đặt lên cán cân, đó đúng là việc máy phải làm. Còn mảng thì tính địa chỉ bằng base + k × kích thước, tức là một phép số học chứ không phải một lần đọc, nên truy cập phần tử thứ k của mảng tốn đúng 1 ô nhớ đọc, dù k bằng bao nhiêu.
Cách đếm này bạn đã gặp ở bài đếm phép tính, và cái giá của nó vẫn là cái giá cũ: nó không nói gì về nanô giây. Cuối bài sẽ quay lại chỗ đó, vì đây đúng là nơi lý thuyết và thực tế lệch nhau nhiều nhất trong cả môn.
Bảng ở trạng thái mở bài
1.000 phần tử, vị trí k bằng 500, danh sách một chiều, không giữ con trỏ tới nút cuối. Sáu thao tác, cặp số là mảng / danh sách phải đi tìm chỗ:
| thao tác | mảng | danh sách | ai thắng |
|---|---|---|---|
| chèn đầu | 1.001 | 2 | danh sách, 500,50 lần |
| chèn cuối | 1 | 1.001 | mảng, 1.001,00 lần |
| chèn giữa, k = 500 | 501 | 501 | hoà |
| xoá phần tử thứ 500 | 500 | 502 | mảng, chênh 2 bước |
| truy cập phần tử thứ 500 | 1 | 501 | mảng, 501,00 lần |
| tìm giá trị nằm ở vị trí 500 | 501 | 1.001 | mảng, 2,00 lần |
Ba chỗ đáng dừng lại.
Chèn đầu là chỗ danh sách liên kết thắng sạch sẽ. Mảng phải dời cả 1.000 phần tử sang phải rồi mới ghi được phần tử mới, thành 1.001 phép. Danh sách chỉ ghi hai con trỏ: trường next của nút mới, và biến head. Hai. Xoá đầu cũng vậy, đặt k về 0 rồi nhìn hàng xoá: 1.000 so với 2.
Chèn cuối thì ngược hẳn lại, và ngược mạnh hơn nhiều người nghĩ. Mảng ghi vào ô trống kế tiếp, tốn 1. Danh sách một chiều không biết nút cuối nằm đâu nên phải đi hết 999 liên kết, thành 1.001. Đây là lý do gần như mọi cài đặt thật đều giữ thêm một con trỏ tới nút cuối. Bấm nút có giữ ở thanh trên: con số 1.001 tụt xuống 3.
Chèn giữa hoà nhau đúng bằng nhau, 501 so với 501. Không phải trùng hợp có sắp đặt: mảng phải dời n - k phần tử rồi ghi 1, còn danh sách phải đi k - 1 bước rồi ghi 2 con trỏ. Hai biểu thức đó gặp nhau đâu đó quanh giữa dãy, và với n bằng 1.000 thì điểm gặp rơi đúng vào k = 500: từ vị trí 500 trở đi mảng rẻ hơn hoặc bằng, còn ở vị trí 499 thì danh sách vẫn còn rẻ hơn. Kéo núm k qua lại quanh 500 để thấy chỗ lật.
Cái bẫy: chèn vào giữa là O(1)
Đây là câu bị nói sai nhiều nhất về danh sách liên kết, và sim in ra cả hai cột chính là để bóc nó.
Ở cấu hình mở bài, chèn vào vị trí 500 tốn 2 bước nếu ai đó đã trao cho bạn con trỏ tới đúng chỗ, và 501 bước nếu bạn phải tự đi tìm chỗ đó. Chênh nhau 250,50 lần. Câu "chèn vào giữa danh sách liên kết là O(1)" chỉ nói về cột thứ nhất. Nếu tất cả những gì bạn biết là "chèn vào vị trí thứ 500" thì bạn phải đi qua 499 liên kết trước đã, và tổng vẫn là O(n).
Chỗ còn khó chịu hơn nữa là xoá. Với danh sách một chiều, cầm sẵn con trỏ tới nút cần xoá tốn 501 bước, còn phải đi tìm tốn 502 bước. Tiết kiệm được đúng một bước. Lý do rất đơn giản và rất khó chịu: để tháo một nút ra khỏi chuỗi, bạn cần nút đứng trước nó, mà danh sách một chiều không có đường đi ngược, nên bạn vẫn phải đi lại từ đầu. Cầm con trỏ trong tay gần như vô dụng.
Bật hai chiều ở thanh trên rồi nhìn lại con số đó: 501 tụt xuống 3. Đó chính là thứ mà liên kết ngược mua về.
Một chi tiết nữa cùng họ, vì nó cũng hay bị nói gộp: con trỏ tới nút cuối một mình không rút ngắn được đường đi nào. Nó cho bạn nhảy thẳng tới nút cuối, nhưng từ đó bạn không đi ngược được, nên xoá phần tử cuối của một danh sách một chiều vẫn tốn 999 bước đi bộ y như cũ: 1.001 khi không giữ con trỏ cuối, và 1.002 khi có giữ, vì lúc đó còn phải ghi lại chính biến con trỏ cuối. Giữ con trỏ cuối làm con số nhích lên chứ không giảm. Phải hai chiều cộng với con trỏ cuối thì mới đi được từ đầu gần hơn: lúc đó truy cập nút 500 tốn 500 thay vì 501, và truy cập nút 999 chỉ tốn 1.
Điểm hoà vốn: bao nhiêu phần trăm thì mảng thắng
Không thao tác nào tồn tại một mình. Cái quyết định là tỉ lệ. Mục 4 của sim trộn hai loại thao tác theo tỉ lệ bạn đặt rồi tính tổng số bước cho mỗi 100 thao tác, bằng số nguyên, nên một kết quả hoà là hoà thật chứ không phải do làm tròn.
Mặc định trộn truy cập theo chỉ số với chèn đầu, tức đúng hai chỗ mà mỗi bên thắng tuyệt đối. Ở tỉ lệ 50 trên 50, trung bình mỗi thao tác mảng tốn 501,00 bước còn danh sách tốn 251,50 bước: danh sách đang thắng gấp đôi.
Kéo núm tỉ lệ lên. Điểm lật nằm ở đây:
| tỉ lệ truy cập | mảng, mỗi 100 thao tác | danh sách | ai rẻ hơn |
|---|---|---|---|
| 0% | 100.100 | 200 | danh sách |
| 50% | 50.100 | 25.150 | danh sách |
| 66% | 34.100 | 33.134 | danh sách |
| 67% | 33.100 | 33.633 | mảng |
| 100% | 100 | 50.100 | mảng |
67% là mốc, và nó được khoá cả hai phía: ở 66% danh sách vẫn còn rẻ hơn, ở 67% mảng đã rẻ hơn. Điểm cắt chính xác nằm ở 66,64%, tức 99900/1499, và 67 là số nguyên đầu tiên vượt qua nó.
Nói bằng lời: phải từ 67% số thao tác trở lên là truy cập theo chỉ số thì mảng mới rẻ hơn, trong khi phần còn lại là chèn đầu, tức là chỗ mảng thua đậm nhất. Ngưỡng đó cao hơn nhiều so với trực giác thông thường kiểu "truy cập nhanh hơn thì dùng mảng". Lý do nằm ở độ lớn chứ không ở số lượng: mỗi lần truy cập mảng chỉ tiết kiệm được 500 bước, còn mỗi lần chèn đầu nó thua tới 999 bước, gần gấp đôi.
Hai mốc biên quanh chỗ này đáng nhìn kỹ, vì chúng cho thấy ngưỡng không phải là hằng số:
- Đặt
kbằng 0 thì không có điểm hoà vốn nào. Truy cập phần tử đầu tiên thì danh sách cũng chỉ tốn 1 bước, đúng bằng mảng, nên mảng không thắng ở tỉ lệ nào cả. Hai đường có chạm nhau ở đúng 100%, nhưng chạm là hoà chứ không phải thắng, và sim nói đúng như vậy. - Đặt
kbằng 1 thì mốc nhảy lên 100%, với điểm cắt chính xác 99,9%. Một bước lệch củakđã đổi kết luận từ "không bao giờ" sang "đúng ở 100%".
Còn khi cặp thao tác đúng với thứ danh sách liên kết sinh ra để làm thì mảng gần như không có cửa. Bấm preset hàng đợi: vào cuối, ra đầu: chèn cuối 1 so với 3, xoá đầu 1.000 so với 2, và ở tỉ lệ 50 trên 50 thì tổng là 50.050 so với 250, tức danh sách rẻ hơn 200,20 lần. Mảng chỉ thắng ở đúng 100%, tức khi không còn thao tác xoá nào nữa.
Một cái công tắc nữa ở mục 4 đáng thử: đổi cách tính cho danh sách sang đã có sẵn con trỏ. Lúc đó mảng không còn thắng ở tỉ lệ nào cả, kể cả 100% truy cập, vì giả định "đã có con trỏ" áp cho mọi thao tác nghĩa là cả truy cập cũng chỉ tốn 1. Đó là một giả định rất mạnh, và nó là cách nhanh nhất để một bảng so sánh nói dối mà trông vẫn có vẻ nghiêm túc.
Bộ nhớ: mỗi nút phải trả thêm một con trỏ
Mảng chỉ chứa phần tử. Mỗi nút của danh sách liên kết phải chứa thêm ít nhất một con trỏ. Trên máy 64 bit thì một con trỏ là 8 byte, còn một số nguyên int là 4 byte, nên:
- mảng 1.000 số nguyên: 1.000 × 4 = 4.000 byte
- danh sách một chiều: mỗi nút 4 + 8 = 12 byte, tổng 12.000 byte, tức gấp 3 lần, phí tổn 200,0%
- danh sách hai chiều: mỗi nút 4 + 16 = 20 byte, tổng 20.000 byte, tức gấp 5 lần, phí tổn 400,0%
Đây chính là vế còn lại của cái đánh đổi ở mục 3. Liên kết ngược làm xoá rẻ đi từ 501 xuống 3 bước, và cái giá là mỗi nút phồng thêm 8 byte. Cả hai vế đều là số, và sim cho bạn đọc cả hai cùng lúc chứ không cho bạn nhìn một vế rồi kết luận.
Tỉ lệ đó không phụ thuộc n, nên nói "gấp 3 lần" là nói về mọi cỡ dữ liệu. Nhưng nó phụ thuộc rất mạnh vào kích thước phần tử, và đây là chỗ câu "gấp 3 lần" hay bị mang đi dùng sai. Đặt số byte mỗi phần tử lên 64: tỉ lệ tụt xuống còn 1,125 lần, tức phí tổn chỉ 12,5%. Con trỏ loãng đi giữa một phần tử to. Ngược lại, đặt byte phụ trội mỗi nút lên 16 để mô hình hoá phần đầu mục mà bộ cấp phát gắn vào từng mảnh nhớ: tỉ lệ vọt lên gấp 7 lần. Bộ cấp phát thật gần như luôn ăn thêm một ít cho mỗi lần cấp phát, nên con số 12 byte một nút là chặn dưới chứ không phải số thật.
Ô thứ tư ở mục 5 là một phép chia, và bài nói thẳng rằng nó chỉ là một phép chia: một dòng bộ nhớ đệm 64 byte chứa 16 phần tử 4 byte của mảng, và chứa được 5 nút 12 byte nếu chúng tình cờ nằm cạnh nhau. Chữ "nếu" đó là toàn bộ vấn đề của mục tiếp theo.
Chỗ phép đếm này nói không đủ
Sim đếm bước. Nó không đo giây. Và ở đúng bài này, khoảng cách giữa hai chuyện đó lớn hơn hầu hết mọi chỗ khác trong môn.
Mảng nằm liền một khối trong bộ nhớ. Khi bộ xử lý cần một phần tử, nó không nạp một ô mà nạp cả một dòng, thường là 64 byte, nên 15 phần tử kế tiếp đã nằm sẵn trong bộ đệm trước cả khi bạn hỏi tới. Còn các nút của danh sách liên kết được cấp phát từng cái một, nằm rải rác ở đâu tuỳ bộ cấp phát và tuỳ lịch sử chương trình, nên mỗi lần đi theo một con trỏ có thể là một lần chờ bộ nhớ thật sự. Máy không đoán trước được nút tiếp theo nằm ở đâu, vì địa chỉ của nó chỉ lộ ra sau khi đọc xong nút hiện tại.
Hệ quả thực tế: mảng thường nhanh hơn ngay cả ở những chỗ phép đếm này nói nó thua. Duyệt tuần tự, tìm kiếm, thậm chí cả chèn xoá ở giữa với n vừa phải, vì dời vài trăm phần tử liền kề bằng một lệnh sao chép khối có khi vẫn rẻ hơn vài chục lần nhảy lung tung trong bộ nhớ. Đó là lý do trong mã nguồn thật, danh sách liên kết hiếm hơn nhiều so với những gì giáo trình gợi ý, và khi nó xuất hiện thì thường là vì một lý do khác chứ không phải vì tốc độ: cần con trỏ tới một phần tử vẫn còn đúng sau khi cấu trúc thay đổi, cần ghép hai dãy mà không chép gì, cần chèn xoá ở những chỗ đã có con trỏ sẵn.
Muốn biết cái nào nhanh hơn trong trường hợp của bạn thì phải đo, và bài hiệu năng tập hợp trong Java là chỗ nói về việc đo đó.
Vài chỗ nữa sim cố tình không đụng tới, để bạn khỏi đọc nó quá lời:
- Chi phí nới mảng không được tính. Cột chèn cuối của mảng giả định còn chỗ trống. Cái giá của việc hết chỗ đã tính đủ ở bài mảng động, và vì nó là hằng số khi chia đều nên nó không đổi kết luận nào ở đây, nhưng nó không bằng không.
- Chi phí cấp phát một nút cũng không được tính. Mỗi lần chèn vào danh sách liên kết là một lần xin bộ nhớ, và việc đó đắt hơn hẳn vài phép ghi con trỏ. Núm byte phụ trội chỉ mô hình hoá phần chỗ nhớ bị ăn thêm, không mô hình hoá thời gian.
- Cả hai bên đều được tìm tuần tự. Nếu dãy đã sắp xếp thì mảng còn tìm nhị phân được, còn danh sách liên kết thì không, vì tìm nhị phân cần nhảy thẳng vào giữa. Đó là một lợi thế nữa của mảng mà bảng này không hề tính tới.
- Vài byte hằng số không được đếm ở cả hai bên: biến kích thước của mảng, biến
headvà biến con trỏ cuối của danh sách. Chúng không lớn theonnên để ngoài cho tỉ lệ khỏi lệch, chứ không phải vì chúng bằng không.
Còn phần cài đặt bằng mã thật thì có ở hai chỗ: danh sách liên kết trong C cho phần cấu trúc, và con trỏ cho phần vì sao một biến lại có thể chứa địa chỉ của một biến khác.
Mảng thắng tuyệt đối ở truy cập theo chỉ số, 1 bước so với k + 1 bước, và ở chèn vào cuối khi danh sách không giữ con trỏ cuối, 1 so với 1.001. Danh sách liên kết thắng tuyệt đối ở chèn và xoá tại đầu, 2 so với 1.001 và 2 so với 1.000. Ở giữa thì phải tính, và điểm hoà vốn không phải là 50%: với cấu hình mở bài, phải từ 67% số thao tác trở lên là truy cập thì mảng mới bắt đầu rẻ hơn, còn ở 66% danh sách vẫn đang thắng. Câu "chèn vào giữa là O(1)" chỉ đúng khi đã có sẵn con trỏ, và với danh sách một chiều thì ngay cả việc cầm sẵn con trỏ cũng gần như vô dụng khi xoá, vì bạn vẫn cần nút đứng trước. Cái giá của mỗi con trỏ là gấp 3 lần bộ nhớ với phần tử 4 byte, gấp 5 nếu hai chiều. Và cuối cùng: sim này đếm bước chứ không đo giây, còn trong máy thật thì mảng thường nhanh hơn cả ở những chỗ phép đếm nói nó thua.
- 1Một danh sách liên kết một chiều có 1.000 nút. Bạn đang cầm sẵn con trỏ tới nút thứ 500 và muốn xoá đúng nút đó. Chi phí thật sự là bao nhiêu?
- 2Chương trình của bạn chỉ làm hai việc trên 1.000 phần tử: truy cập theo chỉ số giữa dãy, và chèn vào đầu. Muốn mảng rẻ hơn danh sách liên kết thì tỉ lệ truy cập phải chiếm ít nhất bao nhiêu?
- 3Sim đếm ra danh sách liên kết rẻ hơn mảng ở một thao tác nào đó. Kết luận nào là đúng?