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

Nội dung text: 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

1. CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Ths.Tôn Quang Toại [email protected] TPHCM, NĂM 2013
2. Chương 10 TỐI ƯU HÓA CHƯƠNG TRÌNH
3. Tối ưu hóa chương trình ▪ 2 Đặc trưng trong chương trình cần tối ưu • Tố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án 3
4. TỐI ƯU HÓA THỜI GIAN CHỈNH SỬA MÃ CHƯƠNG TRÌNH
5. Chỉnh sửa mã chương trình ▪ Các cách chỉnh sửa mã chương trình • Quy tắc Vòng lặp • Quy tắc Logic • Quy tắc Hàm • Quy tắc Biểu thức 5
6. QUY TẮC VÒNG LẶP
7. Tốu ưu câu lệnh lặp ▪ Quy 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ặp • Cá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ặp • Chú ý 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, 7
8. Tốu ưu câu lệnh lặp ▪ Ví dụ: Phân tích và Tối ưu đoạn mã sau theo quy tắc trên for (i=0; i<n; i++) { x[i] = x[i] * exp(sqrt(PI/2)); } 8
9. Tốu ưu câu lệnh lặp ▪ Quy tắc vòng lặp 2: Kết hợp các biểu thức kiểm tra • Một vòng lặp hiệu quả sẽ chứa càng ít biểu thức logic dùng để kiểm tra kết thúc vòng lặp càng tốt. Đặc biệt các vòng lặp nằm sâu bên trong • Tốt nhất chỉ nên có 1 biểu thức logic kiểm tra kết thúc vòng lặp. • Cố gắng thay thế một số điều kiện thoát bằng điều kiện thoát khác hiệu quả hơn 9
10. Tốu ưu câu lệnh lặp ▪ Ví dụ 1: Phân tích và Tối ưu đoạn mã sau theo quy tắc trên i=0; while (i<n && x[i]!=value) i++; if (i<n) found = 1; else found = 1; 10
11. Tốu ưu câu lệnh lặp 11
12. Tốu ưu câu lệnh lặp ▪ Ví dụ 2: Cho đoạn mã Tìm kiếm phần tử có giá trị value trong mảng đã được sắp xếp tăng. Hãy phân tích và cải tiến để giảm biểu thức logic trong vòng lặp của đoạn mã for (i=0; i value) { found = 0; break; } } 12
13. Tốu ưu câu lệnh lặp 13
14. Tốu ưu câu lệnh lặp ▪ Quy 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ặp – Giảm số lần lặp, tăng số lệnh trong thân vòng lặp 14
15. Tốu ưu câu lệnh lặp ▪ Ví dụ 1: Phân tích và cải tiến đoạn mã sau sum=0; for (i=0; i<10; i++) sum = sum + x[i]; 15
16. Tốu ưu câu lệnh lặp ▪ Ví dụ 2: Hãy cải tiến thuật toán tìm kiếm tuần tự giá trị value trong dãy tăng dần x[n] = value; i=0; while (x[i] < value) i++; if (i<n && value==x[i]) found = 1; else found = 0; 16
17. Tốu ưu câu lệnh lặp 17
18. Tốu ưu câu lệnh lặp ▪ Quy tắc vòng lặp 4: Tháo bỏ vòng lặp – Do chi phí phép gán lớn • Nếu chi phí của vòng lặp tập trung vào những phép gán thì những phép gán này có thể được bỏ bằng cách: – Lặp lại đoạn mã và – Thay đổi cách dùng biến 18
19. Tốu ưu câu lệnh lặp ▪ Ví dụ: Cho hàm tính số Fibonacci thứ n như sau. Hãy phân tích và cải tiến để hàm sử dụng ít phép gán hơn int Fibonacci(int n) { int f1, f2, f3, i; if (n MAXFIBO) return 0; if (n<=2) return 1; f1 = 1; f2=1; for (i=3; i<=n; i++) { f3 = f1 + f2; f1 = f2; f2= f3; } return f3; } 19
20. Tốu ưu câu lệnh lặp 20
21. Tốu ưu câu lệnh lặp ▪ Quy tắc vòng lặp 5: Tổ hợp vòng lặp • Nếu 2 vòng lặp gần nhau thực hiện trên cùng tập phần tử thì tổ hợp các lệnh trong thân của 2 vòng lặp và chỉ dùng một vòng lặp 21
22. Tốu ưu câu lệnh lặp ▪ Ví dụ: Phân tích và cải tiến thuật toán tìm max và min sau min = a[0]; max = a[0]; for (i=1; i a[i]) min = a[i]; for (i=1; i<n; i++) if (max < a[i]) max = a[i]; 22
23. Tốu ưu câu lệnh lặp 23
24. QUY TẮC LOGIC
25. Quy tắc logic ▪ Quy tắc logic 1: Tận dụng các biểu thức đại số đồng dạng (tương đương) ▪ Ví dụ: • Thay vì kiểm tra sqrt(X)>0 trong vòng lặp chúng ta sẽ kiểm tra X!=0 • Thay vì kiểm tra sqrt(X)>sqrt(Y) trong vòng lặp chúng ta sẽ kiểm tra X>Y 25
26. Quy tắc logic ▪ Quy tắc logic 2: Dùng hàm có chu kỳ ngắn • Nế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 đến ▪ Ví dụ: sum=0; for (i=0; i threshold) 26
27. Quy tắc logic sum=0; i=0; while (i threshold) 27
28. Quy tắc logic sum=0; i=0; if (n%2==1) { i=1; sum=x[0]; } while (i threshold) 28
29. Tối ưu biểu thức logic ▪ Quy tắc logic 3: sắp xếp lại các biểu thức kiểm tra • Phép toán logic AND: Biểu thức có khả năng sai nhiều nhất được sắp trước: Pfalse (Ai ) Pfalse (Ai+1) if (A1 && A2 && && An) { } 29
30. Tối ưu biểu thức logic ▪ Quy tắc logic 3: sắp xếp lại các biểu thức kiểm tra • Phép toán logic OR: Biểu thức có khả năng đúng nhiều nhất được sắp trước: Ptrue(Ai ) Ptrue (Ai+1) if (A1 || A2 || || An) { } 30
31. TỐI ƯU HÓA THỜI GIAN THAY ĐỔI THUẬT TOÁN
32. 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ức 32
33. Dù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 nhau • Chúng ta chỉ cần giải 1 bài toán con • Dù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ại 33
34. Dùng phương pháp Chia để trị ▪ Ví dụ: • Tính an • Tìm max/min của dãy số nguyên • Tìm số nhỏ thức k trong mảng nguyên • Tìm kiếm nhị phân • Quicksort 34
35. Dù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 lookup 35
36. Dùng phương pháp Quy hoạch động – Bảng tra (lookup table) Ví dụ: Tính 0 1 2 n ▪ CCCCn, n , n , , n n! Ck = n k!( n− k )! ▪ Cách 1: Cách thông thường • Tính k! • Tính tổ hợp: Gọi tính giai thừa • Tính các k Cn 36
37. Dùng phương pháp Quy hoạch động – Bảng tra (lookup table) ▪ Cách 2: Dùng bảng lookup • Dùng bảng (n+1) phần tử a[0], a[1], , a[n] để tính và lưu a[i]=i! an[] Ck =  k = 0, n n a[ k ]* a [ n− k ] 37
38. Tận dụng các công thức ▪ Sử dụng các công thức thay cho vòng lặp ▪ Tính toán trên giấy trước khi lập trình ▪ Tìm mối quan hệ giữa bước tính trước và bước tính sau 38
39. Tận dụng các công thức ▪ Ví dụ: Tính tổng S sau: s( n )= 1 + 2 + + n int TinhTong(int n) { int TinhTong(int n) int s; { s=0; int s; int i; s = n*(n+1)/2; for (i=1; i<=n; i++) s = s + i; return s; } return s; } 39
40. Tận dụng các công thức ▪ Ví dụ: Viết chương trình tính các biểu thức sau: s1( n )= 1 + 3 + 5 + + 2 n − 1 s2 ( n )= 2 + 4 + 6 + + 2 n p( n )= 2 x 4 x 6 x x 2 n 40
41. Tận dụng các công thức ▪ Ví dụ: Viết chương trình tính tổng x x23 x xn s( n , x )= 1 + + + + + 1! 2! 3!n ! ▪ Cách 1: Cách thông thường • Chia nhỏ vấn đề, cài đặt các hàm cho từng vấn đề – Tính xk – Tính k! 41
42. Tận dụng các công thức ▪ Cách 2: Tìm mối quan hệ giữa bước tính trước và bước tính sau xk a = k k! xk +1 a = k +1 (k + 1)! ak +1 xx = aakk+1 = . ak k++11 k 42
43. Tận dụng các công thức Ví dụ: Tính 0 1 2 n ▪ CCCCn, n , n , , n n! Ck = n k!( n− k )! ▪ Cách 1: Cách thông thường • Tính k! • Tính tổ hợp: Gọi tính giai thừa • Tính các k Cn 43
44. Tận dụng các công thức ▪ Cách 2: Dùng bảng lookup • Dùng bảng (n+1) phần tử a[0], a[1], , a[n] để tính và lưu a[i]=i! an[] Ck =  k = 0, n n a[ k ]* a [ n− k ] 44
45. Tận dụng các công thức ▪ Cách 3: Dùng quy nạp k k−1 k CCCn=+ n−−11 n 1 11 1 2 1 1 3 3 1 1 4 6 4 1 45
46. Tận dụng các công thức ▪ Cách 4: Tìm mối quan hệ giữa bước tính trước và bước tính sau n! C k = n k!( n− k )! n! C k +1 = n (k+ 1)!( n − k − 1)! k +1 Cn k!( n−− k )! n k k = = Cn ( k+ 1)!( n − k − 1)! k + 1 nk− =CCkk+1 nnk +1 46
47. Tận dụng các công thức ▪ Cách 5: • Hạ xuống phân nửa cho mỗi cách (2), (3), (4) do tính đối xứng k n− k CCnn= • Chỉ cần tính với k=1, 2, , [n/2] 47
48. Tận dụng các công thức ▪ Ví dụ: Kiểm tra n có là số nguyên tố không ▪ Cá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ông ▪ Cá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ông 48
49. Tận dụng các công thức ▪ Cá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ông • Kiểm tra n có chia hết cho các số từ 3→sqrt(n) không: 3,5,7, , sqrt(n) 49