Tăng hiệu quả chương trình và phong cách lập trình

Sau khi học môn kỹ thuật lập trình ở trường thì mình nhận ra những người mới học như mình còn rất yếu về việc tối ưu hóa code để tăng hiệu năng chương trình. Vậy nên hôm nay mình xin phép được tổng hợp lại những gì được học trên lớp với hy vọng ít nhiều giúp bản thân hiểu vấn đề sâu hơn và nhận sự góp ý từ các bạn.
"Viết code đúng đã khó, viết code đẹp còn khó hơn"

Tối ưu hóa code

#1: Trước hết là giải thuật
• Hãy dùng giải thuật tốt nhất có thể
• Sau đó hãy nghĩ đến việc tăng hiệu quả code
• Ví dụ:
Tìm ước số chung lớn nhất của 2 số nguyên

C++ Code:

Select All | Show/Hide

1. Giai thuat 1:
2. int UCLN(int a, int b)
3. {
4.     while(a!=b)
5.     {
6.         if(a>b)
7.             a-=b;
8.         else
9.             b-=a;
10.     }
11.     return b;
12. }
13. /*-----------------------*/
14. Giai thuat 2:
15. int UCLN(int x, int y)
16. {
17.     int t = x % y;
18.     while (t)
19.     {    
20.         x=y;
21.         y=t;  
22.         t=x % y;  
23.     }  
24.     return y;
25. }

Phân tích:
2 giải thuật trên cùng để tìm UCLN của 2 số nguyên nhưng giải thuật 1 kém tối ưu hơn vì:
- Máy tính xử lý phép trừ chậm hơn phép nhân và phép chia
-> Lý luận đoạn này sai nhé các bạn. máy tính luôn thực hiện phép cộng trừ nhanh hơn nhiều lần so với nhân và chia. phép dịch bít thì nhanh hơn 2 cái này. đoạn sau có ví dụ...- Nếu 2 số a, b chênh lệch nhau rất nhiều( Giả sử a=9, b=60696) thì việc thực hiện phép trừ là rất kém hiệu quả


#2: Vòng lặp
- Loại bỏ những biểu thức thông thường

C++ Code:

Select All | Show/Hide

1. /*---------Bad code---------*/
2. for(int i=0; i<n; i++)
3. {
4.     int a,b;
5.     a=sin(0.25);
6.     b+=a*i;
7. }
8. /*---------Good code--------*/
9. float a=sin(0.25);
10. for(int i=0; i<n; i++)
11. {
12.     float b;
13.     b+=a*i;
14. }

- không dùng vòng lặp ngắn

C++ Code:

Select All | Show/Hide

1. /*---------Bad code---------*/
2. int a=0;
3. for(i=0; i<3; i++)
4. {
5.     a=a*i+i
6. }
7.  
8. /*---------Good code--------*/
9. int a=0, i=0;
10. a=a*i+i;
11. i++;
12. a=a*i+i;
13. i++;
14. a=a*i+i

- Tính toán giá trị trước khi vào vòng lặp
Nếu bạn phải tính đi tính lại giá trị của 1 biểu thức thì hãy tính giá trị ấy 1 lần rồi lưu lại giá trị và có thể sử dụng nhiều lần sau này

C++ Code:

Select All | Show/Hide

1. /*---------Bad code---------*/
2. int f(int n)
3. {
4.     if(n<10&&n>=0)
5.     {
6.         return n*n-n;
7.     }
8. return 0;
9. }
10.  
11. /*---------Good code--------*/
12. static int A[]={0, 0, 2, 3*3-3,...,9*9-9}
13. int f(int n)
14. {
15.     if(n<10&&n>=0) 
16.         return A[n];
17.     return 0;
18. }

Phương pháp này hay còn gọi là Look-up table.

#3: Hạn chế dùng hàm nếu có thể
- Sử dụng inline function trong C++ : Nếu 1 hàm không có loop(for, while…) thì có thể khai báo inline. Inline code sẽ được chèn vào bất cứ chỗ nào hàm được gọi, chương trình sẽ lớn hơn chút ít nhưng sẽ nhanh hơn .Tránh được việc dùng stack -4 bước khi gọi 1 hàm.

C++ Code:

Select All | Show/Hide

1. #include <iostream.h>  
2. #include <math.h>  
3. inline double delta (double a, double b)  
4. {  
5.     return sqrt (a * a + b * b);  
6. }
7.    
8. int main ()
9. {  
10.     double k = 6, m = 9;
11.     // 2 dòng sau thuc hien nhu nhau:  
12.     cout << delta (k, m) << ‘\n’;  
13.     cout << sqrt (k * k + m * m) <<‘\n’;  
14. }

