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 - 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