Ứng dụng triết lý của Quy hoạch động để Hiển thị 10 bài viết mới nhất

Quay đi, quay lại thì tìm kiếm và sắp xếp là hai thuật toán được sử dụng nhiều nhất trong khi thiết kế web.

Bài toán của chúng ta là: Chúng ta có 10,000 posts và khoảng 1,000 requests truy cập cùng một lúc. Yêu cầu: hiển thị ra 10 bài viết mới nhất.

Thuật toán mặc định được sử dụng trong các diễn đàn VBB là sắp xếp chúng bằng lệnh order by của Hệ quản trị Cơ sở dữ liệu. Vì vậy, độ phức tạp của thuật toán là: O(1,000*10*log(10,000)). Rất lớn vì phải truy cập dữ liệu vào thiết bị có tốc độ truy xuất thấp như ổ cứng (database là một file nằm trong ổ cứng – ở đây, nếu sử dụng thuật toán đó, chúng ta bắt buộc phải truy cập toàn bộ bản ghi => rất tệ). (Độ phức tạp trong bài viết này, mình không viết ở dạng O(m*10*log(n)), bởi khi ta cho m, n tổng quát, chúng ta không hình dung ra độ lớn của thuật toán khi chạy trên máy tính cụ thể)

Muốn làm bài này: Chúng ta dựa vào đặc tính riêng của bài toán. Bài toán này chỉ yêu cầu tìm ra 10 bài viết mới nhất.

Nếu chúng ta lại sử dụng thuật toán tổng quát trong trường hợp này thì quả thật quá lãng phí.

Giải pháp: Dùng triết lý của thuật toán Quy hoạch động vào bài toán này. Ứng dụng triết lý Quy hoạch động ở đây không có nghĩa là thiết kế một thuật toán Quy hoạch động đề giải bài này.

Vậy triết lý của Quy hoạch động là gì? Là: các dữ liệu cần thiết cho việc xử lý nên để sẵn trong bộ nhớ. Như vậy, ta chỉ cần gọi dữ liệu đó ra mà không cần thực hiện thêm thuật toán gì cả.

Ứng dụng cho bài toán Hiển thị 10 bài viết mới nhất: Các bạn tạo ra một bảng newposts với các thuộc tính y hệt bảng post của VBB. Bảng này có tối đa là 10 bản ghi mà thôi. Mỗi khi thực hiện một thao tác tạo mới một post hoặc update một post. Ngoài việc, chúng ta ghi nó vào bảng post, đồng thời chúng ta cũng ghi nó vào bảng newposts. Bảng newposts cần có thêm một trường nữa là trường Rank. Rank = 1 là mới nhất. Rank = 10 là cũ nhất. (Trong thuật toán này chúng ta chỉ truy cập 10 bản ghi thôi => Hay là ở chỗ đó)

Khi thêm một bài thì:
– Chỉnh sửa các bài từ Rank1 tới Rank9 lên 1.
– Post mới được update cho rank10. Chỉnh rank10 thành rank1.

Vậy với 1,000 requests cùng lúc yêu cầu hiển thị 10 bài viết mới nhất thì độ phức tạp là:

O(1,000*10log(10)). Nhỏ hơn ban đầu rất nhiều.

Hạn chế: Phương pháp này bỏ qua những nguyên tắc thiết kế của cơ sở dữ liệu, phục vụ vào tính nhanh. Nếu giờ chúng ta đổi tên tài khoản user tạo bài đó thì sẽ có sự khác biệt giữa các bản ghi trong bảng post và newposts.

Ý nghĩa: Do phục vụ tính nhanh, cũng là một cách để chống phần nào đó DDOS thì cái giá đó chấp nhận được.

Bạn có thể sửa chương trình nhanh chóng để có thể in ra 10 bài viết mới nhất mà không bị trùng tên nhau. Rất dễ.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: