Chọn cấu trúc theo thao tác bạn làm nhiều nhất
Chọn cấu trúc theo thao tác bạn làm nhiều nhất
Chín chương vừa rồi đếm chi phí của từng cấu trúc một cách riêng lẻ. Bài này gom chúng lại thành một câu hỏi thực dụng, và trả lời bằng phép cộng thay cho cảm giác.
Câu hỏi mà mọi bài trước dẫn tới là câu này: tôi nên dùng cấu trúc nào? Và câu trả lời trung thực duy nhất là một câu hỏi ngược lại: bạn sẽ làm gì với dữ liệu, mỗi việc bao nhiêu lần?
Bài này không cho bạn một bảng xếp hạng. Nó cho bạn một cái máy tính tiền. Bạn khai ra khối lượng công việc, gồm sáu con số: bao nhiêu lần chèn, bao nhiêu lần xoá, bao nhiêu lần tìm theo khoá, bao nhiêu lần đọc phần tử thứ k, bao nhiêu lần hỏi phần tử nhỏ nhất, bao nhiêu lần duyệt hết theo thứ tự khoá. Sim cộng số bước cho từng cấu trúc, rồi xếp theo con số. Đổi khối lượng thì thứ tự đổi, và đó là toàn bộ nội dung của bài.
Năm cấu trúc trong bảng, và bài đã dạy từng cái:
- Mảng động, ở bài mảng động.
- Danh sách liên kết đơn, ở bài danh sách liên kết so với mảng.
- Bảng băm dây móc, ở hai bài hàm băm và va chạm và hệ số tải.
- Cây tìm kiếm cân bằng, ở hai bài cây tìm kiếm nhị phân và cân bằng cây bằng phép xoay.
- Đống nhỏ nhất, ở bài đống và hàng đợi ưu tiên.
1 · Khối lượng công việc của bạn ✎ sửa được
2 · Cấu trúc đang giữ bao nhiêu, và ở dạng nào ✎ sửa được
Ở 1.000 phần tử: cây cân bằng cao 14 mức theo cây cao nhất mà luật cân bằng còn cho phép (dải cho phép là 10 tới 14 mức), bảng băm cần 1.334 ô để giữ hệ số tải 75%, và phần tử vừa chèn vào đống nằm ở mức có thể nổi lên 9 lần.
3 · Hoá đơn cho đúng khối lượng đó
| cấu trúc \ thao tác | chèn100 lượt | xoá20 lượt | tìm khoá5.000 lượt | theo chỉ số0 lượt | nhỏ nhất0 lượt | duyệt thứ tự0 lượt | tổng số bước | thứ |
|---|---|---|---|---|---|---|---|---|
| mảng động | 501× 100 = 50.100 | 500× 20 = 10.000 | 501× 5.000 = 2.505.000 | 1không dùng | 1.000không dùng | × không làm được | 2.565.100105,28 lần tổng nhỏ nhất | #3 |
| danh sách liên kết đơn | 501× 100 = 50.100 | 502× 20 = 10.040 | 1.001× 5.000 = 5.005.000 | 501không dùng | 1.999không dùng | × không làm được | 5.065.140207,89 lần tổng nhỏ nhất | #4 |
| bảng băm dây móc | 5× 100 = 500 | 5,75× 20 = 115 | 4,75× 5.000 = 23.750 | × không làm được | 3.334không dùng | × không làm được | 24.365ít nhất | #1 |
| cây tìm kiếm cân bằng | 38× 100 = 3.800 | 84× 20 = 1.680 | 14× 5.000 = 70.000 | × không làm được | 14không dùng | 1.000không dùng | 75.4803,10 lần tổng nhỏ nhất | #2 |
| đống nhỏ nhất | 18× 100 = 1.800 | × không làm được | × không làm được | × không làm được | 1không dùng | × không làm được | bị loại | – |
4 · Đổi khối lượng thì đổi người thắng
Bảng dưới đây tính lại cả chín khối lượng mẫu, ở đúng 1.000 phần tử, hệ số tải 75% và chiều cao cây 14 mức mà bạn đang đặt. Nó là bằng chứng cho câu quan trọng nhất của bài: bảng ở mục 3 không xếp hạng cấu trúc, nó chỉ cộng số bước cho đúng khối lượng đang gõ.
| khối lượng | ít bước nhất | tổng của nó | còn bao nhiêu cấu trúc trong cuộc |
|---|---|---|---|
| Sổ tra cứu theo mã | bảng băm dây móc | 24.365 bước | 4/5 |
| Bảng điểm đọc theo chỉ số | mảng động | 65.100 bước | 2/5 |
| Nhật ký luôn ghi vào đầu | danh sách liên kết đơn | 10.200 bước | 4/5 |
| Hàng đợi ưu tiên | đống nhỏ nhất | 19.000 bước | 5/5 |
| Ưu tiên nhưng phải xoá được bất kỳ | cây tìm kiếm cân bằng | 26.200 bước | 4/5 |
| Báo cáo sắp theo khoá | cây tìm kiếm cân bằng | 67.800 bước | 1/5 |
| Mốc hoà: chỉ chèn vào giữa | bảng băm dây móc | 5.000 bước | 5/5 |
| Mốc biên: không có việc gì | cả năm hoà ở 0 bước | 0 bước | 5/5 |
| Mốc biên: đòi cả hai thứ xung khắc | không có ai | – | 0/5 |
5 · Riêng mảng và danh sách: vị trí k quyết định
Với khối lượng đang gõ, mảng động bắt đầu rẻ hơn danh sách liên kết từ vị trí k = 23 trở lên, và dưới vị trí đó thì danh sách rẻ hơn. Không có vị trí nào hai bên hoà khít, vì khối lượng này trộn nhiều loại thao tác nên hai đường không cắt nhau tại một số nguyên.
| vị trí k | mảng | danh sách | bảng băm | cây | đống | ít bước nhất |
|---|---|---|---|---|---|---|
| k = 0 | 125.100 | 5.240 | 24.365 | 75.480 | × loại | danh sách |
| k = 250 | 1.345.100 | 2.535.140 | 24.365 | 75.480 | × loại | bảng băm |
| k = 500 | 2.565.100 | 5.065.140 | 24.365 | 75.480 | × loại | bảng băm |
| k = 750 | 3.785.100 | 7.595.140 | 24.365 | 75.480 | × loại | bảng băm |
| k = 999 | 5.000.220 | 10.115.020 | 24.365 | 75.480 | × loại | bảng băm |
6 · Bảng tra nhanh, và bài đã dạy từng cái
- Nó không xếp hạng cấu trúc. Nó cộng số bước cho đúng khối lượng bạn gõ vào. Bảng ở mục 4 cho thấy năm khối lượng khác nhau đưa năm cấu trúc khác nhau lên đầu, nên bất kỳ câu nào rút ra từ đây mà bỏ mất chữ "với khối lượng này" đều đã sai.
- Đơn vị bước của năm cột không hoàn toàn cùng thang. Mỗi con số được giữ đúng theo cách đếm của bài đã dạy cấu trúc đó, để hai bài không nói ngược nhau: bài danh sách liên kết tính cả lần theo con trỏ, còn bài cân bằng cây chỉ tính phép so sánh và phép ghi. Cộng chúng vào một cột rồi xếp hạng là một xấp xỉ. Tôi chọn giữ đúng từng bài, vì cái giá của lựa chọn kia là một con số mà không trang nào khác trong sách đồng ý.
- Đếm bước không phải đo giây. Mảng nằm liền mạch nên bộ nhớ đệm của máy thưởng cho nó rất nhiều, còn các nút của danh sách liên kết nằm rải rác nên bị phạt. 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ồ. Sim không mô hình hoá chuyện đó, vì mô hình hoá nó nghĩa là bịa ra một con số.
- Ba chi phí bị cố ý bỏ ra ngoài: cấp phát lại của mảng động, băm lại của bảng băm, và chi phí sắp xếp trước khi duyệt theo thứ tự. Hai cái đầu là hằng số khấu hao đã được chứng minh ở bài riêng của chúng, ở cấu hình mở bài của bài mảng động là 2,02 phép cho mỗi phần tử, tức khoảng một lần chép thêm cho mỗi lượt chèn. Cái thứ ba là một thao tác khác, nên tính nó vào đây là lặng lẽ trả lời một câu hỏi khác.
- Con số của cây là trần của trường hợp xấu nhất, không phải phép đo trên một cây cụ thể. Ở 1.000 khoá, luật cân bằng cho phép cây cao từ 10 tới 14 mức, và núm ở thanh công cụ cho bạn xem cả hai đầu dải. Ở n rất nhỏ thì trần này nới hơn thực tế khá nhiều.
- Con số của bảng băm là công thức lý tưởng hoá, lấy từ bài hệ số tải: nó giả định hàm băm trải khoá thật đều. Trên một bảng thật 64 ô, chính bài đó đo được 1,354 nút mỗi lượt tra thành công trong khi công thức nói 1,375. Sim dùng công thức, và nói ra là nó dùng công thức.
- Đọc phần tử nhỏ nhất khác với lấy nó ra. Cột "nhỏ nhất" chỉ đọc. Lấy hẳn ra khỏi đống thì phần tử cuối phải lên gốc rồi chìm lại xuống, tốn thêm tối đa 28 bước ở 1.000 phần tử.
Trạng thái mở bài nói gì
Sim khởi động ở một khối lượng kiểu sổ tra cứu theo mã: cấu trúc đang giữ 1.000 phần tử, và công việc gồm 100 lượt chèn, 20 lượt xoá, 5.000 lượt tìm theo khoá, tổng cộng 5.120 lượt. Không đọc theo chỉ số, không cần báo cáo sắp thứ tự. Vị trí k của các thao tác theo vị trí đặt ở 500, tức giữa mảng.
Hoá đơn cho mỗi lượt, ở đúng cấu hình đó:
| chèn | xoá | tìm khoá | theo chỉ số | nhỏ nhất | duyệt thứ tự | |
|---|---|---|---|---|---|---|
| mảng động | 501 | 500 | 501 | 1 | 1.000 | không làm được |
| danh sách liên kết đơn | 501 | 502 | 1.001 | 501 | 1.999 | không làm được |
| bảng băm dây móc | 5 | 5,75 | 4,75 | không làm được | 3.334 | không làm được |
| cây tìm kiếm cân bằng | 38 | 84 | 14 | không làm được | 14 | 1.000 |
| đống nhỏ nhất | 18 | không làm được | không làm được | không làm được | 1 | không làm được |
Nhân với số lượt rồi cộng lại:
- bảng băm 24.365 bước, xếp thứ nhất
- cây cân bằng 75.480 bước, tức 3,10 lần bảng băm
- mảng động 2.565.100 bước, tức 105,28 lần
- danh sách liên kết 5.065.140 bước, tức 207,89 lần
- đống bị loại, không xếp hạng
Riêng cột tìm khoá đã gánh gần hết hoá đơn: bảng băm 23.750 bước, cây 70.000 bước, còn mảng động 2.505.000 bước. Khi một thao tác chiếm 5.000 trong 5.120 lượt thì mọi thứ khác chỉ là tiếng ồn, và đó chính là ý của cái tên bài.
Chú ý con đống bị loại chứ không xếp bét. Khối lượng này có 20 lượt xoá và 5.000 lượt tìm khoá, hai việc mà đống không làm được. Xếp nó thứ năm sẽ hàm ý rằng nó vẫn chạy, chỉ chậm. Sự thật khác hẳn: nó không chạy.
Ranh giới quan trọng nhất: đây không phải bảng xếp hạng
Nếu bạn chỉ nhớ một câu từ bài này, hãy nhớ câu này. Bảng ở mục 3 không trả lời "cấu trúc nào tốt nhất". Nó cộng số bước cho đúng sáu con số bạn vừa gõ. Đổi chúng thì thứ tự đổi, và mục 4 của sim tồn tại để chứng minh chuyện đó chứ không phải để nói suông.
Cùng 1.000 phần tử, cùng hệ số tải, cùng chiều cao cây, chỉ đổi khối lượng:
| khối lượng | ít bước nhất | tổng của nó | còn trong cuộc |
|---|---|---|---|
| sổ tra cứu theo mã | bảng băm | 24.365 | 4/5 |
| bảng điểm đọc theo chỉ số | mảng động | 65.100 | 2/5 |
| nhật ký luôn ghi vào đầu | danh sách liên kết | 10.200 | 4/5 |
| hàng đợi ưu tiên | đống | 19.000 | 5/5 |
| ưu tiên nhưng phải xoá được bất kỳ | cây cân bằng | 26.200 | 4/5 |
| báo cáo sắp theo khoá | cây cân bằng | 67.800 | 1/5 |
Năm cấu trúc, năm khối lượng, năm người thắng khác nhau. Không cấu trúc nào trong bảng thắng mọi lúc, và không cấu trúc nào thua mọi lúc. Nếu một trong năm chưa bao giờ thắng gì thì bảng này đã thực sự là một bảng xếp hạng, và tôi sẽ phải bỏ nó ra khỏi bài.
Hai dòng trong bảng đó thắng theo hai cách khác nhau, và phân biệt được hai cách ấy mới là hiểu bài:
- Đống thắng hàng đợi ưu tiên bằng con số. Cả năm cấu trúc đều làm được khối lượng đó, và đống rẻ nhất: 19.000 bước so với 52.000 bước của cây cân bằng, người về nhì. Chèn tốn 18 bước và đọc nhỏ nhất tốn đúng 1 bước, vì phần tử nhỏ nhất luôn nằm ở gốc.
- Cây cân bằng thắng báo cáo sắp theo khoá bằng loại trừ. Khối lượng đó có 50 lượt duyệt theo thứ tự khoá, và bốn cấu trúc kia không giữ thứ tự khoá nên không làm được. Cây thắng vì nó là người duy nhất còn lại, không phải vì nó rẻ. Sim nói đúng câu đó thay vì để bạn tưởng nó vừa vượt qua bốn đối thủ.
Còn một núm nữa cũng lật được thứ hạng, và nó không nằm trong sáu con số khối lượng: vị trí k. Với đúng khối lượng mở bài, kéo k về 0, tức mọi thao tác đều ở đầu, thì danh sách liên kết tụt từ 5.065.140 bước xuống 5.240 bước và thắng cả bảng băm, còn mảng động lên 125.100 bước vì mỗi lượt chèn phải dời cả nghìn phần tử. Tới k = 250 thì mảng động đã ngược lại: 1.345.100 bước so với 2.535.140 bước của danh sách, và bảng băm giành lại ngôi đầu ở 24.365 bước, con số không đổi vì bảng băm không quan tâm bạn chèn vào đâu.
Chỗ bảng này không nói được
Có chín cặp cấu trúc và thao tác mà sim từ chối định giá. Nó in chữ "không làm được" kèm một câu giải thích, thay vì in một con số giả. Đây là danh sách đầy đủ, và mỗi dòng là một tính chất của cấu trúc chứ không phải một giới hạn của sim:
- Bảng băm và đống không duyệt theo thứ tự khoá. Hàm băm cố tình trải khoá ra khắp bảng, nên hai khoá kề nhau về giá trị rơi vào hai ô cách xa nhau. Còn đống chỉ bảo đảm cha nhỏ hơn hai con, nên đọc mảng của nó từ đầu tới cuối không ra thứ tự tăng dần. Muốn thứ tự thì phải lấy hết ra rồi sắp, và sắp là một thao tác khác với hoá đơn riêng, xem sắp xếp trộn.
- Mảng động và danh sách liên kết cũng không duyệt theo thứ tự khoá, vì chúng giữ thứ tự bạn đã chèn chứ không giữ thứ tự khoá. Chúng chỉ khác bảng băm ở chỗ dễ sắp hơn, không khác ở chỗ có sẵn thứ tự.
- Bảng băm không có phần tử thứ k. Vị trí của một khoá do hàm băm quyết định, nên đọc ô số k trả về một khoá tuỳ ý chứ không phải phần tử thứ k của bất cứ trình tự nào.
- Cây tìm kiếm cân bằng cũng không có phần tử thứ k, vì nó không lưu kích cỡ từng cây con nên không biết đường nào chứa phần tử ấy. Có bản mở rộng lưu thêm số nút mỗi cây con và làm được việc này trong chiều cao bước, nhưng đó là một cấu trúc khác, và sim không cho điểm cho thứ nó chưa có.
- Đống không tìm được khoá bất kỳ và không xoá được phần tử bất kỳ. So sánh với gốc không cho biết khoá cần tìm nằm ở nhánh nào, nên không có đường đi nào dẫn tới nó. Quét cả mảng thì được, nhưng lúc đó bạn đang dùng nó như một mảng chứ không như một đống. Và vì không tìm được, cũng không xoá được.
- Ô số k của mảng đống không phải phần tử thứ k. Đọc nó mất đúng một bước, nhưng con số ấy trả lời một câu hỏi khác, nên sim không nhận.
Quy tắc loại trừ có một chi tiết dễ làm sai và bài kiểm số của bài canh nó ở cả hai phía: một cấu trúc chỉ bị loại khi thao tác nó không làm được có số lượt lớn hơn 0. Bấm sang khối lượng mốc biên: không có việc gì rồi đặt số lượt duyệt theo thứ tự bằng 1 thì bốn cấu trúc bị loại ngay; hạ về 0 thì cả năm quay lại. Mốc nằm ở 1, không nằm ở 0. Phải làm phép thử này trên khối lượng rỗng thì mới đọc được đúng mốc: ở khối lượng mở bài, hạ về 0 chỉ đưa bốn cấu trúc quay lại, vì đống vẫn nằm ngoài do 5.000 lượt tra khoá và 20 lượt xoá của chính khối lượng đó.
Có một khối lượng mà cả năm đều bị loại: vừa đọc theo chỉ số vừa duyệt theo thứ tự khoá. Không cấu trúc đơn lẻ nào trong bảng có cả hai. Sim nói đúng câu đó, và nói thêm lối ra thật: ghép hai cấu trúc, ví dụ một bảng băm để tra theo khoá cạnh một cây để duyệt theo thứ tự, rồi trả giá bằng việc phải cập nhật cả hai mỗi lần dữ liệu đổi. Một bảng không tìm được người thắng thì phải nói là không có, chứ không được chọn bừa.
Mốc hoà khít: đúng giữa mảng
Có một chỗ hai cấu trúc hoà bằng nhau khít, và nó tính ra được bằng một dòng.
Chèn vào vị trí k của mảng động tốn n - k lần dời cộng 1 lần ghi, tức n - k + 1 bước. Cùng chỗ đó, danh sách liên kết phải đi bộ k - 1 bước tới nút đứng trước rồi ghi 2 liên kết, tức k + 1 bước. Hai vế bằng nhau khi n - k + 1 = k + 1, tức k = n/2.
Ở 1.000 phần tử, bấm khối lượng mốc hoà: chỉ chèn vào giữa rồi để k ở 500:
| vị trí k | mảng động | danh sách liên kết | ai rẻ hơn |
|---|---|---|---|
| 499 | 502.000 | 500.000 | danh sách, rẻ hơn 2.000 |
| 500 | 501.000 | 501.000 | hoà khít |
| 501 | 500.000 | 502.000 | mảng, rẻ hơn 2.000 |
Ba dòng ở đây có chủ ý. Một cổng kiểm chỉ khẳng định "có tồn tại chỗ hoà" thì không phân biệt được 500 với 499, 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 của bài khoá cả ba vị trí, và khoá thêm rằng ở 499 và 501 thì không có chỗ hoà nào, để một mốc thật không bị lẫn với một vùng phẳng.
Hai chuyện nữa đáng nói ở mốc này. Thứ nhất, k = n/2 chỉ là số nguyên khi n chẵn: ở 999 phần tử không có vị trí nào hoà, và hai vị trí gần mốc lệch nhau đúng 1 bước mỗi lượt chèn. Thứ hai, chỗ hoà này nằm ở giữa bảng chứ không ở đỉnh. Với khối lượng chỉ có chèn, bảng băm vẫn thắng chung cuộc ở 5.000 bước vì nó không phải dời cũng không phải đi bộ; mảng động và danh sách liên kết cùng xếp thứ tư ở 501.000 bước. Một chỗ hoà sâu trong bảng vẫn là một chỗ hoà, và sim in ra câu đó.
Với khối lượng mở bài, tức đã trộn cả xoá và tìm khoá, hai đường không còn cắt nhau tại một số nguyên nào nữa: mảng động bắt đầu rẻ hơn từ k = 23, và không có vị trí nào hai bên bằng nhau khít. Mốc là hệ quả của những con số bạn gõ vào, không phải hằng số của vũ trụ.
Con số của bài này khớp với con số bài trước
Đây là chỗ tôi cẩn thận nhất, vì hai bài của một cuốn sách nói ngược nhau là lỗi tệ nhất mà cuốn sách đó có thể mắc. Mọi hoá đơn trong bảng đều giữ đúng cách đếm của bài đã dạy cấu trúc ấy, và cổng kiểm số của bài này biên dịch luôn năm engine kia rồi so từng con số:
- Mảng động và danh sách liên kết: 1.044 ô hoá đơn được so với đúng cái mà bài danh sách liên kết in ra, trên nhiều cỡ và nhiều vị trí. Ví dụ cụ thể mà cả hai bài đều in: ở 1.000 phần tử, chèn vào đầu tốn 1.001 bước trên mảng và 2 bước trên danh sách; chèn vào giữa tốn 501 so với 501. Con số 501 hoà nhau đó chính là câu mà preset của bài kia đã ghi.
- Bảng băm: chi phí một lượt tra cứu là 1 phép băm, 1 lần đọc con trỏ đầu ô, rồi 2 bước cho mỗi nút phải xem, và số nút phải xem lấy đúng công thức của bài hệ số tải. Cổng đối chiếu ở cả 40 mức hệ số tải từ 5% tới 200%. Hệ số tải mặc định 75% cũng chính là ngưỡng băm lại mà bài kia dùng.
- Cây cân bằng: mọi con số chiều cao được so với hàm của bài cân bằng cây, trên 3.001 giá trị
n. Một phép quay đơn tính 3 lần ghi liên kết, đúng bằng con số mặc định của bài đó. Hơn nữa cổng dựng cây thật bằng engine của bài kia trên 14 cỡ, rồi kiểm rằng chiều cao đo được nằm trong dải mà bài này tính, rằng lượt tra sâu nhất tốn đúng bằng chiều cao, và rằng không lượt chèn thật nào vượt quá cái trần mà bài này đặt. - Đống: mỗi con số chèn được so với việc chạy thật hàm chèn của bài đống trên một đống ở trường hợp xấu nhất, ở 15 cỡ khác nhau. Hai bên khớp chính xác, không phải xấp xỉ.
- Mảng động, phần bị bỏ ra ngoài: chi phí cấp phát lại không nằm trong bảng này, và con số tôi nêu ở phần cuối sim, 2,02 phép cho mỗi phần tử, là số mà chính bài mảng động đo được ở cấu hình mở bài của nó, gồm 2.020 phép cho 1.000 lượt thêm, 8 lần dời và 1.020 phần tử bị chép.
Phải nói thẳng một chỗ xấp xỉ trong việc này, vì giữ đúng từng bài có giá của nó. Cách đếm của các bài không giống nhau: bài danh sách liên kết tính cả lần theo con trỏ, còn bài cân bằng cây chỉ tính phép so sánh và phép ghi. Nghĩa là một "bước" ở cột cây hơi rẻ hơn một "bước" ở cột danh sách. Cộng chúng vào một cột rồi xếp hạng là một phép xấp xỉ, và tôi chọn giữ đúng từng bài vì cái giá của lựa chọn kia là một con số mà không trang nào khác trong sách đồng ý. Bạn nên đọc thứ hạng như một so sánh bậc độ lớn, không như một phép đo lệch nhau vài phần trăm.
Bảng tra nhanh
Mỗi dòng một cấu trúc: mạnh ở đâu, yếu ở đâu, và bài đã dạy nó.
- Mảng động mạnh nhất ở phép đọc phần tử thứ k trong đúng 1 bước, và không cấu trúc nào khác trong bảng làm được việc đó. Nó nằm liền mạch trong bộ nhớ nên bộ nhớ đệm của máy thưởng cho nó, thứ mà bảng đếm bước này không thấy. Yếu ở chỗ chèn hay xoá giữa mảng phải dời nửa mảng, và tìm theo khoá phải quét tuyến tính. Xem mảng động và tìm tuyến tính so với tìm nhị phân.
- Danh sách liên kết đơn mạnh ở chỗ chèn và xoá tại nơi bạn đang đứng chỉ tốn vài lần ghi con trỏ, không phải dời gì cả, và đó là lý do ngăn xếp và hàng đợi cùng danh sách kề của biểu diễn đồ thị hay dựng trên nó. Yếu ở chỗ muốn tới vị trí k thì phải đi bộ đúng k bước, và các nút nằm rải rác nên bộ nhớ đệm phạt nặng. Xem danh sách liên kết so với mảng.
- Bảng băm dây móc mạnh ở chỗ tra một khoá gần như không phụ thuộc số phần tử: hoá đơn chỉ nhìn hệ số tải. Đây là cấu trúc rẻ nhất cho câu hỏi "khoá này có không". Yếu ở chỗ không giữ thứ tự nào cả, nên không duyệt theo thứ tự và không có phần tử thứ k; và hoá đơn xấu đi nhanh khi hệ số tải cao. Xem hàm băm và va chạm và hệ số tải.
- Cây tìm kiếm cân bằng là cấu trúc duy nhất trong bảng giữ thứ tự khoá, nên nó là cấu trúc duy nhất duyệt theo thứ tự được, và cũng là cấu trúc duy nhất trả lời được những câu kiểu "khoá nhỏ nhất còn lớn hơn x". Mọi thao tác của nó đều có trần theo chiều cao. Yếu ở chỗ không thao tác nào rẻ bằng bảng băm ở phép tra khoá đơn thuần. Xem cây tìm kiếm nhị phân và cân bằng cây bằng phép xoay.
- Đống nhỏ nhất mạnh ở đúng hai việc và mạnh tuyệt đối ở đó: chèn tốn theo chiều cao, và phần tử nhỏ nhất luôn ở gốc nên đọc mất 1 bước. Nó nằm gọn trong một mảng, không con trỏ nào. Yếu ở chỗ nó chỉ có hai việc đó: không tìm được khoá bất kỳ, không xoá được phần tử bất kỳ, không có phần tử thứ k, và đọc mảng của nó không ra thứ tự tăng dần. Xem đống và hàng đợi ưu tiên.
Nếu bạn muốn xem lại vì sao những con số này đáng tin, hai bài mở đầu học phần là chỗ để về: đếm chi phí thay vì đoán và các bậc tăng và chỗ chúng cắt nhau.
Đếm bước 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 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ồ. Mảng động là bên hưởng lợi lớn nhất từ chuyện này và bảng đếm bước không cho nó điểm nào.
- Mảng ở đây không phải mảng đã sắp. Nó giữ thứ tự chèn, nên tìm khoá phải quét tuyến tính. Nếu bạn giữ mảng luôn đã sắp thì tìm khoá tụt xuống 10 bước ở 1.000 phần tử, đúng như tìm nhị phân đã đếm, nhưng đổi lại mỗi lượt chèn phải tìm đúng chỗ rồi vẫn phải dời, và bạn đã trả tiền cho một lần sắp ban đầu. Đó là một cấu trúc khác với hoá đơn khác, và sim không mô hình hoá nó.
- Con số của cây là trần của trường hợp xấu nhất, không phải phép đo trên một cây cụ thể. Ở 1.000 khoá, luật cân bằng cho phép cây cao từ 10 tới 14 mức, vì cây cân bằng cao 14 mức cần ít nhất 986 nút còn cao 15 mức thì cần tới 1.596 nút. Núm ở thanh công cụ cho bạn xem cả hai đầu dải: chuyển sang sàn tốt nhất thì tổng của cây tụt từ 75.480 xuống 54.200 bước, vì mỗi lượt chèn xuống 30 bước và mỗi lượt xoá xuống 60 bước. Ở
nrất nhỏ thì trần này nới hơn thực tế khá nhiều. - Con số của bảng băm là công thức lý tưởng hoá, giả định hàm băm trải khoá thật đều. Trên một bảng thật 64 ô, chính bài hệ số tải đo được 1,354 nút mỗi lượt tra thành công trong khi công thức nói 1,375. Sim dùng công thức, và nói ra rằng nó dùng công thức.
- Ba chi phí bị cố ý bỏ ra ngoài: cấp phát lại của mảng động, băm lại của bảng băm, và chi phí sắp xếp trước khi duyệt theo thứ tự. Hai cái đầu là hằng số khấu hao đã chứng minh ở bài riêng của chúng; cái thứ ba là một thao tác khác, nên tính nó vào đây là lặng lẽ trả lời một câu hỏi khác.
- Đọc phần tử nhỏ nhất khác với lấy nó ra. Cột "nhỏ nhất" chỉ đọc. Lấy hẳn ra khỏi đống thì phần tử cuối phải lên gốc rồi chìm lại xuống, tốn thêm tối đa 28 bước ở 1.000 phần tử.
- Chín khối lượng mẫu là số minh hoạ, không chép từ hệ thống thật nào. Chúng có mặt để cho thấy thứ tự đổi khi khối lượng đổi. Khối lượng thật của bạn là thứ duy nhất đáng gõ vào.
Vậy đếm để làm gì? Để lần sau, khi ai đó nói "dùng bảng băm đi, nó nhanh hơn", bạn có một câu hỏi cụ thể để hỏi lại: nhanh hơn ở thao tác nào, và tôi làm thao tác đó bao nhiêu lần? Với 5.000 lượt tra khoá thì bảng băm thật sự rẻ hơn cây tới 3,10 lần. Với 50 lượt duyệt theo thứ tự thì nó không rẻ hơn gì cả, vì nó không làm được. Không cảm giác nào phân biệt được hai câu đó.
Không có cấu trúc tốt nhất, chỉ có cấu trúc rẻ nhất cho một khối lượng cụ thể. Ở khối lượng mở bài, gồm 100 lượt chèn, 20 lượt xoá và 5.000 lượt tra khoá trên 1.000 phần tử, bảng băm tốn 24.365 bước, cây cân bằng 75.480, mảng động 2.565.100, danh sách liên kết 5.065.140, còn đống bị loại thẳng vì nó không tra khoá và không xoá được phần tử bất kỳ. Đổi khối lượng thì đổi người thắng: sáu khối lượng mẫu trong sim đưa cả năm cấu trúc lên đầu ít nhất một lần. Hai kiểu thắng phải phân biệt, thắng bằng con số như đống ở hàng đợi ưu tiên và thắng bằng loại trừ như cây ở báo cáo sắp theo khoá. Và có chỗ bảng này không nói được: chín cặp cấu trúc với thao tác bị từ chối định giá, vì bảng băm không giữ thứ tự và đống chỉ cho phần tử nhỏ nhất. Từ chối một con số là câu trả lời đúng, in ra một con số giả thì không.
- 1Bạn giữ 1.000 phần tử và mỗi ngày làm 5.000 lượt tra theo khoá, 100 lượt chèn, 20 lượt xoá, không bao giờ cần báo cáo sắp thứ tự. Sim xếp bảng băm nhất với 24.365 bước, cây cân bằng nhì với 75.480. Kết luận nào đúng?
- 2Bạn cần một cấu trúc vừa đọc được phần tử thứ k rất nhiều lần, vừa in được báo cáo sắp theo khoá. Sim báo cả năm cấu trúc đều bị loại. Điều đó nghĩa là gì?
- 3Cấu trúc giữ 1.000 phần tử, khối lượng chỉ gồm 1.000 lượt chèn vào vị trí k. Ở k = 499 danh sách liên kết tốn 500.000 bước còn mảng động tốn 502.000. Ở k = 501 thì ngược lại, 502.000 so với 500.000. Vì sao mốc lật nằm đúng ở 500?