Độ phức tạp thuật toán: Ảnh hưởng của O lớn tới performance

Bất cứ ai trong lúc tối ưu code ruby luôn nhập tâm nằm lòng các nguyên tắc:

• Tìm kiếm trên hash luôn nhanh hơn tìm kiếm trên array
• Tránh các vòng lặp lồng nhau
• Hạn chế query database khi hiển thị một list trên view

Các nguyên tắc này rất hiệu quả, dễ nhớ và dễ áp dụng. Nhưng không việc không hiểu được vì sao lại có những quy luật đấy, và chúng hoạt động như thế nào, ta sẽ dễ mắc phải những sai lầm không đáng có. Bản thân tôi đã gặp trường hợp coder sử dụng hash để tăng tốc nhưng lại tra cứu hash như một array, làm triệt tiêu tất cả lợi thế tốc độ của hash.

Thật may là tôi ngành khoa học máy tính tôi theo học đại học lại lấy những lý thuyết về độ phức tạp thuật toán làm nền tảng và chữ O lớn là mục tiêu nghiên cứu, nên dù muốn hay không, tôi vẫn luôn bị ám ảnh về việc mỗi dòng code viết ra, O lớn là bao nhiêu và làm thế nào để làm cho O lớn nhỏ nhất.

Bài viết này nói về khái niệm O lớn trong thực tế, hy vọng cung cấp cho mọi người cái nhìn cơ bản nhất về O lớn và áp dụng trong các bài toán thực tế. Code trong bài được thể hiện bằng Ruby, nhưng lý thuyết về độ phức tạp thuật toán có thể được áp dụng ở tất cả các ngôn ngữ.

O lớn là gì?

Chắc hẳn sau khi đọc qua mấy dòng trên trong đầu bạn sẽ nảy ra nhiều câu hỏi: O lớn là gì? O lớn có gì mà khiến cho tay viết bài ám ảnh đến vậy? O lớn là ký hiệu mô tả độ phức tạp của một thuật toán, hay nói đơn giản là performace của code trên một database bất kỳ. O lớn đại diện cho trường hợp xấu nhất có thể sảy ra, hay cận trên của thuật toán. Cùng với O lớn, còn có các ký hiệu Ω(omega) và Θ(teta) đại diện cho trường hợp tốt nhất và trường hợp trung bình.

Performance thường được hiểu là khái niệm bao gồm hai tiêu chí: tốc độ xử lý và bộ nhớ cần sử dụng. Trong ngành khoa học máy tính hai khái niệm này thường được gọi là "độ phức tạp thời gian" và "độ phức tạp không gian". Khái niệm O lớn có thể dùng cho cả hai loại độ phức tạp trên, nhưng với độ lớn gần như vô hạn của phần cứng bộ nhớ và mục tiêu chính của chúng ta thường là cải thiện tốc độ, nên O lớn thường được dùng với khái niệm thời gian.

Với những bài toán nhỏ, O lớn không ảnh hưởng nhiều đến thời gian tính toán. Nhưng khi lượng dữ liệu tăng dần, O lớn sẽ quyết định tốc độ xử lý tăng tương ứng bao nhiêu lần.

Dưới đây là một bảng tra cứu nhanh về các giá trị O lớn thường gặp, rank đánh giá O lớn trong bảng chính là cái mặt của bạn khi gặp những thuật toán như thế.

Vậy nên nếu nói hàm tìm kiếm Array#bsearch tốt hơn Array#find bởi vì O(log n) tốt hơn O(n) thì ta chỉ cần so sánh hai mức rank 😁 và 😕 là có thể hiểu được.

Giải nghĩa các giá trị O lớn

Ta hoàn toàn có thể tính toán được O lớn của các thuật toán về mặt toán học nên việc ghi nhớ giá trị O lớn cho từng thuật toán là không cần thiết (tuy nhiên tôi khuyến khích bạn nên ghi nhớ phương pháp hoạt động của một số thuật toán nổi tiếng và tự phân tích O lớn cho các thuật toán này).

Ví dụ với trường hợp tệ nhất vừa kể đến O(2^n). Nếu viết bằng một hàm Ruby thì nó sẽ có dạng:

def o2 n
  2 ** n
end

Từ đó ta có thể viết được hàm ước lượng thời gian chạy cho các thuật toán O(2^n):

# Thời gian chạy của O(2^n)
def execution_time size_of_dataset
  2 ** size_of_dataset
end

Tương tự với các giá trị O lớn khác:

# O(1)
def o1_execution_time size_of_dataset
  1
end

# O(n)
def on_execution_time size_of_dataset
  size_of_dataset
end

# O(n^2)
def on2_execution_time size_of_dataset
  size_of_dataset * size_of_dataset
end

...etc

Phía trên là tóm tắt một số lý thuyết về O lớn, dưới đây là các trường hợp áp dụng thực tế và các ví dụ liên quan.

O(1)

Khi ta nói một thuật toán nào đó có độ phức tạp O(1) có nghĩa là tốc độ xử lý không phụ thuộc vào độ lớn của bộ dữ liệu. Tìm kiếm kết quả của một bài toán trên bộ dữ liệu đều có tốc độ như nhau, giống như được đọc trực tiếp từ ô nhớ trên RAM.

