Bài giảng Kỹ thuật lập trình nâng cao: Chương 8 - Trần Minh Thái

Chia sẻ: Y Nhân | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

41
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Kỹ thuật lập trình nâng cao - Chương 8: Kiểm tra tính đúng đắn và tối ưu hóa chương trình" cung cấp cho người học các kiến thức: Kỹ thuật dò tìm và phát hiện lỗi, cách kiểm tra, tối ưu hóa chương trình, tối ưu hóa bộ nhớ,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình nâng cao: Chương 8 - 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ụ: Sau khi tối ưu: Hàm P(i) Hàm P() { { … for(i=1; i
* 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