#4: Sử dụng biến đổi số học
Trình dịch không thể tự động xử lý một cách thông minh , vậy nên hãy giúp trình dịch làm việc đó.
Máy tính thực hiện phép dịch bit nhanh hơn phép nhân, chia. Phép cộng trừ thực hiện mất nhiều thời gian hơn nhân và chia.
Ví Dụ:

C++ Code:

Select All | Show/Hide

1. /*---------Bad-------*/
2. if(a*8<50)
3. {
4.     a=a*a+4*a-5;
5. }
6. /*-------Good-------*/
7. if((a<<3)<50)
8. {
9.     a=(a-1)*(a+5);
10. }

Thay vì viết a*8 thì ta thực hiện phép dịch bit sẽ nhanh hơn a<<3=a*2^3


#5: Dùng lính canh để tránh những kiểm tra không cần thiết
ý tưởng:
- Đặt vị trí tìm thấy ở cuối xâu, mảng…
- Ta luôn tìm thấy nhưng: nếu vị trí tìm thấy mà lớn hơn độ dài xâu => không tìm thấy!

C++ Code:

Select All | Show/Hide

1. /*----------Trước khi dùng lính canh-----------*/
2. char s[100], searchValue;
3. int vitri, timthay, size;
4. ...<gan gia tri cho s va searchValue>
5. ...
6. size=strlen(s);
7. vitri=0;
8. while((pos<size)&&(s[vitri]!=searchValue))
9.     {
10.         vitri++;
11.     }
12. if(vitri>=size)
13.     timthay=0;
14. else
15.     timthay=1;
16.  
17. /*----------Su dung linh canh---------*/
18. s=strlen(str);
19. strcat(str,searchValue);
20. vitri=0;
21. while(str[vitri]!=searchValue)
22. {
23.     vitri++;
24. }
25. if(vitri>=s)
26.         timthay=0;
27. else
28.     timthay=1;

- Dùng lính canh sẽ tránh được việc kiểm tra không cần thiết: trong trường hợp này nếu không dùng lính canh ta sẽ phải thêm 1 lần kiểm tra vitri<s trong mỗi lần lặp.

#6: Những nguyên tắc cơ bản để có 1 code tốt
- Đơn giản hóa code: hầu hết chương trình chạy nhanh đều đơn giản, vì vậy hãy đơn giản hóa code nhất có thể để chương trình chạy nhanh hơn.
- Đơn giản hóa vấn đề : hãy đơn giản hóa vấn đề mà chương trình cần giải quyết
- Không ngừng nghi ngờ: luôn đặt những câu hỏi về sự có mặt của những dòng code, những trường trong struct,…

Quy tắc tốc độ:
1. Có thể tăng tốc độ bằng cách dùng thêm bộ nhớ phụ (mảng): Những biểu thức thường xuyên được tính toán với phạm vi giá trị nhỏ thì ta có thể tính trước tất cả rồi đưa vào mảng để sau này chỉ việc gọi theo chỉ số mảng mà không cần tính toán lại
2. Hiểu và tận dụng bộ nhớ cache:
Một chút về cache: Bộ nhớ cache có dung lượng rất nhỏ (máy mình có cache ~3Mb), tốc độ rất lớn( xấp sỉ bằng tốc độ của CPU) có chức năng làm giảm sự chênh lệch về mặt tốc độ giữa bộ nhớ chính và CPU. Khi CPU thực hiện 1 lệnh nó sẽ load dữ liệu vào và trước tiên nó sẽ kiểm tra xem trong cache đã có chưa, nếu có dữ liệu đó rồi thì sẽ sử dụng luôn. Nếu chưa có thì sẽ tải từ bộ nhớ chính vào cache sau đó mới sử dụng. Khi tải dữ liệu vào cache nó sẽ tải theo từng blocks(gồm nhiều bytes dữ liệu nằm liên tiếp nhau trong bộ nhớ chính). Vì thế dữ liệu thường dùng cần phải dễ tiếp cận và luôn hiện hữu. Cụ thể hãy xem ví dụ nhỏ sau:

Vi dụ dưới đây mô ta việc gán giá trị cho các phần tử của mảng 2 chiều. Nhưng một số trường hợp các bạn không để ý việc triển khai vòng lặp theo thứ tự cột trước hàng sau là không có lợi.

C++ Code:

Select All | Show/Hide

1. /*--------Bad code----------*/
2. for(int j=0; j<cot; j++)
3. for(int i=0; i<hang; i++)
4. {
5.     A[i][j]=1;
6. }
7. /*--------Good code----------*/
8. for(int i=0; i<hang; i++)
9. for(int j=0; j<cot; j++)
10. {
11.     A[i][j]=1;
12. }

