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

Bài giảng Kỹ thuật lập trình nâng cao - Chương 4 trình bày về kỹ thuật lập trình tối ưu. Các nội dung chính trong chương này gồm có: Các bước để xây dựng chương trình, đánh giá chất lượng một chương trình, phương pháp phân tích bài toán, các nguyên lý khi lập trình, các phương pháp lập trình, kiểm tra & tối ưu hóa chương trình,... Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình nâng cao: Chương 4 - ThS. Dương Thành Phết TRƢỜNG CAO ĐẲNG CNTT TP.HCM KHOA CÔNG NGHỆ THÔNG TIN KỸ THUẬT LẬP TRÌNH NÂNG CAO Chƣơng 4: KỸ THUẬT LẬP TRÌNH TỐI ƢU Giảng Viên: ThS. Dƣơng Thành Phết Email: phetcm@gmail.com Website: http://www.thayphet.net 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. PHƢƠNG PHÁP PHÂN TÍCH BÀI TOÁN 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 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. KIỂM TRA & TỐI ƢU HÓA CHƢƠNG TRÌNH 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. 12  Nguyên lý dùng công thức thay bộ nhớ 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ụ: Sau khi tối ưu: Hàm P(i) Hàm P() { { … for(i=1; i 6. ...