Thuật toán, Donald Knuth

Thuật toán, Donald Knuth

Có lần Donald Knuth nói trong một lần phỏng vấn đại ý là ông chưa thấy một chương trình nào (của người khác) mà ông không làm cho nó nhanh hơn 10 lần được.

Một trong những điểm đặc biệt của Knuth là ông rất tỉ mỉ khi phân tích giải thuật. Tỉ mỉ đến từng đơn vị thời gian. Chính vì thế mà hầu hết code trong TAoCP của ông được viết trên MMIX, ngôn ngữ bậc rất thấp, vì với chương trình viết trên MMIX, ông có thể đếm được số lệnh cơ bản trong chương trình mà ông thiết kể để minh họa cho tính tối ưu của nó.

Trong sách TAoCP (Vol 3) của ông có một ví dụ như thế này mà mình rất thích. Ở đây mình minh họa bằng C (mình phải thừa nhận rằng cách minh họa này không hay lắm, nhưng tìm cách minh họa giống với MMIX không dễ).

Giả sử bạn có một danh sách liên kết có cấu trúc như sau:

1
2
3
4
5
6
7
typdef struct llnode {
........int key;
........struct llnode *next;
} llnode;

llnode *head;
llnode *tail;

Giờ bạn muốn kiểm tra xem trong danh sách này có khóa K hay không. Bạn có lẽ sẽ làm như sau:

1
2
3
4
5
6
7
8
9
llnode *itr = head;
while(itr != null){
........if(itr->key == K){
................printf("%d is in the list", K);
................break;
.........}else {
................iter = itr->next;
.........} 
}

Nhưng theo Knuth, chương trình này có thể làm nhanh hơn được. Nếu là bạn thì bạn sẽ làm thế nào?

#Đáp án
Hãy dừng ở đây nếu bạn muốn suy nghĩ thử cách của mình rồi đọc đáp án sau nhé
Cách Knuth đề xuất là thêm vào cuối danh sách một nút mới có khóa K cần tìm (mất thời gian O(1)) (chú ý trong câu hỏi mình có để nút llnode *tail). Sau khi thêm vào rồi, code có thể viết lại như sau:

1
2
3
4
5
6
7
8
9
10
add a node of key K after tail;
itr = head;
while(itr->key != K){
........itr = itr->next
}

if(itr->next != null){
.......printf("%d is in the list", K);
} 
remove the node after tail;

So với code trước, ta không cần phải check null cho con trỏ itr vì K luôn ở trong danh sách mới. Do đó tiết kiệm được N phép so sánh cho mỗi lần tìm kiếm không thành công (N là chiều dài của danh sách) trong khi đó chỉ mất thêm O(1) phép tính cho việc thêm và xóa nút khỏi danh sách.

Enjoy!!!