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)
13 trang |
Chia sẻ: lylyngoc | Lượt xem: 1734 | Lượt tải: 2
Bạn đang xem nội dung tài liệu Kiểm tra tính đúng đắn & tối ưu hóa chương trình, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Kiểm tra tính đúng đắn & tối
ưu hóa chương trình
Đặt vấn đề
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
Kỹ thuật dò tìm và phát hiện lỗi
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
Cách kiểm tra
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 hóa chương trình
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
Tối ưu hóa bộ nhớ
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
Tối ưu hóa thời gian thực hiện
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
Tránh gọi lặp một thủ tục
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
Thay đổi, bố trí (cấu trúc) dữ liệu
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
Nguyên lý phân cấp bộ nhớ
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
Nguyên lý đối xứng
Tính một phần rồi lấy đối xứng, không cần tính toàn bộ.
12
Tăng tính hiệu quả của chương trình
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