Bài giảng Kỹ thuật lập trình nâng cao - Chương 4: Kỹ thuật lập trình tối ưu - Dương Thành Phết

Chƣơng 4: 
KỸ THUẬT LẬP TRÌNH TỐI ƢU 
KỸ THUẬT LẬP TRÌNH NÂNG CAO 
TRƢỜNG CAO ĐẲNG CNTT TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
Giảng Viên: ThS. Dƣơng Thành Phết 
Email: phetcm@gmail.com 
Website:  
Tel: 0918158670 – facebook.com/DuongThanhPhet 
1. CÁC BƢỚC ĐỂ XÂY DỰNG CHƢƠNG TRÌNH 
B1: Phân tích và xác định rõ bài toán. 
B2: Xây dựng thuật toán. 
B3: Viết chương trình. 
B4: Chạy và kiểm tra chương trình. 
B5: Bảo trì. 
2 
2. ĐÁNH GIÁ CHẤT LƢỢNG MỘT CHƢƠNG TRÌNH 
Đúng đắn - chính xác (correctness). 
Chắc chắn (robustness). 
Thân thiện (user friendliness). 
Khả năng thích nghi (adapability): Chương trình có khả 
năng để phát triển theo yêu cầu. 
Tính tái sử dụng (reuseability): Chương trình có thể 
dùng để làm một phần trong một chương trình khác. 
Tính hiệu quả (efficiency). 
Tính khả chuyển (porability): Khả năng chuyển đổi dễ 
dàng giữa các môi trường. 
Tính an toàn (security). 
Tính dừng (halt). 
3 
3.1. Phƣơng pháp Top - down 
 Phân rã vấn đề một cách có hệ thống từ trên xuống, 
(sử dụng cho quá trình phân tích và thiết kế hệ thống) 
 Quá trình phân rã bài toán được thực hiện theo từng 
mức khác nhau. 
 Mức thấp nhất - mức tổng quan: Cho thấy chức 
năng của hệ thống một cách tổng thể (hệ thống làm 
được gì?). 
 Mức phân tích: Các chức năng chính. 
 Quá trình phân tích tiếp tục phân rã cho tới khi nào 
nhận được mức đơn thể, và tiến hành cài đặt. 
4 
3. PHƢƠNG PHÁP PHÂN TÍCH BÀI TOÁN 
3.2. Phƣơng pháp Bottom - Up 
 Được sử dụng cho quá trình cài đặt hệ thống. 
 Phương pháp này: 
 Từ cái riêng tới cái chung 
 Từ các đối tượng thành phần ở mức cao tới mức 
thấp 
 Từ mức mođun đến mức tổng thể 
 Từ những mođun có sẵn lắp ghép thành mođun 
mới. 
5 
3. PHƢƠNG PHÁP PHÂN TÍCH BÀI TOÁN 
4. CÁC NGUYÊN LÝ KHI LẬP TRÌNH 
 Nguyên lý tối thiểu: Nắm vững các cấu trúc lệnh, kiểu 
dữ liệu, phép toán để viết chương trình. Tiếp theo, mới 
tìm hiểu những thư viện tiện ích của ngôn ngữ. 
 Nguyên lý địa phƣơng: Hạn chế sử dụng biến toàn cục 
 Nguyên lý nhất quán: Thao tác phải phù hợp với dữ liệu 
 Nguyên lý an toàn: Tránh mọi lỗi trong khi xây dựng 
chương trình, nên phát hiện và sửa lỗi ở từng bước. 
6 
5. CÁC PHƢƠNG PHÁP LẬP TRÌNH 
 Tuần tự 
 Thủ tục 
 Đơn thể (module) 
 Hướng đối tượng 
7 
6.1. Đặ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) 
8 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
6.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. 
9 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
6.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. 
10 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
6.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. 
11 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
6.5.Tối ƣu hóa bộ nhớ 
Giảm thiểu vùng nhớ làm việc 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ớ 
12 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
6.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. 
13 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
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. 
 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 
lệnh 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 không làm sai chương trình) 
 Thực hiện hợp nhất các vòng lặp có thể. 
14 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
 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/thủ tục. Giảm 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); 
Hàm P() 
{ 
 for(i=1; i<n; i++) 
} 
Gọi Hàm P(); 
15 
Sau khi tối ưu: 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
 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. 
16 
6. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 
7.1. Vấn đề 
 Nền tảng của lập trình là thiết kế giải thuật. 
 Trong việc thiết kế cấu trúc logic của chương trình, 
