89: Sử dụng đúng thuật toán và cấu trúc dữ liệu

Một ngân hàng lớn với nhiều chi nhánh phàn nàn rằng các máy tính mới mà họ mua cho các giao dịch viên chạy quá chậm. Vào thời điểm đó ngân hàng điện tử và cây ATM không phổ biến như bây giờ. Mọi người đến ngân hàng thường xuyên hơn, và những chiếc máy tính chậm chạp đang khiến mọi người phải chờ đợi. Do đó, ngân hàng đe dọa sẽ phá vỡ hợp đồng với nhà cung cấp.

Nhà cung cấp đã gửi đến một chuyên gia phân tích và điều chỉnh hiệu suất để xác định nguyên nhân của sự chậm trễ. Anh ta sớm tìm thấy một chương trình tiêu thụ gần như toàn bộ dung lượng CPU. Sử dụng một công cụ định hình, anh ta phân tích chương trình và tìm thấy thủ phạm:

Và một chuỗi trung bình gồm hàng nghìn ký tự. Code (được viết bởi ngân hàng) đã nhanh chóng được sửa đổi, và các giao dịch viên sống hạnh phúc mãi mãi về sau ….

Không phải là có cách tốt hơn việc sử dụng code được chia tỷ lệ không cần thiết theo phương pháp bậc hai sao? Mỗi hàm strlen đi qua một trong số hàng ngàn ký tự trong chuỗi để tìm ký tự null kết thúc. Chuỗi, ngược lại, không bao giờ thay đổi. Bằng cách xác định trước độ dài của nó, lập trình viên có thể lưu hàng nghìn cuộc gọi vào strlen (và hàng triệu lần thực hiện vòng lặp):

Mọi người đều biết câu ngạn ngữ “Trước hết hãy làm cho nó hoạt động, sau đó mới làm cho nó hoạt động nhanh” để tránh những cạm bẫy của tối ưu hóa vi mô. Nhưng ví dụ nêu trên sẽ khiến bạn tin rằng lập trình viên đã tuân theo Machiavellian adagio “Trước tiên hãy làm cho nó hoạt động chậm”.

Sự thiếu suy nghĩ này bạn có thể đã bắt gặp nhiều lần. Và nó không chỉ là một thứ “không- phát- minh- lại- bánh xe”. Đôi khi các lập trình viên mới bắt tay vào làm mà không thực sự suy nghĩ và đột nhiên họ “phát minh ra” bubble sort. Họ thậm chí còn khoe khoang về nó.

Mặt khác của việc chọn thuật toán phù hợp là lựa chọn cấu trúc dữ liệu. Nó có thể tạo ra sự khác biệt lớn: Sử dụng danh sách được liên kết với bộ sưu tập một triệu mục bạn muốn tìm kiếm- so với cấu trúc dữ liệu hoặc hệ nhị phân- sẽ có tác động lớn đến sự đánh giá của người dùng đối với chương trình của bạn.

Các lập trình viên không nên phát minh lại bánh xe, mà nên sử dụng các thư viện hiện có. Nhưng để có thể tránh các vấn đề như của ngân hàng, họ cũng cần được giáo dục về các thuật toán và cách chúng mở rộng quy mô. Có phải đó chỉ là trò chơi trong các trình soạn thảo văn bản hiện đại khiến chúng chậm như các chương trình trường học cũ như Wordstar vào những năm 1980? Nhiều người nói tái sử dụng trong lập trình là tối quan trọng. Tuy nhiên, các lập trình viên nên biết khi nào, cái gì và làm sao có thể sử dụng lại. Để có thể làm điều đó, họ cần có kiến thức về miền, các thuật toán và cấu trúc dữ liệu.

Một lập trình viên giỏi cũng nên biết khi nào cần sử dụng một thuật toán phức tạp.

Ví dụ: nếu miền ra lệnh không bao giờ có nhiều hơn năm vật phẩm (như số xúc xắc trong trò Yahtzee), bạn biết rằng bạn chỉ có thể sắp xếp tối đa năm vật phẩm. Trong trường hợp đó, bubble sort thực sự là cách hiệu quả nhất để sắp xếp các mục. Ai rồi cũng có lúc gặp vận.

Vì vậy, hãy đọc những cuốn sách hay- và chắc chắn rằng bạn hiểu chúng. Nếu bạn thực sự đọc hiểu “Nghệ thuật lập trình máy tính” của Donald Knuth, bạn có thể gặp may mắn: Tìm một lỗi sai của tác giả và nhận được tờ séc trị giá 2,56 $ của Don Knuth.