Đọc Mã để Tìm Tốc độ Tăng trưởng
Đánh giá Mã để tính Đúng đắn vs Đánh giá Mã để tính Độ phức tạp
Đánh giá mã để tính đúng đắn bắt các lỗi logic: điều kiện sai, chỉ số sai một, kiểm tra null bị thiếu. Đánh giá mã có nhận thức về độ phức tạp bắt một loại khiếm khuyết khác: mã hoạt động đúng ở N = 100 nhưng phát triển thảm hại ở N = 100.000.
Bài học này kết nối với một cuộc điều tra sâu hơn trong khóa học unhamming: Chương Bị thiếu: Độ phức tạp Thuật toán bao gồm Big O trong bối cảnh khiếm khuyết sản xuất, & MOAD-0001: Khiếm khuyết Lắng đọng ánh xạ mẫu trên 60+ hệ sinh thái phần mềm.
Hai Heuristic Đánh giá
Vòng lặp lồng nhau nhân độ phức tạp. Hai vòng lặp lồng nhau trên N mục tạo ra O(N²). Ba tạo ra O(N³). Khi đánh giá: đếm độ sâu lồng vòng lặp trước tiên.
Vùng chứa tuần tự bên trong vòng lặp nóng. Bất kỳ kiểm tra .contains(), .includes(), .find() hoặc in list nào bên trong vòng lặp đều tốn O(N) trên mỗi kiểm tra. Qua N lần lặp: O(N²) tổng cộng. Mẫu này xuất hiện trong mã sản xuất trên hàng chục hệ sinh thái — trình biên dịch GHC Haskell, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot. Cùng một sai lầm, các cơ sở mã khác nhau.
Đánh giá: find_duplicates
Đánh giá hàm Python sau đây về độ phức tạp:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: Khiếm khuyết Lắng đọng
Cùng một Khiếm khuyết, Sáu Mươi Hệ sinh thái
Mẫu if x not in list: list.append(x) bên trong vòng lặp xuất hiện — đã xuất hiện — trong mã sản xuất trên hàng chục hệ sinh thái phần mềm:
- GHC (trình biên dịch Haskell): bộ phân giải phụ thuộc, O(N²) ở N = 50.000 gói, xây dựng trong 17 phút
- Python pip: giải quyết xung đột phụ thuộc
- Apache Maven: khử trùng lặp đường dẫn lớp
- Rust Cargo: thống nhất tính năng
- trình biên dịch TypeScript: phân giải mô-đun
- Godot / Redot game engine: duyệt qua biểu đồ nút
Không có đội nào mắc lỗi. Họ viết mã chính xác ở N nhỏ. N phát triển. Mã hóa đơ. Mẫu có tên: MOAD-0001, Khiếm khuyết Lắng đọng. Trầm tích: đúng, vô hại trong các lớp mỏng. Theo thời gian, các lớp tích tụ và cứng lại.
Sửa chữa
Trong mọi trường hợp: thay thế vùng chứa tuần tự bằng vùng chứa băm. Một dòng. Không có thay đổi hành vi ở các đầu vào đúng. Tăng tốc độ 100–1.000×.
Sửa chữa hoạt động vì hai hoạt động cần phải nhanh:
1. Kiểm tra thành viên: phần tử này đã được nhìn thấy trước đây chưa?
2. Đầu ra theo thứ tự: trả lại các phần tử theo thứ tự chúng xuất hiện.
Một tập hợp xử lý (1) trong O(1). Nếu (2) cũng quan trọng, hãy giữ một danh sách riêng biệt cho đầu ra có thứ tự và một tập hợp cho kiểm tra thành viên. Hai cấu trúc dữ liệu, mỗi cái làm một công việc.
Phản hồi cho Nhà đánh giá
Một yêu cầu kéo sửa MOAD-0001 trong hàm duyệt đồ thị của dự án. Một nhà đánh giá bình luận:
> "Các tập hợp không bảo toàn thứ tự chèn — điều này thay đổi hành vi."
Mẫu Phân tích Phỏng vấn
Định dạng Dự kiến
Phân tích độ phức tạp thuật toán xuất hiện trong các cuộc phỏng vấn kỹ sư phần mềm. Một câu trả lời mạnh mẽ tuân theo mẫu bốn phần:
1. Nêu rõ độ phức tạp hiện tại — O(?) cho thời gian, O(?) cho không gian.
2. Giải thích tại sao — xác định cấu trúc cụ thể chịu trách nhiệm (vòng lặp lồng nhau, quét tuyến tính trong vòng lặp, nhánh đệ quy).
3. Đề xuất một tối ưu hóa — đặt tên cho thay đổi và cấu trúc dữ liệu hoặc thuật toán nó giới thiệu.
4. Nêu rõ độ phức tạp mới — sau khi sửa chữa, độ phức tạp thời gian & không gian là gì?
Ví dụ:
Mã: [hàm kiểm tra thành viên trong danh sách bên trong vòng lặp]
Hiện tại: O(N²) — `item in seen_list` là O(N) mỗi kiểm tra × N lần lặp
Tối ưu hóa: thay thế seen_list bằng seen_set (bảng băm)
Sau: O(N) — kiểm tra thành viên bảng băm là O(1)Kỹ năng này chuyển tiếp vào các phỏng vấn: đánh giá mã có nhận thức về độ phức tạp, thiết kế kiến trúc, gỡ lỗi hiệu suất, kiểm toán bảo mật. Bất kỳ hệ thống nào xử lý các đầu vào có kích thước biến đổi đều được hưởng lợi từ nó.
Bài học này liên kết chuyển tiếp với khóa học unhamming, áp dụng mẫu chính xác này để điều tra khiếm khuyết sản xuất trên 60+ dự án mã nguồn mở.
Phỏng vấn: Phân tích has_common_element
Áp dụng định dạng phỏng vấn bốn phần cho hàm này:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False