Tôi không có degree khoa học máy tính. Nhiều Rubyists cũng không. Vì vậy lâu nay tôi tránh học về big-O notation. Nó trông hơi quá giống higher math. Tôi nói: O(N^2). Thôi nào.
Thay vào đó, tôi học các quy tắc ngón tay:
- Tìm item cụ thể trong Hash nhanh hơn Array
- Tránh nested loops
- Cẩn thận accidental DB queries khi generate lists trong views
Các quy tắc này hay, nhưng trừ khi bạn hiểu TẠI SAO chúng hoạt động, bạn sẽ thấy mình làm sai lầm và gặp vấn đề hiệu năng không thể giải thích.
Tại sao nó quan trọng?
Big-O notation chỉ là một cách fancy để mô tả performance của code phụ thuộc vào lượng data nó đang xử lý như thế nào.
Performance nghĩa là một trong hai thứ: speed, hoặc ram usage. Trong lớp khoa học máy tính bạn sẽ gọi đây là "time complexity" và "space complexity." Big-O notation dùng cho cả hai, nhưng chúng ta sẽ tập trung vào speed ở đây, vì đó dường như là usage phổ biến hơn.
Bạn sẽ mong đợi xử lý array 100 items chậm hơn array 10 items. Nhưng chậm bao nhiêu? 10x, 100x? 1000x?
Đây không phải vấn đề lớn với dataset nhỏ, nhưng nếu app của bạn chậm theo cấp số nhân cho mỗi row trong database nó sớm trở thành vấn đề.
Trước khi đi vào chi tiết, tôi làm một biểu đồ nhanh cho thấy common big-Os với emoji cho thấy chúng sẽ làm bạn cảm thấy như thế nào khi data scale.
| Big O | Xếp hạng | Ý nghĩa |
|---|---|---|
| O(1) | 😎 | Speed không phụ thuộc vào kích thước dataset |
| O(log n) | 😁 | 10x data nghĩa là 2x thời gian hơn |
| O(n) | 😕 | 10x data nghĩa là 10x thời gian hơn |
| O(n log n) | 😖 | 10x data nghĩa là khoảng 20x thời gian hơn |
| O(n^2) | 😫 | 10x data tốn 100x thời gian hơn |
| O(2^n) | 😱 | High dilithium crystals are breaking up! |
Vì vậy khi ai đó nói Array#bsearch tốt hơn Array#find vì nó O(log n) vs O(n) bạn chỉ cần so sánh 😁 với 😕 và thấy họ có thể nói đúng.
Cho thứ gì đó robust hơn, xem Big-O Cheat Sheet
Giải mã ký hiệu
Bạn không phải nhớ tất cả giá trị Big-O khác nhau, miễn là bạn hiểu cách ký hiệu hoạt động.
Ví dụ, O(2^n) kinh khủng. Nếu chúng ta biểu diễn đó trong Ruby, nó có thể trông như:
# O(2^n) dịch sang Ruby
def o(n)
2 ** n # Đây là ruby cho 2^n
end
Vẫn không rõ? Thử rename method và argument thành thứ user-friendly hơn?
# O(2^n) dịch sang Ruby đẹp hơn
def execution_time(size_of_dataset)
2 ** size_of_dataset
end
Bạn có thể làm điều này cho tất 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
Bây giờ bạn biết cách ký hiệu hoạt động, hãy xem một số code Ruby điển hình và xem nó liên quan như thế nào.
O(1)
Khi chúng ta nói cái gì đó là O(1) nghĩa là speed của nó không phụ thuộc vào kích thước dataset.
Ví dụ, hash lookup times không phụ thuộc vào hash size:
# Tất cả nên mất cùng lượng thời gian
hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]
Đây là lý do chúng ta tend to nói hash nhanh hơn array cho dataset lớn.
O(n)
Ngược lại, Array#find là O(n). Nghĩa là Array#find phụ thuộc tuyến tính vào số item trong array. Array 100 items sẽ mất 100 lần lâu hơn để search hơn array 1 item
Nhiều code iterate over arrays follow pattern O(n).
(0..9).each do |i|
puts i
end
# Ví dụ này 1/2 speed của trước vì nó chứa 2x items.
(0..19).each do |i|
puts i
end
O(n^2)
Code fit profile O(n^2) tend to involve nested loops. Điều đó hợp lý nếu bạn nghĩ về nó. Một loop cho bạn O(n), loop nested thứ hai cho bạn O(n^2). Nếu — vì lý do unholy nào đó — bạn có 5-level nested loop, nó sẽ là O(n^5).
data = (0..100)
data.each do |d1|
data.each do |d2|
puts "#{ d1 }, #{ d2 }"
end
end
O(n log n)
O(n log n) code thường là kết quả của ai đó tìm cách clever để giảm lượng work mà thuật toán O(n^2) khác sẽ làm.
Bạn không thể chỉ nhìn code và nói nó là O(n log n). Đây là nơi higher math xuất hiện, và cũng là nơi tôi bow out.
Nhưng quan trọng phải biết về O(n log n) vì nó mô tả nhiều thuật toán search phổ biến. Array#sort của Ruby dùng thuật toán quicksort uy tín, mà trung bình là O(n log n) và worst-case là O(n^2)
Nếu bạn không quen quicksort, xem demonstration tuyệt vời này.
Đặt hết vào nhau: Database của bạn
Một trong những vấn đề phổ biến nhất với web application mới là chúng nhanh trên máy developer, nhưng trong production chúng chậm dần theo thời gian.
Điều này xảy ra vì lượng record trong database của bạn tăng theo thời gian, nhưng code của bạn yêu cầu DB làm các operation không scale tốt. i.e. O(n) hoặc tệ hơn.
Ví dụ, bạn có biết trong postgres, count queries luôn là O(n)?
# Buộc DB iterate qua mọi row của Users
# ...trừ khi bạn dùng Rails counter cache.
Users.count
Chúng ta có thể thấy điều này bằng cách dùng lệnh explain của postgres. Dưới đây, tôi dùng nó để lấy query plan cho count query. Như bạn thấy, nó plan làm sequential scan (nghĩa là looping) qua tất cả 104,791 rows trong 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)
Nhiều Rails idioms phổ biến có thể trigger unintentional sequential scans, trừ khi bạn cụ thể optimize database để ngăn chặn chúng.
# Yêu cầu DB sort toàn bộ bảng `products`
Products.order("price desc").limit(1)
# Nếu `hobby` không indexed, DB loop qua mỗi row của Users để tìm nó.
User.where(hobby: "fishing")
Bạn có thể dùng lệnh explain để thấy điều đó cũng vậy. Ở đây chúng ta thấy chúng ta đang làm sort (có thể quicksort) trên toàn bảng. Nếu có memory constraints, nó có thể chọn thuật toán sort khác với đặc điểm performance khác.
# 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)
Câu trả lời cho tất cả vấn đề này là, tất nhiên, indexing. Bảo database dùng index giống như trong Ruby, khi bạn dùng hash lookup O(1) thay vì array find O(n).
Hết rồi, các bạn ơi
Tôi hy vọng đây đã là giới thiệu hữu ích về Big-O notation và cách nó impact bạn như một ruby developer! Ping tôi @StarrHorne nếu bạn có câu hỏi.