Bài giảng Kỹ thuật lập trình - Chương 8: Kiểm tra tính đúng đắn và tối ưu hóa chương trình - Trần Minh Thái

TRẦN MINH THÁI minhthai@itc.edu.vn 1 *Nguồn gốc các sai sót có 3 loại: *Dữ liệu: Dùng bộ kiểm tra dữ liệu *Cú pháp: Dùng trình biên dịch *Ngữ nghĩa è Có 2 cách kiểm lỗi chương trình: kiểm (testing) và sửa (debugging) 2 Nguyên tắc * Bảo đảm mọi trường hợp đều được kiểm tra. * Thường bị lỗi ở những ngã rẻ, phải duyệt qua ít nhất một lần. * Một chương trình cần test nhiều lần. * Kiểm tra từng môđun một để giảm độ phức tạp. 3 Tạo bộ dữ liệu thử sao cho thỏa 1 trong 4 cách sau: * Kiểm tra toàn bộ các nhánh của chương trình: Mỗi lệnh của chương trình đều chạy qua ít nhất một lần. * Kiểm tra ngẫu nhiên. * Kiểm tra ở những điểm nút: lựa chọn, lặp, * Chèn lệnh kiểm tra logic ở mỗi đoạn (dòng) lệnh. 4 *Tối ưu thời gian: Tăng không gian lưu trữ, thuật toán không đổi, đổi cấu trúc dữ liệu và cấu trúc chương trình. *Tối ưu không gian: Tăng thời gian, thuật toán không đổi, đổi cấu trúc dữ liệu và cấu trúc chương trình. *Tối ưu thời gian và không gian: Thuật toán thay đổi. 5 Giảm thiểu vùng nhớ làm việc cần cho chương trình. *Nguyên lý nén dữ liệu *Giảm khoảng trống: Biểu diễn danh sách tọa độ các giá trị có cùng giá trị. *Mã lặp: Những dữ liệu thường xuyên lặp lại dùng mã lặp Runlength-Coding để nén. *Mã hóa dựa vào tần suất. *Mã nền. *Ánh xạ co dữ liệu. *Nguyên lý dùng công thức thay bộ nhớ 6 Kỹ thuật tối ưu việc rẽ nhánh Sắp xếp các biểu thức điều kiện theo thứ tự: * Nếu dùng phép and để kết hợp các biểu thức thì sắp xếp các biểu thức theo xác suất sai giảm dần. * Nếu dùng phép or để kết hợp các biểu thức thì sắp xếp các biểu thức theo xác suất đúng giảm dần. 7 Kỹ thuật tối ưu các vòng lặp * Tách các lệnh không phụ thuộc vào chỉ số lặp ra khỏi vòng lặp. Thay các phép nhân thành phép cộng nếu được. * Giảm số toán tử phức tạp trong vòng lặp nhờ các biến phụ. * Giảm số vòng lặp chương trình. Thực hiện nhiều hơn trong mỗi vòng lặp. * Vòng lặp nào có số lần lặp ít sẽ nằm ngòai vòng lặp có số lần lặp nhiều hơn: Hoán đổi thứ tự các vòng lặp mà không làm sai ý nghĩa chương trình. * Thực hiện hợp nhất các vòng lặp có thể. 8 *Giảm tối đa việc gọi các thủ tục. Hãy làm nhiều nhất trong một vòng lặp, trong một thủ tục. Giảm thiểu tối đa việc gọi đến các thủ tục. *Ví dụ: Hàm P(i) { } for(i=1; i<n; i++) Gọi Hàm P(i); Sau khi tối ưu: Hàm P() { for(i=1; i<n; i++) } Gọi Hàm P(); 9 * Dùng biến phụ thay cho các biểu thức phải tính toán nhiều. * Dùng bảng tra (table - lookup) để tính toán: Cố gắng lập bảng tính toán sẵn cho các trường hợp phổ biến. 10 Dữ liệu thường được truy cập phải ở vị trí được truy cập tốt nhất: Tổ chức ở bộ nhớ trong hoặc bộ nhớ ngoài. 11 Tính một phần rồi lấy đối xứng, không cần tính toàn bộ. 12 *Phân tích chương trình thành các chương trình con. *Tính độc lập của chương trình con càng cao càng tốt. 13