- Ta đã biết , mảng 2 chiều thực ra là các mảng một chiều nối tiếp nhau vậy nên khi lệnh được thực hiện thì dữ liệu được đưa vào trong cache theo từng vùng liên tiếp nhau. Nên nếu ta thực hiện lệnh trên các phần tử ,mảng liên tiếp nhau sẽ nhanh hơn rất nhiều.
- Khi ta gọi A[0][0] thì A[0][1], A[0][2] cũng được nạp vào cache như vậy việc ta thực hiện gán theo từng hàng sẽ nhanh hơn việc gán theo cột vì A[1][0] và A[2][0] không được nạp vào cùng.
3. Gần 2/3 số lệnh mà máy tính cần thực hiện là đến từ vòng lặp. Vậy nếu ta tối ưu hóa các lệnh cũng như thực hiện lặp một cách thông mình thì hiệu năng chương trình sẽ tăng rất cao:
- Đưa các biểu thức bất biến ra khỏi vòng lặp, tính toán giá trị trước khi vào lặp-nếu có thể.
- Nếu 2 vòng lặp cạnh nhau cùng thao tác trên cùng một tập hợp phần tử thì hãy dồn chúng lại thành một vòng lặp.
- Trong vòng lặp, càng ít phép kiểm tra càng tốt và tốt nhất là 1 phép thử. Nên sử dụng lính canh để giảm số phép thử.
- Cần loại bỏ vòng lặp ngắn để tránh việc kiểm tra điều kiện lặp…


#7: Good programming type

Sau đây là các quy tắc về “programming style “ rút ra từ cuốn “The Elements of Programming Style" của tác giả Kernighan and Plauger. Cần lưu ý rằng các quy tắc của “programming style” , giống như quy tắc văn phạm English, đôi khi bị vi phạm, thậm trí bởi những nhà văn hay nhất. Tuy nhiên khi 1 quy tắc bị vi phạm, thì thường được bù lại bằng một cái gì đó, đáng để ta mạo hiểm. Nói chung sẽ là tốt nếu ta tuân thủ các quy tác sau đây :
1. Tính nhất quán: việc đặt tên hàm, tên biến hãy tự tạo ra quy tắc cho riêng mình và tuân thủ trong suốt chương trình. Ví dụ:
Tên hàm: TenHam
Tên biến: biến chạy( i,j,k) và không sử dụng chúng vào mục đich khác
Tên struct : Struct NODE
…
2. Đầu mỗi chương trình nên có 1 đoạn chú thích
3. Mỗi chương trình con chỉ nên thực hiện một chức năng nhất định và nó phải đủ ngắn, rõ ràng để người đọc dễ dàng nắm bắt được chức năng của nó
4. Hãy dùng tối thiểu tham số cho chương trình con. > 6 tham số cho 1 chương trình con là quá nhiều
5. Không nên thay đổi giá trị của biến chạy trong thân vòng for:

C++ Code:

Select All | Show/Hide

1. for(i=0; i<69; i++) i++;

6. Viết rõ ràng, đừng quá thông minh(kỳ bí):
Hãy cho biết nhiệm vụ của đoạn chương trình sau. Và viết lại chúng cho sáng sủa, dễ hiểu hơn.

C++ Code:

Select All | Show/Hide

1. #include<stdio.h>
2. int ____(int _, int __){!__?_:____(__,_%__);}int main(){int _=24, __=32;printf("%d",____(_,__));}

7. Sử dụng thư viện mọi khi có thể.
8. Tránh dùng nhiều biến trung gian
9. Viết rõ ràng/ đừng hy sinh sự rõ ràng cho hiệu quả
10. Hãy để máy tính làm những việc nặng nhọc của nó (tính toán)
11. Thay các biểu thức lặp đi lặp lại bằng các hàm
12. Dùng () để tránh rắc rối
13. Trước hết hãy viết chương trình bằng giả ngữ dễ hiểu rồi hãy viết bằng ngôn ngữ cần thiết
14. Không chắp vá mã xấu, mà hãy viết lại chúng
15. Viết và kiểm tra 1 CT lớn thành các chương trình con
16. Dùng thủ tục đệ quy thay cho các cấu trúc dữ liệu đệ quy
17. Kiểm tra đầu vào để đảm bảo tính chính xác và hợp lệ
18. Hãy kết thúc dòng nhập bằng ký hiệu EOF chứ k dùng biến đếm
19. Hãy làm cho chương trình chạy đúng trước khi làm cho nó chạy nhanh
20. Chú thích phải rõ ràng, sát code. Không chú thích điều hiển nhiên



Source: http://diendan.congdongcviet.com/threads/t207034::tang-hieu-qua-chuong-trinh-phong-cach-lap-trinh.cpp