Ví dụ, tìm kiếm một phần tử trong hash theo key không phụ thuộc vào số phần tử trong hash. Ta có thể nói rằng các thao tác dưới đây có thời gian tương đương:

hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]

Đây là lý do vì sao hash thường được ưu tiên sử dụng so với array trong những bộ dữ liệu lớn.

O(n)

Thuật toán được sử dụng trong hàm Array#find có độ phức tạp O(n). Điều này có nghĩa là thời gian xử lý của thuật toán Array#find phụ thuộc tuyến tính vào số phần tử trong array. Việc tìm kiếm trong một array với 100 phần tử có thể tốn thời gian gấp 100 lần so với array một phần tử.

Phần lớn các đoạn code sử dụng vòng lặp sẽ có độ phức tạp O(n).

User.all.each do |user|
  puts user.name
end

O(n^2)

Các đoạn code có độ phức tạp O(n^2) thường là các vòng lặp lồng nhau. Điều này rất dễ hiểu và có thể tính toán được: với mỗi vòng lặp có độ phức tạp O(n), vậy với một vòng lặp thứ hai được thực hiện trong mỗi vòng lặp trên ta có độ phức tạp là O(n^2). Vậy nên, nếu ta có 5 vòng lặp lồng nhau, độ phức tạp ta có là O(n^5).

Post.all.each do |post|
  puts post.title
  post.comments.each do |comment|
    puts comment.content
  end
end

Fun fact: Các phép cộng trừ thông thường là vô nghĩa trong lý thuyết tính toán, vậy nên ta hoàn toàn có thể viết rằng O(2n^3 - 4n^2 + 1) = O(n^3)

O(n log n)

Các thuật toán O(n log n) thường là kết quả của một thuật toán tối ưu do một nhà toán học nào đó nghĩ ra để cải thiện tốc độ của một bài toán mà cách thông thường (vét cạn) phải mất thời gian cỡ O(n^2).

Thường thì khó mà có thể chỉ nhìn qua là biết được một đoạn code có phải là O(n log n) hay không mà đòi hỏi phải tính toán và chứng minh chi tiết.

Dù vậy, điều quan trọng cần phải ghi nhớ là các thuật toán tìm kiếm nổi tiếng thường có kết quả là O(n log n). Hàm Ruby Array#sort sử dụng một biến thể của thuật toán quicksort, có độ phức tạp cận trên là O(n log n) và trung bình là Θ(n^2)

Áp dụng vào truy vấn trong database

Một vấn đề thường thấy của các bạn developer là code chạy ngon lành trên máy của dev, nhưng khi đưa code lên staging hoặc production thì lăn ra lỗi, hoặc chạy chậm đến mức timeout error.

Điều này sảy ra vì số lượng bản ghi thật trên database sẽ lớn lên theo thời gian, nhưng code lại yêu cầu database thực hiện những query có độ phức tạp lớn, mà trong bộ dữ liệu nhỏ thì chênh lệch là không đáng kể.

Ví dụ, nếu sử dụng postgresSQL, count queries luôn tốn thời gianO(n). Ví dụ chỉ với đoạn code đơn giản:

# Dòng code này tốn thời gian O(n) nếu sử dụng postgresSQL
User.count

Ta có thể dễ dàng thấy được điều này bằng lệnh EXPLAIN của postgres. Như đã thể hiện ở dưới, hệ quản trị CSDL này sẽ thực hiện một lượt quét toàn bộ 104,791 dòng trong bảng. Còn nếu sử dụng mySQL thì thời gian chỉ mất O(1) vì mySQL luôn có một giá trị lưu tổng số bản chi cho mỗi bảng.

# EXPLAIN SELECT COUNT(*) FROM users;
                           QUERY PLAN
-----------------------------------------------------------------
 Aggregate  (cost=6920.89..6920.90 rows=1 width=0)
   ->  Seq Scan on users  (cost=0.00..6660.71 rows=104701 width=0)
(2 rows)

Rất nhiều các cấu trúc thường dùng của Rails tự động kích hoạt các lượt quét liên tục toàn bộ bảng, trừ khi ta thực hiện tối ưu database để ngăn chặn việc này:

# Dòng code này yêu cầu phải sắp xếp lại cả bảng `products`
Products.order("price desc").limit 1

# Nếu trường `hobby` không được đánh index, SQL sẽ kiểm tra tất cả các bản ghi trong bảng `users` để tìm kiếm.
User.where hobby: "fishing"

Ta có thể sử dụng lệnh EXPLAIN để kiểm tra. Dưới đay là một lệnh yêu cầu sắp xếp (quicksort) cả bảng:

# EXPLAIN SELECT * FROM users ORDER BY nickname DESC LIMIT 1;
                               QUERY PLAN
-------------------------------------------------------------------------
 Limit  (cost=7190.07..7190.07 rows=1 width=812)
   ->  Sort  (cost=7190.07..7405.24 rows=104701 width=812)
         Sort Key: nickname
         ->  Seq Scan on users  (cost=0.00..6606.71 rows=104701 width=812)

Giải pháp để tăng tốc thao tác này là đánh index. Yêu cầu SQL kiểm tra trên index thay vì trên bảng cũng tương đương với việc yêu cầu Ruby kiểm tra trên hash thay vì array.