Đếm chi phí thay vì đoán
Đếm chi phí thay vì đoán
Câu nói tốn kém nhất trong nghề này là 'thuật toán kia nhanh hơn' khi chưa ai đếm. Bài này bắt bạn đếm, trên đúng dữ liệu đang có, từng bước một.
Bạn sẽ nghe câu này rất nhiều trong bốn năm tới: thuật toán A nhanh hơn thuật toán B. Hỏi lại một câu là mọi thứ thường sụp: nhanh hơn trên dữ liệu nào, ở kích thước bao nhiêu, và ai đã đếm? Phần lớn thời gian câu trả lời là không ai cả. Người ta nhớ một dòng trong sách, thấy O(n) nhỏ hơn O(n²), rồi dừng lại ở đó.
Bài này không cấm bạn dùng bậc tăng trưởng. Nó chỉ bắt bạn làm một việc trước đã: chạy thuật toán và đếm. Ba con số được đếm là số phép so sánh, số phép gán, và số lần truy cập mảng. Không con số nào trong sim dưới đây đến từ một công thức đoán trước, tất cả đều là cái mà một lượt chạy thật để lại. Bạn đổi dữ liệu thì nó chạy lại và đếm lại.
1 · Dãy số đang xét ✎ sửa được
▲ là vị trí mà thuật toán đang xem (tìm cặp có tổng bằng k · hai vòng lặp) trả về. Bảng băm đang có 48 ô cho 24 phần tử.2 · Đếm khi chạy, trên đúng dãy ở trên nhấp để xem từng bước
| thuật toán | so sánh | gán | truy cập mảng | tổng phép | kết quả |
|---|---|---|---|---|---|
| tìm phần tử lớn nhất | 23 | 27 | 24 | 74 | lớn nhất là 20, ở vị trí 22 |
| đếm số lần xuất hiện | 24 | 28 | 24 | 76 | 8 xuất hiện 3 lần |
| kiểm tra đã sắp chưa | 2 | 4 | 4 | 10 | chưa sắp: nghịch thế đầu tiên ở vị trí 1 và 2 |
| ▶ tìm cặp có tổng bằng k · hai vòng lặp | 33 | 35 | 35 | 103 | tìm thấy cặp (1, 11): 16 + 9 = 25 |
| tìm cặp có tổng bằng k · bảng băm | 1 | 76 | 60 | 137 | tìm thấy cặp (2, 5): 8 + 17 = 25 |
3 · Từng bước của tìm cặp có tổng bằng k · hai vòng lặp ✎ chọn ở bảng trên
| bước | việc | so sánh | gán | truy cập | cộng dồn |
|---|---|---|---|---|---|
| 1 | lấy x = a[0] = 4 | · | 1 | 1 | 2 |
| 2 | a[0] + a[1] = 4 + 16 khác 25 | 1 | 1 | 1 | 5 |
| 3 | a[0] + a[2] = 4 + 8 khác 25 | 1 | 1 | 1 | 8 |
| 4 | a[0] + a[3] = 4 + 6 khác 25 | 1 | 1 | 1 | 11 |
| 5 | a[0] + a[4] = 4 + 8 khác 25 | 1 | 1 | 1 | 14 |
| 6 | a[0] + a[5] = 4 + 17 khác 25 | 1 | 1 | 1 | 17 |
| 7 | a[0] + a[6] = 4 + 3 khác 25 | 1 | 1 | 1 | 20 |
| 8 | a[0] + a[7] = 4 + 8 khác 25 | 1 | 1 | 1 | 23 |
| 9 | a[0] + a[8] = 4 + 4 khác 25 | 1 | 1 | 1 | 26 |
| 10 | a[0] + a[9] = 4 + 7 khác 25 | 1 | 1 | 1 | 29 |
| 11 | a[0] + a[10] = 4 + 2 khác 25 | 1 | 1 | 1 | 32 |
| 12 | a[0] + a[11] = 4 + 9 khác 25 | 1 | 1 | 1 | 35 |
| 13 | a[0] + a[12] = 4 + 1 khác 25 | 1 | 1 | 1 | 38 |
| 14 | a[0] + a[13] = 4 + 11 khác 25 | 1 | 1 | 1 | 41 |
| 15 | a[0] + a[14] = 4 + 10 khác 25 | 1 | 1 | 1 | 44 |
| 16 | a[0] + a[15] = 4 + 6 khác 25 | 1 | 1 | 1 | 47 |
| 17 | a[0] + a[16] = 4 + 6 khác 25 | 1 | 1 | 1 | 50 |
| 18 | a[0] + a[17] = 4 + 11 khác 25 | 1 | 1 | 1 | 53 |
| 19 | a[0] + a[18] = 4 + 17 khác 25 | 1 | 1 | 1 | 56 |
| 20 | a[0] + a[19] = 4 + 12 khác 25 | 1 | 1 | 1 | 59 |
| 21 | a[0] + a[20] = 4 + 9 khác 25 | 1 | 1 | 1 | 62 |
| 22 | a[0] + a[21] = 4 + 1 khác 25 | 1 | 1 | 1 | 65 |
| 23 | a[0] + a[22] = 4 + 20 khác 25 | 1 | 1 | 1 | 68 |
| 24 | a[0] + a[23] = 4 + 5 khác 25 | 1 | 1 | 1 | 71 |
| 25 | lấy x = a[1] = 16 | · | 1 | 1 | 73 |
| 26 | a[1] + a[2] = 16 + 8 khác 25 | 1 | 1 | 1 | 76 |
| 27 | a[1] + a[3] = 16 + 6 khác 25 | 1 | 1 | 1 | 79 |
| 28 | a[1] + a[4] = 16 + 8 khác 25 | 1 | 1 | 1 | 82 |
| 29 | a[1] + a[5] = 16 + 17 khác 25 | 1 | 1 | 1 | 85 |
| 30 | a[1] + a[6] = 16 + 3 khác 25 | 1 | 1 | 1 | 88 |
| 31 | a[1] + a[7] = 16 + 8 khác 25 | 1 | 1 | 1 | 91 |
| 32 | a[1] + a[8] = 16 + 4 khác 25 | 1 | 1 | 1 | 94 |
| 33 | a[1] + a[9] = 16 + 7 khác 25 | 1 | 1 | 1 | 97 |
| 34 | a[1] + a[10] = 16 + 2 khác 25 | 1 | 1 | 1 | 100 |
| 35 | a[1] + a[11] = 16 + 9 = 25, tìm thấy | 1 | 1 | 1 | 103 |
4 · Cùng bấy nhiêu số, chỉ đổi thứ tự
Bốn dòng dưới đây chứa đúng cùng một tập số, không thêm không bớt, chỉ khác thứ tự. Câu trả lời của mọi thuật toán vì thế không đổi. Chỉ có chi phí đổi.
| thứ tự | tìm max: số phép gán | đã sắp chưa: số so sánh | cặp tổng 25: tổng phép | đã sắp chưa: kết quả | cùng tập số |
|---|---|---|---|---|---|
| thứ tự sinh ra | 27 | 2 | 103 | chưa sắp: nghịch thế đầu tiên ở vị trí 1 và 2 | ✓ đúng |
| tăng dần | 38 | 23 | 434 | đã sắp tăng dần, phải xét hết mọi cặp kề nhau | ✓ đúng |
| giảm dần | 24 | 1 | 53 | chưa sắp: nghịch thế đầu tiên ở vị trí 0 và 1 | ✓ đúng |
| gần như đã sắp | 37 | 6 | 381 | chưa sắp: nghịch thế đầu tiên ở vị trí 5 và 6 | ✓ đúng |
5 · Mốc mà thứ tự đảo chiều ca phản trực giác
Ở đây cả hai thuật toán tìm cặp đều bị bắt chạy hết: mỗi độ dài dùng một tổng mà không cặp nào đạt tới, nên không ai được dừng sớm nhờ may. Với mỗi n từ 3 tới 24, sim dựng lại dãy theo đúng mẫu đang chọn rồi chạy thật và đếm.
| n | k xấu nhất | ô bảng băm | hai vòng lặp | bảng băm | ai ít phép hơn |
|---|---|---|---|---|---|
| 3 | 33 | 6 | 13 | 33 | ◀ hai vòng lặp |
| 4 | 33 | 8 | 24 | 44 | ◀ hai vòng lặp |
| 5 | 33 | 10 | 38 | 55 | ◀ hai vòng lặp |
| 6 | 35 | 12 | 55 | 68 | ◀ hai vòng lặp |
| 7 | 35 | 14 | 75 | 81 | ◀ hai vòng lặp |
| 8 | 35 | 16 | 98 | 90 | ▶ bảng băm · mốc đảo chiều |
| 9 | 35 | 18 | 124 | 99 | ▶ bảng băm |
| 10 | 35 | 20 | 153 | 116 | ▶ bảng băm |
| 11 | 35 | 22 | 185 | 123 | ▶ bảng băm |
| 12 | 35 | 24 | 220 | 144 | ▶ bảng băm |
| 13 | 35 | 26 | 258 | 153 | ▶ bảng băm |
| 14 | 35 | 28 | 299 | 160 | ▶ bảng băm |
| 15 | 35 | 30 | 343 | 171 | ▶ bảng băm |
| 16 | 35 | 32 | 390 | 178 | ▶ bảng băm |
| 17 | 35 | 34 | 440 | 187 | ▶ bảng băm |
| 18 | 35 | 36 | 493 | 198 | ▶ bảng băm |
| 19 | 35 | 38 | 549 | 209 | ▶ bảng băm |
| 20 | 35 | 40 | 608 | 220 | ▶ bảng băm |
| 21 | 35 | 42 | 670 | 231 | ▶ bảng băm |
| 22 | 35 | 44 | 735 | 242 | ▶ bảng băm |
| 23 | 41 | 46 | 803 | 253 | ▶ bảng băm |
| 24 | 41 | 48 | 874 | 264 | ▶ bảng băm |
- Nó đếm phép tính, nó không đo giây. Một phép so sánh hai chuỗi đắt hơn hẳn một phép so sánh hai số nguyên, mà ở đây cả hai đều tính là 1. Bộ nhớ đệm của máy làm mọi dự đoán lệch: một vòng lặp quét liên tiếp thường nhanh hơn nhiều so với một bảng băm nhảy lung tung, dù bảng băm ít phép hơn. Và trình biên dịch có quyền bỏ hẳn phần mã bạn tưởng nó chạy.
- Ba con số cộng lại thành tổng phép là một quy ước của bài này, không phải một đại lượng chuẩn. Nó coi một phép gán ngang giá một lần đọc mảng, điều không đúng trên máy thật.
- Điều khiển vòng lặp không được tính: phép so
jvớinvà phép tăngjở mỗi vòng đều bị bỏ qua, cho cả hai thuật toán. Tính vào thì mọi con số đội lên và phần khác nhau giữa chúng bị lấp bớt. - Cùng một thuật toán, viết khác nhau thì đếm khác nhau. Phép kiểm tra đã sắp ở đây đọc cả hai phần tử kề nhau mỗi bước, tức 2 lần truy cập; nếu giữ lại phần tử trước trong một biến thì chỉ còn 1, mà số so sánh không đổi một chút nào. Số so sánh thuộc về thuật toán, số truy cập thuộc về cách viết.
- Bộ sinh “ngẫu nhiên” ở đây là xorshift32 rồi lấy phần dư, nên phân bố lệch nhẹ về phía các giá trị nhỏ. Đủ dùng để dạy, không đủ dùng cho việc cần ngẫu nhiên thật sự.
- Bảng băm ở đây không nở ra: nó được dọn đúng một lần theo n. Bảng thật thường tự nhân đôi khi đầy, và lúc nhân đôi thì chi phí nhảy vọt thành bậc thang, chứ không mượt như bảng trong mục 5.
Ba con số, và vì sao phải là ba
Ở trạng thái mở bài, dãy có 24 số sinh từ hạt giống 7, mỗi số nằm trong khoảng 1 tới 20: 4 16 8 6 8 17 3 8 4 7 2 9 1 11 10 6 6 11 17 12 9 1 20 5. Đây không phải một dãy tôi bịa ra rồi dán vào bài. Nó là đầu ra của bộ sinh giả ngẫu nhiên viết ngay trong phần tính, và hạt giống là một núm bạn sửa được: đổi 7 thành 8 thì cả bài đổi theo, đổi ngược về 7 thì mọi con số quay lại y nguyên.
Tìm phần tử lớn nhất tốn 23 phép so sánh, 27 phép gán, 24 lần truy cập mảng, tổng 74. Con số 23 chính là n - 1, vì mỗi phần tử từ vị trí 1 trở đi bị so đúng một lần với giá trị lớn nhất đang giữ. Con số 24 là mỗi ô đọc đúng một lần. Còn 27 mới là chỗ thú vị: nó bằng 24 lần đọc cộng 3 lần thật sự ghi lại best. Trên dãy này chỉ có ba lần một số mới phá kỷ lục, là 16, 17 và 20.
Đếm số 8 xuất hiện mấy lần tốn 24 so sánh, 28 gán, 24 truy cập, tổng 76, và kết quả là 3 lần. Chú ý số so sánh ở đây là 24 chứ không phải 23: phép đếm không được dừng sớm. Muốn chắc chắn 8 xuất hiện đúng 3 lần thì phải nhìn hết, kể cả khi đã gặp cả ba từ sớm.
Kiểm tra dãy đã sắp chưa chỉ tốn 2 phép so sánh, tổng 10. Vì 16 đứng trước 8, chỉ cần tới cặp thứ hai là biết chưa sắp và dừng luôn. Hãy nhớ con số 2 này, lát nữa nó sẽ thành 23.
Tìm cặp có tổng bằng 25 thì có hai cách, và đây là chỗ bài học bắt đầu. Cách ngây thơ với hai vòng lặp lồng nhau tốn 33 so sánh, tổng 103 phép, và nó nêu ra cặp ở vị trí 1 và 11, tức 16 + 9. Cách dùng bảng băm tốn 1 so sánh nhưng 76 phép gán và 60 lần truy cập, tổng 137 phép, và nó nêu ra cặp ở vị trí 2 và 5, tức 8 + 17.
Hai chuyện đáng dừng lại ở đây. Thứ nhất, hai cách trả lời hai cặp khác nhau, và cả hai đều đúng: câu hỏi là có tồn tại một cặp hay không, chứ không phải cặp nào. Thứ hai, cách được coi là nhanh hơn lại tốn nhiều phép hơn, 137 so với 103, dù dãy đã dài 24 phần tử. Chuyện đó xảy ra vì cả hai đều dừng ngay khi gặp cặp đầu tiên, mà chúng gặp ở chỗ khác nhau. So như vậy là so may rủi.
Muốn so cho công bằng thì phải bắt cả hai chạy hết. Sim làm việc đó bằng cách lấy một tổng mà không cặp nào với tới: phần tử lớn nhất là 20, nên không cặp nào vượt quá 40, và tổng k = 41 là an toàn. Lúc đó hai vòng lặp tốn 874 phép còn bảng băm tốn 264 phép, chênh 3,31 lần. Đó mới là con số nói lên điều gì.
Cùng bấy nhiêu số, đổi thứ tự thì đổi giá
Mục 4 của sim là chỗ tôi muốn bạn ngồi lâu nhất. Bốn dòng ở đó chứa đúng cùng một tập số, không thêm một số nào, không bớt một số nào, chỉ khác thứ tự. Sim kiểm điều đó và đánh dấu ở cột cuối, nên bạn không phải tin lời tôi.
Kết quả thì y hệt nhau ở cả bốn dòng: phần tử lớn nhất vẫn là 20, số 8 vẫn xuất hiện 3 lần. Chi phí thì không.
- Kiểm tra đã sắp chưa: dãy đã sắp tăng dần tốn 23 phép so sánh, dãy giảm dần tốn đúng 1. Chênh 23 lần, trên đúng cùng những con số ấy.
- Tìm phần tử lớn nhất: dãy tăng dần tốn 38 phép gán, dãy giảm dần tốn 24. Số so sánh và số lần truy cập thì hai bên bằng nhau khít.
- Tìm cặp có tổng 25 bằng hai vòng lặp: 434 phép trên dãy tăng dần, 53 phép trên dãy giảm dần.
Ba chữ tốt nhất, trung bình, xấu nhất mà bạn sẽ gặp suốt học kỳ chính là chuyện này, không hơn. Chúng không mô tả thuật toán, chúng mô tả thuật toán gặp phải loại dữ liệu nào.
Và chú ý cái bẫy: với phép kiểm tra đã sắp, ca xấu nhất lại là dãy đã sắp sẵn. Nghe ngược đời nhưng đúng, vì không có nghịch thế nào để dừng sớm, nên nó buộc phải xét hết n - 1 cặp kề nhau. Còn dãy đảo ngược hoàn toàn, cái nghe như tệ nhất, lại là ca rẻ nhất: nghịch thế nằm ngay cặp đầu tiên. Con số 2 lúc nãy thành 23 chỉ vì thứ tự.
Tại sao 38 chứ không phải 47 cho dãy tăng dần? Vì dãy có số lặp lại. Trong 24 số chỉ có 15 giá trị khác nhau, mà best chỉ được ghi lại khi gặp số lớn hơn hẳn, chứ không phải bằng. Nên có 14 lần ghi lại, cộng 24 lần đọc, ra 38. Bạn tăng núm giá trị lớn nhất lên thì số lặp giảm và con số này bò lên gần 47.
Ca phản trực giác: khi cách chậm hơn lại ít phép hơn
Mục 5 là điểm dạy học quan trọng nhất của bài. Ở đó cả hai cách tìm cặp đều bị bắt chạy hết, mỗi độ dài dùng một tổng mà không cặp nào với tới, rồi sim dựng lại dãy ở từng độ dài từ 3 tới 24 và chạy thật để đếm.
Kết quả ở trạng thái mở bài:
- ở
n = 7, hai vòng lặp tốn 75 phép, bảng băm tốn 81 phép - ở
n = 8, hai vòng lặp tốn 98 phép, bảng băm tốn 90 phép - ở
n = 9, khoảng cách đã nới rộng: 124 so với 99
Mốc đảo chiều là n = 8. Ở mọi độ dài nhỏ hơn 8, cách bị coi là chậm hơn về bậc lại làm ít việc hơn. Chuyện này không hề bí ẩn. Ở n = 8 bảng băm có 16 ô, và chỉ riêng việc dọn 16 ô đó đã ăn 32 trong tổng số 90 phép, trước khi nó nhìn vào phần tử đầu tiên. Sau đó mỗi phần tử còn trả 5 phép gán và ít nhất 2 lần truy cập. Trong khi đó vòng lặp trong của cách ngây thơ chỉ trả đúng 1 phép so sánh mỗi lần, và ở n = 7 nó chỉ phải chạy 21 lần.
Nói cách khác, bậc tăng trưởng cho bạn biết ai thắng khi n đủ lớn. Nó tuyệt đối không nói cho bạn biết đủ lớn là bao nhiêu. Con số đó nằm ở các hằng số, mà hằng số thì phụ thuộc vào cách cài đặt.
Muốn thấy điều đó rõ hơn nữa, kéo núm ô bảng băm mỗi phần tử. Bảng càng rộng thì phần dọn bảng càng đắt, và mốc lùi ra theo:
| ô bảng cho mỗi phần tử | mốc đảo chiều |
|---|---|
| 1 | n = 7 |
| 2 (mặc định) | n = 8 |
| 3 | n = 9 |
| 4 | n = 10 |
Mốc này không phải một hằng số của vũ trụ. Nó là hệ quả của những hằng số bạn vừa chọn, và nếu bạn đổi cách cài đặt thì nó đi chỗ khác. Đây chính là lý do các thư viện sắp xếp thật ngoài đời chuyển sang một thuật toán "tệ hơn về bậc" khi mảng con còn ngắn.
Đếm phép không phải đo thời gian
Chỗ này phải nói thẳng, vì đây là hiểu nhầm dễ mắc nhất sau khi học xong một bài như bài này.
Sim đếm phép tính. Nó không đo giây. Bốn lý do, tất cả đều là chuyện thật:
- Không phải phép nào cũng đắt như nhau. So sánh hai số nguyên là một lệnh máy. So sánh hai chuỗi có thể phải duyệt hàng chục ký tự. Ở đây cả hai đều tính là 1.
- Bộ nhớ đệm của máy quyết định phần lớn thời gian thật. Một vòng lặp quét mảng liên tiếp đọc dữ liệu đã nằm sẵn trong bộ đệm, còn một bảng băm thì nhảy lung tung khắp bộ nhớ. Rất thường xuyên, cái ít phép hơn lại chậm hơn khi bấm đồng hồ.
- Trình biên dịch có quyền bỏ hẳn phần bạn tưởng nó chạy. Nếu kết quả không được dùng vào đâu, cả vòng lặp có thể biến mất khỏi mã máy.
- Ba con số cộng lại thành "tổng phép" là quy ước của bài này, không phải một đại lượng chuẩn của ngành. Nó coi một phép gán ngang giá một lần đọc mảng, điều không đúng trên máy thật.
Thêm hai điều mà sim tự nhận, bạn nên đọc kỹ vì chúng dạy nhiều hơn phần kết quả:
- Điều khiển vòng lặp không được tính. Phép so
jvớinvà phép tăngjbị bỏ qua, cho cả hai thuật toán. Tính vào thì mọi con số đội lên và phần khác nhau giữa chúng bị lấp bớt. Đó là một lựa chọn, và lựa chọn thì phải nói ra. - Cùng một thuật toán, viết khác nhau thì đếm khác nhau. Phép kiểm tra đã sắp ở đây đọc cả hai phần tử kề nhau mỗi bước, tức 2 lần truy cập; nếu giữ lại phần tử trước trong một biến thì chỉ còn 1, mà số so sánh không đổi một chút nào. Số so sánh thuộc về thuật toán, số truy cập thuộc về cách viết.
Vậy đếm phép để làm gì, nếu nó không cho biết thời gian? Để bạn có một con số kiểm chứng được thay cho một cảm giác. Nó phát hiện được chuyện thứ tự dữ liệu đổi chi phí 23 lần, chuyện mốc đảo chiều nằm ở 8 chứ không phải ở 3, và chuyện cách được ca ngợi lại thua ở kích thước nhỏ. Không cảm giác nào cho bạn những thứ đó.
Trước khi nói thuật toán nào nhanh hơn, hãy chạy cả hai và đếm. Ba con số so sánh, gán, truy cập mảng không phải là thời gian chạy, nhưng chúng kiểm chứng được, còn cảm giác thì không. Cùng một tập số chỉ đổi thứ tự đã làm phép kiểm tra đã sắp chênh 23 lần, nên tốt nhất, trung bình, xấu nhất là chuyện của dữ liệu chứ không phải của thuật toán. Và bậc tăng trưởng chỉ nói ai thắng khi n đủ lớn: trên dãy này, ở mọi độ dài dưới mốc n = 8 thì cách hai vòng lặp lại làm ít việc hơn cách bảng băm. Đủ lớn là bao nhiêu thì phải đếm mới biết.
- 1Với phép kiểm tra "dãy đã sắp tăng dần chưa" viết theo kiểu dừng ngay khi gặp nghịch thế đầu tiên, dãy nào là ca xấu nhất?
- 2Ở n = 7, cách hai vòng lặp lồng nhau tốn 75 phép còn cách bảng băm tốn 81 phép. Giải thích nào đúng?
- 3Ở ca xấu nhất trên dãy 24 phần tử, sim đếm 874 phép cho hai vòng lặp và 264 phép cho bảng băm, tức chênh 3,31 lần. Kết luận nào là kết luận đúng?