Tôi không có bằng về khoa học máy tính. Rất nhiều người trong số chúng tôi Rubyists không. Vì vậy, trong một thời gian dài, tôi đã tránh tìm hiểu về ký hiệu big-O. Nó trông giống như một môn toán cao hơn một chút. Ý tôi là:O(N^2) . Nào.
Thay vào đó, tôi đã học các quy tắc ngón tay cái:
- Tìm một mục cụ thể trong Hash nhanh hơn trong Mảng
- Tránh các vòng lặp lồng nhau
- Đề phòng các truy vấn DB ngẫu nhiên khi tạo danh sách trong chế độ xem của bạn
Những quy tắc này rất hay, nhưng trừ khi bạn hiểu TẠI SAO chúng hoạt động, bạn sẽ thấy mình mắc sai lầm và gặp các vấn đề về hiệu suất không thể giải thích được.
Tại sao nó lại quan trọng?
Ký hiệu Big-O chỉ là một cách mô tả hiệu suất mã của bạn phụ thuộc vào lượng dữ liệu mà nó đang xử lý.
Hiệu suất có nghĩa là một trong hai điều:tốc độ hoặc mức sử dụng ram. Trong lớp khoa học máy tính, bạn sẽ gọi chúng là "độ phức tạp về thời gian" và "độ phức tạp về không gian". Ký hiệu Big-O được sử dụng cho cả hai, nhưng chúng ta sẽ tập trung vào tốc độ ở đây, vì đó dường như là cách sử dụng phổ biến hơn.
Bạn có thể mong đợi rằng việc xử lý một mảng 100 mục sẽ chậm hơn một mảng 10 mục. Nhưng bằng bao nhiêu? 10x, 100x? 1000 lần?
Đó không phải là vấn đề lớn với các tập dữ liệu nhỏ, nhưng nếu ứng dụng của bạn chậm hơn theo cấp số nhân đối với mỗi hàng trong cơ sở dữ liệu thì điều đó sẽ sớm trở thành vấn đề.
Trước khi chúng ta đi vào chi tiết, tôi đã tạo một biểu đồ nhanh hiển thị những điểm lớn thường gặp với biểu tượng cảm xúc cho thấy chúng sẽ khiến bạn cảm thấy như thế nào khi dữ liệu của bạn mở rộng.
| Big O | Xếp hạng | Ý nghĩa |
|---|---|---|
| O (1) | 😎 | Tốc độ không phụ thuộc vào kích thước của tập dữ liệu |
| O (log n) | 😁 | 10 lần dữ liệu có nghĩa là tăng gấp đôi thời gian |
| O (n) | 😕 | 10 lần dữ liệu có nghĩa là thời gian nhiều hơn 10 lần |
| O (n log n) | 😖 | 10 lần dữ liệu có nghĩa là thời gian nhiều hơn khoảng 20 lần |
| O (n ^ 2) | 😫 | 10 lần dữ liệu mất thêm 100 lần thời gian |
| O (2 ^ n) | 😱 | Các tinh thể dilithium đang vỡ ra! |
Vì vậy, khi ai đó nói Array#bsearch tốt hơn Array#find bởi vì nó là O(log n) so với O(n) bạn chỉ có thể so sánh 😁 với 😕 và thấy rằng họ có thể ở trên một cái gì đó.
Để có thứ gì đó chắc chắn hơn một chút, hãy xem Big-O Cheat Sheet
Giải mã Ký hiệu
Bạn không cần phải ghi nhớ tất cả các giá trị Big-O khác nhau, miễn là bạn hiểu cách ký hiệu hoạt động.
Lấy ví dụ, O(2^n) khủng khiếp khủng khiếp . Nếu chúng ta diễn đạt điều đó bằng Ruby, nó có thể trông như thế này:
# O(2^n) translated to Ruby
def o(n)
2 ** n # This is ruby for 2^n
end
Vẫn không rõ ràng? Còn nếu tôi đổi tên phương thức và đối số thành một thứ gì đó thân thiện với người dùng hơn thì sao?
# O(2^n) translated to prettier Ruby
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ả chúng:
# 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 cùng xem một số mã ruby điển hình và xem nó liên quan như thế nào.
O (1)
Khi chúng ta nói rằng một cái gì đó là O(1) nó có nghĩa là tốc độ của nó không phụ thuộc vào kích thước của tập dữ liệu của nó.
Ví dụ:thời gian tra cứu hàm băm không phụ thuộc vào kích thước hàm băm:
# These should all take the same amount of time
hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]
Đây là lý do tại sao chúng tôi có xu hướng nói rằng băm nhanh hơn mảng cho các tập dữ liệu lớn hơn.
O (n)
Ngược lại, Array#find là O(n) . Điều đó có nghĩa là Array#find phụ thuộc tuyến tính vào số lượng mục trong mảng. Mảng có 100 mục sẽ mất thời gian tìm kiếm lâu hơn 100 lần so với mảng có một mục
Rất nhiều mã lặp qua các mảng tuân theo O(n) họa tiết.
(0..9).each do |i|
puts i
end
# This example is 1/2 the speed of the previous because it contains 2x the items.
(0..19).each do |i|
puts i
end
O (n ^ 2)
Mã phù hợp với O(n^2) hồ sơ có xu hướng liên quan đến các vòng lồng nhau. Điều đó có ý nghĩa nếu bạn nghĩ về nó. Một vòng lặp cung cấp cho bạn O(n) , vòng lặp lồng nhau thứ hai cung cấp cho bạn O(n^2) . Nếu - vì một lý do xấu xa nào đó - bạn có một vòng lặp lồng nhau 5 cấp, 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) mã thường là kết quả của việc ai đó tìm ra một cách thông minh để giảm bớt khối lượng công việc mà một O(n^2) khác thuật toán sẽ làm.
Bạn sẽ không thể chỉ nhìn vào một đoạn mã và nói đó là O(n log n) . Đây là nơi môn toán cao hơn xuất hiện, và cũng là nơi tôi cúi đầu.
Nhưng điều quan trọng là phải biết về O(n log n) bởi vì nó mô tả rất nhiều thuật toán tìm kiếm phổ biến. Ruby's Array#sort sử dụng thuật toán quicksort đáng tin cậy, trung bình là O(n log n) và trường hợp xấu nhất là O(n^2)
Nếu bạn không quen với quicksort, hãy xem phần trình diễn xuất sắc này.
Kết hợp tất cả lại với nhau:Cơ sở dữ liệu của bạn
Một trong những vấn đề phổ biến nhất với các ứng dụng web mới là chúng chạy nhanh trên máy tính của nhà phát triển, nhưng trong quá trình sản xuất, chúng ngày càng chậm hơn.
Điều này xảy ra do số lượng bản ghi trong cơ sở dữ liệu của bạn tăng lên theo thời gian, nhưng mã của bạn đang yêu cầu DB thực hiện các hoạt động không đúng quy mô. I E. O(n) hoặc tồi tệ hơn.
Ví dụ:bạn có biết rằng trong postgres, số lượng truy vấn luôn là O(n) ?
# This makes the DB iterate over every row of Users
# ...unless you're using a Rails counter cache.
Users.count
Chúng ta có thể thấy điều này bằng cách sử dụng postgres explain yêu cầu. Dưới đây, tôi sử dụng nó để lấy kế hoạch truy vấn cho một truy vấn đếm. Như bạn có thể thấy, nó có kế hoạch thực hiện quét tuần tự (có nghĩa là lặp lại) trên tất cả 104.791 hàng 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)
Rất nhiều thành ngữ đường ray phổ biến có thể kích hoạt các lần quét tuần tự không chủ ý, trừ khi bạn đặc biệt tối ưu hóa cơ sở dữ liệu để ngăn chặn chúng.
# This asks the DB to sort the entire `products` table
Products.order("price desc").limit(1)
# If `hobby` isn't indexed, the DB loops through each row of Users to find it.
User.where(hobby: "fishing")
Bạn có thể sử dụng explain lệnh để xem điều đó là tốt. Ở đây chúng ta thấy rằng chúng ta đang sắp xếp (có thể là nhanh chóng) trên toàn bộ bảng. Nếu có các hạn chế về bộ nhớ, nó có thể đã chọn một thuật toán sắp xếp khác với các đặc tính hiệu suất khác nhau.
# 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)
Tất nhiên, câu trả lời cho tất cả những vấn đề này là lập chỉ mục. Việc nói với cơ sở dữ liệu để sử dụng một chỉ mục giống như trong Ruby, khi bạn sử dụng tìm kiếm băm O(1) thay vì tìm mảng O(n) .
Vậy thôi, các bạn
Tôi hy vọng đây là phần giới thiệu hữu ích về ký hiệu Big-O và tác động của nó đến bạn với tư cách là một nhà phát triển ruby! Vui lòng ping tôi @StarrHorne nếu bạn có bất kỳ câu hỏi nào.