Bài giảng Kỹ thuật lập trình - Bài 11: Tinh chỉnh mã nguồn - Lê Gia Minh

Nội dung text: Bài giảng Kỹ thuật lập trình - Bài 11: Tinh chỉnh mã nguồn - Lê Gia Minh

1. TINH CHỈNH MÃ NGUỒN Kỹ thuật lập trình Nâng cao Lê gia Minh 1
2. Nội dung l Ôn tập. l Khái niệm về tinh chỉnh mã nguồn. l Một số kỹ thuật tinh chỉnh mã nguồn. l Một số ví dụ. 2
3. Khái niệm tinh chỉnh mã nguồn l Một chương trình hiệu qủa ¡ Biên dịch nhanh (công sức lập trình) ¡ Yếu tố thời gian: NHANH (góc nhìn của user) ¡ Yếu tố lưu trữ: NHỎ (yếu tố không gian) ¡ Khó đạt được cả ba ¡ Ngày nay: Yếu tố thời gian được xem trọng l Muốn biên dịch nhanh Bỏ Optimizer khi biên dịch ( phụ thuộc vào compiler ) l Dùng các cấu trúc dữ liệu hợp lý, cải tiến giải thuật, sử dụng các phat biểu hợp lý cũng giúp làm tăng đáng kể về hiệu suất thời gian chạy của chương trình. 3
4. Khái niệm tinh chỉnh mã nguồn (tt) l Hai yếu tố thời gian và không gian mâu thuẫn nhau Muốn chạy nhanh thì chấp nhận kích thước chương trình lớn. ( thí dụ : bỏ bớt các lời gọi hàm ) l Ngày nay, với sự tiến bộ của kỹ thuật, CPU tốc độ cao, bộ nhớ lớn, khuynh hướng hiện nay là chấp nhận dư thừa dữ liệu để đạt yêu cầu về thời gian. 4
5. Thí dụ l Thí dụ: Có khai báo cấu trúc về đoạn thẳng struct Line { int x1,y1; // điểm đầu int x2,y2; // điểm cuối }; double getLen (Line L) // hàm tính độ dài { return sqrt( (L.y2-L.y1)*(L.y2-L.y1) + (L.x2-L.x1)*(L.x2-L.x1)); } Mỗi lần truy xuất độ dài 1 đoạn thẳng, 8 lần truy xuất dữ liệu (biến), 4 phép trừ, 2 phép nhân, một phép cộng và 1 lời gọi hàm sqrt được thực thi 5
6. Cải tiến struct Line { int x1,y1; // điểm đầu int x2,y2; // điểm cuối double len ; // độ dài }; Chỉ phải cập nhật trị của len mỗi lần khi x1,y1,x2,y2 thay đổi, còn khi truy xuất độ dài chỉ tốn 1 lần truy xuất bộ dữ liệu (biến). 6
7. Một số kỹ thuật l Cải tiến giải thuật l Tinh chỉnh code (tuning code) 7
8. Cải tiến giải thuật l Thêm yêu tố (augmenting) trong cấu trúc thay cho tính toán l Tạo bảng tìm kiếm để lưu các trị được tình toán trước. l Dùng bảng kiểm tra lười (lazy evaluation) l Khởi tạo dữ liệu ngay lúc biên dịch và tính toán trước. l Giải pháp cho các tình huống đơn giản . l Cải tiến giải thuật l Dùng kiểm tra đơn giản thay cho việc kiểm tra phức tạp. l Dùng kỹ thuật cầm canh (sentinels). l Tránh đệ quy. l Giảm truy xuất đĩa. 8
9. Thêm yếu tố trong cấu trúc struct Line struct Line { int x1,y1; { int x1,y1; int x2, y2; int x2,y2; }; double Len; }; Bớt việc tính toán độ dài mỗi khi cần truy xuất 9
10. Tạo bảng tìm kiếm l Tình huống: Cần rất nhiều truy xuất 1 trị căn bậc 2 của 0 = ‘A’ && ch <= ‘Z’) 10
11. Bảng kiểm tra lười ( lazy table) l Ta muốn bảng tính toán trước chỉ cần thực thi tại lần đầu tiên truy xuất căn bậc 2 của x #define NUM 100 double square_root(int x) { static double sqrt_table[NUM+1]; static int precalc[NUM+1]; // mảng flag đánh dấu if (!precalc[x]) { sqrt_table[x]= sqrt(x); // đưa căn x vào mảng precalc[x]= 1; // đánh dấu đã đưa trị vào bảng rồi } return sqrt_table[x]; } 11
12. Kỹ thuật khởi tạo dữ liệu lúc biên dịch l Định nghĩa trước bảng căn 2 #define NUM 100 double square_root(int x) { static double sqrt_table[NUM+1]= { 0.000000, 1.000000, 1.414214, 1.732051, 9.949874, 10.000000 }; return sqrt_table[x]; } 12
13. Tạo trước dữ liệu cho một số tình huống đơn giản l Định nghĩa trước một số trị kết qủa của n! int factorial(int n) { static precalc[8]= {1,1,2,6,24,120,720,5040}; if (n<8) return precalx[n]; return n * factorial(n-1); } 13
14. Phần tử cầm canh l Vét cạn(Exhautive) – đơn giản for(I = 1 to N) if (A[i] == X ) return i ; l Tìm kiếm có phần tử cầm canh(sentinel) Làm giảm số lần so sánh trong vòng lặp bằng cách thêm phần tử lính canh H K A I S D E A G S Phần tử cần14 tìm S N
15. Compare Sentinel and Not START START 1 i 1 i > = i : N A[i] : X = (i+1) i N+1 i : N N*2 lần so < lần so sánh Found Found Not Found sánh 15 END END
16. Kiểm tra đơn giản l Giải thuật kiểm tra 1 điểm (x,y) có nằm trong 1 vòng tròn (xc,yc,R)hay không? l d= khoảng cách (x,y) tới (xc,yc) l (x,y) nằm trong vòng tròn d R) return 0; if (dy>R) return 0; return (dx*dx + dy*dy <= R*R); } 16
17. Tránh dùng đệ quy nếu được l Sử dụng giải thuật đệ quy làm tăng chi phí gọi và trả về từ hàm. l Tốn thêm nhiều bộ nhớ. l Viết hàm đệ quy ngắn gọn. l Có chương riêng về kỹ thuật đệ quy. 17
18. Dùng số nguyên thay cho số thực l Xử lý số thực chậm hơn xử lý số nguyên. l Với số thực có số số lẻ cố định, nên biểu diễn số thực sang số nguyên l Thí dụ: Biểu diễn tiền: value= $US 12.48 sẽ biểu diễn thành: value=1248. Khi xuất dữ liệu dollars= value/100; cents = value % 100; 18
19. Giảm truy xuất đĩa l Chi phí truy disk I/O chiếm tỉ lệ lớn trong hiệu qủa thời gian của chương trình. l Các kỹ thuật tăng hiệu suất disk I/O § Sử dụng các record kích thước nhỏ. § Đệm lại các record hay dùng. § I/O với buffer § Nén data § Sử dụng các cấu trúc được thiết kế tốt hơn. 19
20. Bài tập l Mỗi hóa đơn được mô tả bằng số hóa đơn, ngày xuât hóa đơn, tên và địa chỉ khách hàng. Trên hoa đơn ghi chép một số mặt hàng đã được khách hàng này mua. Đối với nhà quản lý, doanh thu là quan trọng nên thông tin này thường được truy xuất. Theo ý bạn, hóa đơn nên được mô tả thế nào để giúp tăng hiệu suất của chương trình xử lý các hóa đơn? 20
21. Tinh chỉnh Code 21
22. Tinh chỉnh Code l Tinh chỉnh vòng lặp l Tinh chỉnh các phát biểu điều khiển l Tinh chỉnh biểu thức l Tinh chỉnh hàm l Một sô kỹ thuật khác 22
23. Tinh chỉnh Code – Lấy Code ra ngòai vòng lặp l for (i = 0 ; i<20 ; i++) l for (i = 0; i<strlen(st) l a[i] *= PI * 2.0; ; i++) Thay bằng : l st[i] = st[i]+32; l scale = PI*2.0; Thay bằng: l for (i = 0 ; i<20 ; i++) l Nên đem strlen ra a[i] *= scale ; ngoài 23
24. Gom vòng lặp for (i=0;i<n; i++) a[i]= 0; for (i=0;i<n; i++) b[i]= 0; (2*n lần kiểm tra i<n) for (i=0;i<n; i++) a[i]= b[i]= 0; 24
25. Duyệt mảng với pointer l Duyệt mảng với pointer để làm giảm việc tinh toán địa chỉ từ a[i] for (i=0;i<MAX; i++) a[i]= 0; n=MAX; int *ptr ; for (ptr=a; n!=0; ptr++,n ) *ptr=0; 25
26. Bài tóan gà - chó l Vừa gà vừa chó bó lại cho tròn 36 con 100 chân chẳn. Hỏi có bao nhiêu gà chó. void Ga_Cho() { int ga , cho ; for ( ga = 1 ; ga <=35 ; ga++) for(cho = 1 ; cho<=24 ; cho++) if (((2*ga) + (cho*4))==100 && (ga+cho) == 36) { printf("So ga : %d\n“,ga); printf("So cho : %d\n“ , cho); } } 26
27. Bài tóan gà – chó(cải tiến) l void Ga_Cho2() l { l int ga , cho ; l for ( ga = 1 ; ga <=35 ; ga++) l { l cho = 36 - ga ; l if (((2*ga) + (cho*4))==100 ) l { l printf("So ga : %d\n“,ga); l printf("So cho : %d\n“ , cho); l } l } l } 27
28. Bài tóan ex l e^x = 1 + x + x^2/2! +x^3/3! + + x^n/n! l Nhận xét : ¡ Với x không lớn : khi n ∞ thì : n! >>x^n ¡ Do vậy : x^n/n! 0 khi n ∞ l Dựa vào nhận xét trên ta giải bài tóan : 28
29. l double giaithua(int x) l { l double kq = 1.0 ; l int k; l if ( x == 0 ) return 0; l for ( k = 1 ; k epsilon ) ; l printf("e^x la : %lf\n“ , result); l } 29
30. Cải tiến bài tóan ex l void main() l { l const double epsilon = 0.0000001; l double result = 0 , bieuthuc = 1; l double x , k; l int n = 0; l printf("Nhap x : “); scanf(“%lf” , &x); l do l { l result += bieuthuc ; l bieuthuc *= x/++n ; l } while( bieuthuc > epsilon ) ; l printf("e^x la : %lf\n“ , result); l } 30
31. Tinh chỉnh phát biểu điều khiển l Dùng if else thay cho switch switch(c) { case ‘a’: if (c==‘a’) { } case ‘f’: else if (c==‘f’) { } case ‘d’: else if (c==‘d’) { } default: else { } } 31
32. Tinh chỉnh biểu thức Dùng các biểu thức đại số tương đương có hiệu suất cao, giảm số phép toán. l x+x 2*x x<<1 l a*x + a*y a*(x+y) l (a&&b)||(a&&c) a&&(b||c) l (a||b) && (a||c) a || (b&&c) l 2*x*3.14 (2*3.14)*x vì một số trình biên dịch sẽ tinh toán (2*3.14) vào lúc biên dịch. 32
33. Số nguyên tố int La NT( long N) int La NT( long N) int La NT( long N) { { { long i ; long i , max ; long i , max ; for ( i = 2 ; i< N ; i++) max = long(sqrt(n)); if (n<=2) return 1; if ( n%i ==0) return for ( i = 2 ; i< max; if ( n%2==0) return 0; 0; i++) max = long(sqrt(n)); return 1; if ( n%i ==0) return for (i = 3 ;i< max; } 0; i+=2) 1 to 10000 : 12.59 giay return 1; if ( n%i ==0) return } 0; 1 to 10000 : 0.34 giay return 1; } 0.20 giay 33
34. Binary Search l int BSearch(int A[],int n,int T) l { l int L = 0, R = n-1; l int m ; l l while(1) l { l if (L>R) return –1; l m = (L+R)/2; l if (A[m]==T) return m ; l else if (A[m] T) R = m-1; l } l } 34
35. Bài tập l Tinh chỉnh code sau : if (strcmp(s1,s2)==0) printf(“equal”); else if (strcmp(s1,s2) >0) printf(“greater than”); else printf(“less than”); l Giải hệ phương trình : X + Y + Z = M X3 + Y3 + Z3 = N X,Y,Z :nguyên dương 35