điều quan trọng là dùng giải thuật nào cho thích hợp 
 Chọn giải thuật để sử dụng là một trong những tiêu 
chuẩn quan trọng 
 Việc sử dụng giải thuật hiệu quả và dễ hiểu giúp gia 
tăng tốc độ thực hiện và giảm những lỗi tiềm ẩn. 
 Do vậy giải thuật là một nhân tố chính yếu quyết 
định hiệu suất của hệ thống. 
17 
7. THIẾT KẾ GIẢI THUẬT 
7.2. Các loại giải thuật 
 Tìm kiếm 
 Sắp xếp. 
 Đệ quy. 
 Xử lý chuỗi ký tự. 
 Xử lý file. 
 Đồ họa. 
 Đồ thị. 
 V. v 
18 
7. THIẾT KẾ GIẢI THUẬT 
7.3. Các phƣơng pháp xây dựng giải thuật 
 Giải thuật là một tập các quy tắc được định nghĩa áp 
dụng để giải quyết một vấn đề. 
 Giải thuật và cấu trúc dữ liệu có mối quan hệ chặt chẽ 
với nhau. Cấu trúc dữ liệu xác định khung nền cho giải 
thuật với một độ tin cậy chắc chắn. 
 Khi giải quyết một bài toán trên máy tính ta phải chú 
trọng đến hai vấn đề Cấu trúc dữ liệu và giải thuật. 
Giải thuật phản ánh cách xử lý, còn đối tượng xử lý là dữ 
liệu, với cấu trúc dữ liệu được chọn, sẽ có những giải 
thuật tương ứng, khi cấu trúc dữ liệu thay đổi thường giải 
thuật cũng thay đổi theo. 
19 
7. THIẾT KẾ GIẢI THUẬT 
Ví dụ: 
 Trong việc xử lý cấu trúc mảng, dữ liệu có thể được tìm 
kiếm và cập nhật dễ dàng, nhưng phải mất thời gian để 
chèn hay xoá dữ liệu. 
 Bởi vì dữ liệu trong mảng được tổ chức liên tiếp nhau, 
thao tác chèn hay xoá dữ liệu thì tương đối phức tạp 
bởi việc dịch chuyển các dữ liệu liên quan về sau hoặc 
về phía trước. 
 Bằng cách dùng cấu trúc kiểu danh sách, việc chèn và 
xoá dữ liệu thì dễ dàng hơn, dữ liệu không cần phải 
dịch chuyển mà chỉ cần thay đổi con trỏ. 
20 
7. THIẾT KẾ GIẢI THUẬT 
7.4. Biểu Diễn Giải Thuật 
Có 2 phương pháp chính biểu diễn giải thuật: 
 Pseudocode (mã giả) 
 Flowchart (lưu đồ) 
Khi thiết kế giải thuật phải mô tả rõ: 
 Đầu vào 
 Đầu ra (kết quả) 
Mô tả giải thuật 
21 
7. THIẾT KẾ GIẢI THUẬT 
Các từ khóa biểu diễn giải thuật bằng mã giả 
 IF ... THEN ENDIF 
 IF ... THEN ... ELSE ... ENDIF 
 DO WHILE  ENDDO 
 DO  UNTIL  
22 
7. THIẾT KẾ GIẢI THUẬT 
Read schedule file for tables to be loaded 
IF any tables to be loaded THEN 
 Call XYZ to load tables 
ENDIF 
IF (value > low-value) AND (value < high-value) THEN 
 Update table 
ELSE 
 Display error message 123 on screen 
ENDIF 
DO 
 Get field value 
 Determine screen-field-number 
 CASE screen-field-number OF 
 1: Perform edits for field-1 
 2: Perform edits for field-2 
 OTHERWISE 
 Display error message 112 
 ENDCASE 
UNTIL no error in field values 23 
7. THIẾT KẾ GIẢI THUẬT 
Các ký hiệu Flowchart 
Bắt đầu/ kết thúc 
Xuất/ in 
Rẽ nhánh 
Luồng xử lý 
Khối xử lý 
Nhập 
Điều 
kiện 
Giá trị trả về 
Điểm nối 
24 
7. THIẾT KẾ GIẢI THUẬT 
Ví dụ: Giải và biện luận: ax+b=0 
25 
7. THIẾT KẾ GIẢI THUẬT 
26 
 The End.