Bài giảng Cơ sở lập trình nâng cao - Chương 10: Tối ưu hóa chương trình - Tôn Quang Toại

CƠ SỞ LẬP TRÌNH NÂNG CAOBiên soạn: Ths.Tôn Quang ToạiTonQuangToai@yahoo.comTPHCM, NĂM 2013TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCMKHOA CÔNG NGHỆ THÔNG TINTỐI ƯU HÓA CHƯƠNG TRÌNHChương 10Tối ưu hóa chương trình 2 Đặc trưng trong chương trình cần tối ưuTối ưu hóa thời gian thực hiện chương trình Tối ưu hóa không gian lưu trữ dữ liệu 2 Loại tối ưu Tối ưu chương trình không làm thay đổi thuật toán (Chỉnh sửa mã chương trình)Tối ưu chương trình làm thay đổi thuật toánTỐI ƯU HÓA THỜI GIANCHỈNH SỬA MÃ CHƯƠNG TRÌNHChỉnh sửa mã chương trìnhCác cách chỉnh sửa mã chương trìnhQuy tắc Vòng lặpQuy tắc LogicQuy tắc HàmQuy tắc Biểu thứcQUY TẮC VÒNG LẶPTốu ưu câu lệnh lặpQuy tắc vòng lặp 1: Đưa code ra ngoài vòng lặpĐưa các tính toán không phụ thuộc vào chỉ số lặp ra khỏi vòng lặpCác biểu thức tính toán nếu đều được tính toán giống nhau qua các lần lặp thì nên được để ngoài vòng lặpChú ý những biểu thức chứa những phép toán tốn nhiều thời gian: *, /, hàm mũ, lấy căn, ...Tốu ưu câu lệnh lặpfor (i=0; i value) { found = 0; break; }}Tốu ưu câu lệnh lặpCải tiếnTốu ưu câu lệnh lặpQuy tắc vòng lặp 3: Tháo bỏ vòng lặp – Do chi phí thay đổi chỉ số lớn: Trong vòng lặp ngắn hay thân vòng lặp ít code thì chi phí lớn thường nằm trong các lệnh thay đổi chỉ số. Chi phí thay đổi chỉ số vòng lặp thường được giảm bằng cách Bỏ vòng lặpGiảm số lần lặp, tăng số lệnh trong thân vòng lặpTốu ưu câu lệnh lặpsum=0;for (i=0; iMAXFIBO) return 0; if (n a[i]) min = a[i];for (i=1; i0 trong vòng lặp chúng ta sẽ kiểm tra X!=0Thay vì kiểm tra sqrt(X)>sqrt(Y) trong vòng lặp chúng ta sẽ kiểm tra X>YQuy tắc logicQuy tắc logic 2: Dùng hàm có chu kỳ ngắnNếu chúng ta muốn kiểm tra một hàm không giảm với một ngưỡng nào đó thì chúng ta không cần phải tính toán hàm tiếp nếu ngưỡng đã đạt đếnVí dụ:sum=0;for (i=0; i threshold)Quy tắc logicCải tiếnsum=0;i=0;while (i threshold)Quy tắc logicCải tiếnsum=0;i=0;if (n%2==1){ i=1; sum=x[0];}while (i threshold)Tối ưu biểu thức logicQuy tắc logic 3: sắp xếp lại các biểu thức kiểm traPhép toán logic AND: Biểu thức có khả năng sai nhiều nhất được sắp trước:if (A1 && A2 && && An){ }Tối ưu biểu thức logicQuy tắc logic 3: sắp xếp lại các biểu thức kiểm traPhép toán logic OR: Biểu thức có khả năng đúng nhiều nhất được sắp trước: if (A1 || A2 || || An){ }TỐI ƯU HÓA THỜI GIANTHAY ĐỔI THUẬT TOÁN THAY ĐỔI THUẬT TOÁN Dùng phương pháp Chia để trịDùng phương pháp Quy hoạch động – Bảng tra (lookup table)Tận dụng các công thứcDùng phương pháp Chia để trịDùng phương pháp Chia để trịKhi chia được bài toán thành các bài toán con giống nhauChúng ta chỉ cần giải 1 bài toán conDùng kết quả này cho các bài toán con giống nhau mà không cần giải lạiDùng phương pháp Chia để trịVí dụ: Tính anTìm max/min của dãy số nguyên Tìm số nhỏ thức k trong mảng nguyênTìm kiếm nhị phânQuicksortDùng phương pháp Quy hoạch động – Bảng tra (lookup table)Dùng phương pháp Quy hoạch động – Bảng tra (lookup table)Những giá trị được dùng nhiều lần, chúng ta chỉ cần tính 1 lần rồi lưu lại trong 1 bảng (gọi là bảng lookup)Khi cần giải lại bài toán đã giải chúng ta chỉ tra trong bảng lookupDùng phương pháp Quy hoạch động – Bảng tra (lookup table)Ví dụ: Tính Cách 1: Cách thông thườngTính k!Tính tổ hợp: Gọi tính giai thừaTính các Dùng phương pháp Quy hoạch động – Bảng tra (lookup table)Cách 2: Dùng bảng lookupDùng bảng (n+1) phần tử a[0], a[1], ..., a[n] để tính và lưu a[i]=i!Cải tiếnTận dụng các công thứcSử dụng các công thức thay cho vòng lặpTính toán trên giấy trước khi lập trìnhTìm mối quan hệ giữa bước tính trước và bước tính sauTận dụng các công thứcVí dụ: Tính tổng S sau: int TinhTong(int n){ int s; s=0; int i; for (i=1; i<=n; i++) s = s + i; return s;}int TinhTong(int n){ int s; s = n*(n+1)/2; return s;}Tận dụng các công thứcVí dụ: Viết chương trình tính các biểu thức sau: Tận dụng các công thứcVí dụ: Viết chương trình tính tổng Cách 1: Cách thông thườngChia nhỏ vấn đề, cài đặt các hàm cho từng vấn đềTính xkTính k!Tận dụng các công thứcCách 2: Tìm mối quan hệ giữa bước tính trước và bước tính sauCải tiếnTận dụng các công thứcVí dụ: Tính Cách 1: Cách thông thườngTính k!Tính tổ hợp: Gọi tính giai thừaTính các Tận dụng các công thứcCách 2: Dùng bảng lookupDùng bảng (n+1) phần tử a[0], a[1], ..., a[n] để tính và lưu a[i]=i!Cải tiếnTận dụng các công thứcCách 3: Dùng quy nạpCải tiếnTận dụng các công thứcCách 4: Tìm mối quan hệ giữa bước tính trước và bước tính sauCải tiếnTận dụng các công thứcCách 5: Hạ xuống phân nửa cho mỗi cách (2), (3), (4) do tính đối xứngCải tiếnChỉ cần tính với k=1, 2,..., [n/2]Tận dụng các công thứcVí dụ: Kiểm tra n có là số nguyên tố khôngCách 1: Dựa vào định nghĩa số nguyên tốKiểm n có chia hết cho các số từ 2n-1 khôngCách 2: Nhận xét các ước số của n chỉ nằm trong [2...n/2]Kiểm tra n có chia hết cho các số từ 2n/2 khôngTận dụng các công thứcCách 3: Nhận xét nếu n không nguyên tố thì sẽ tồn tại ước số nguyên tố thuộc [2...sqrt(n)]Nếu n<2 thì n không là số nguyên tốNếu n=2 thì n là số nguyên tốKiểm tra n có là số chẵn khôngKiểm tra n có chia hết cho các số từ 3sqrt(n) không: 3,5,7, ..., sqrt(n)KẾT THÚC NỘI DUNGMÔN HỌC CSLTNC