Bài giảng Kỹ thuật lập trình - Chương 3: Viết code hiệu quả - Lương Mạnh Bá

Nội dung text: Bài giảng Kỹ thuật lập trình - Chương 3: Viết code hiệu quả - Lương Mạnh Bá

1. Inline functions #include #include using namespace std; inline double hypothenuse (double a, double b) { return sqrt (a * a + b * b); } int main () { double k = 6, m = 9; // 2 dòng sau thực hiện như nhau: cout << hypothenuse (k, m) << endl; cout << sqrt (k * k + m * m) << endl; return 0; } SE-SoICT KTLT-3.8 Last update 6-2010
2. Static Variables • Các biến khai báo trong CT con được cấp phát bộ nhớ khi CT con được gọi và sẽ được giải phóng khi CT con kết thúc. • Khi gọi lại CT con, các biến cục bộ lại được cấp phát và khởi tạo lại, • Nếu muốn 1 giá trị vẫn được lưu lại cho đến khi kết thúc toàn chương trình, cần khai báo biến cục bộ của CT con đó là static và khởi tạo cho nó 1 giá trị. – Việc khởi tạo sẽ chỉ thực hiện lần đàu tiên chương trình được gọi và giá trị sau khi biến đổi sẽ được lưu cho các lần gọi sau. – Bằng cách này một ct con có thể “nhớ” một vài mẩu tin sau mỗi lần được gọi. • Dùng biến Static thay vì Global : – Cái hay của một biến static là nó là cục bộ của CT con, => tránh được các side efects. SE-SoICT KTLT-3.10 Last update 6-2010
3. Tính toán trước các giá trị • Nếu bạn phải tính đi tính lại 1 biểu thức, thì nên tính trước 1 lần và lưu lại giá trị, rồi dùng giá trị ấy sau này int f(int i) { static int[] values = if (i = 0) {0, 0, 2,3*3-3, , 9*9- { 9}; return i * i - i; int f(int i) { } if (i = 0) return 0; return values[i]; } return 0; } SE-SoICT KTLT-3.12 Last update 6-2010
4. Sử dụng các biến đổi số học! • Trình dịch không thể tự động xử lý if (a > sqrt(b)) x = a*a + 3*a + 2; Ít phép nhân hơn! if (a *a > b) x = (a+1)*(a+2); SE-SoICT KTLT-3.14 Last update 6-2010
5. Dùng “lính canh” . • Ý tưởng chung – Đặt giá trị cần tìm vào cuối xâu: “lính canh” – Luôn tìm thấy ! – Nhưng nế u vị trí > size => không tìm thây ! size = strlen(s); strcat(s, searchValue); pos = 0; while ( s[pos] != searchValue) do pos++; If (pos >= size) tim =0 else tim = 1; Có thể làm tương tự với mảng, danh sách SE-SoICT KTLT-3.16 Last update 6-2010
6. Không dùng các vòng lặp ngắn for (i =j; i<= j+3;i++) sum += q*i -i*7; i = j; sum += q*i -i*7; i ++; sum += q*i -i*7; i ++; sum += q*i-i*7; SE-SoICT KTLT-3.18 Last update 6-2010
7. Tính Sigmoid float sigmoid (float x ) { return 1.0 / (1.0 + exp(-x)) }; SE-SoICT KTLT-3.20 Last update 6-2010
8. Tính Sigmoid – Giải pháp • Thay vì tính hàm mọi lúc, người x0 sigmoid(x0) x sigmoid(x ) ta: 1 0 x2 sigmoid(x0) – Tính hàm tại N điểm và xây dựng 1 x3 sigmoid(x0) mảng. x4 sigmoid(x0) x sigmoid(x ) – Trong mỗi lần gọi sigmoid 5 0 x6 sigmoid(x0) • Tìm giá trị gần nhất của x và kết quả . ứng với giá trị ấy . . • Thực hiện nội suy tuyến tính - linear interpolation x99 sigmoid(x99) SE-SoICT KTLT-3.22 Last update 6-2010
9. Tính Sigmoid (tiếp) • Chọn số các điểm (N = 1000, 10000, v.v.) tùy theo độ chính xác mà bạn muốn – Tốn kếm thêm không gian bộ nhớ cho mỗi điểm là 2 float hay double tức là 8 – 16 bytes/ điểm • Khởi tạo giá trị cho mảng khi bắt đầu thực hiện. SE-SoICT KTLT-3.24 Last update 6-2010
10. Kết quả • Nếu dùng exp(x) : – Mỗi lần gọi mất khoảng 300 nanoseconds với 1 máy Pentium 4 tốc độ 2 Ghz. • Dùng tìm kiếm trên mảng và nội suy tuyến tính : – Mỗi lần gọi mất khoảng 30 nanoseconds • Tốc độ tăng gập 10 lần – Đổi lại phải tốn kếm thêm từ 64K -> 640 K bộ nhớ. SE-SoICT KTLT-3.26 Last update 6-2010
11. Những quy tắc cơ bản Fundamental Rules • Đơn giản hóa Code – Code Simplification : Hầu hết các chương trình chạy nhanh là đơn giản. Vì vậy, hãy đơn giản hóa chương trình để nó chạy nhanh hơn. Tuy nhiên • Đơn giản hóa vấn đề - Problem Simplification: Để tăng hiệu quả của chương trình, hãy đơn giản hóa vấn đề mà nó giải quyết. • Không ngừng nghi ngờ - Relentless Suspicion: Đặt dấu hỏi về sự cần thiết của mỗi mẩu code và mỗi trường , mỗi thuộc tính trong cấu trúc dữ liệu. • Liên kết sớm - Early Binding: Hãy thực hiện ngay công việc để tránh thực hiện nhiều lần sau này. SE-SoICT KTLT-3.28 Last update 6-2010
12. Quy tắc tăng tốc độ : cont. • Caching: Dữ liệu thường dùng cần phải dễ tiếp cận nhất, luôn hiện hữu. • Lazy Evaluation: Không bao giờ tính 1 phần tử cho đến khi cần để tránh những sự tính toán không cần thiết. SE-SoICT KTLT-3.30 Last update 6-2010
13. Quy tắc lặp : Loop Rules • Kết hợp các phép thử - Combining Tests: Trong vòng lặp càng ít kiểm tra càng tốt và tốt nhất chỉ một phép thử. LTV có thể phải thay đổi điều kiện kết thúc vòng lặp. “Lính canh (sentinel)” là một ví dụ cho quy tắc này. • Loại bỏ Loop : Với những vòng lặp ngắn thì cần loại bỏ vòng lặp, tránh phải thay đổi và kiểm tra điều kiện lặp. SE-SoICT KTLT-3.32 Last update 6-2010
14. GOOD PROGRAMMING STYLE Sau đây là các quy tắ c vế “programming style “ rút ra tư cuố n “The Elements of Programming Style" cuả tác giắ Kernighan và 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 chí 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 : • “Tính nhất quán”. Nếu bạn chấp nhận một cách thức đặt tên hàm hay biến, hằng thì hãy tuân thủ nó trong toàn bộ chương trình. • Đầu mỗi CT, nên có một đoạn chú thích • Mỗi CT con phải có một nhiệm vụ rõ ràng. Một CT con phải đủ ngắn để người đọc có thể nắm băt như một đơn vị, 1 chức năng. • Hãy dùng tối thiểu số các tham số của CT con. > 6 tham số cho 1 CT con là quá nhiều. SE-SoICT KTLT-3.34 Last update 6-2010
15. GOOD PROGRAMMING STYLE 1. Write clearly / don't be too clever – Viết rõ ràng – đừng quá thông minh (kỳ bí) 2. Say what you mean, simply and directly – Trình bày vấn đề 1 cách đơn giản, trực tiếp 3. Use library functions whenever feasible. – Sử dụng thư viện mọi khi có thể 4. Avoid too many temporary variables – Tránh dùng nhiều biến trung gian 5. Write clearly / don't sacrifice clarity for efficiency – Viết rõ ràng / đừng hy sinh sự rõ ràng cho hiệu quả SE-SoICT KTLT-3.36 Last update 6-2010
16. GOOD PROGRAMMING STYLE 13. Write first in easy-to-understand pseudo language; then translate into whatever language you have to use. – Trước tiên hãy viết ct bằng giả ngữ dễ hiểu, rồi hãy chuyển sang ngôn ngữ cần thiết. 14. Modularize. Use procedures and functions. – Mô đul hóa. Dùng các hàm và thủ tục 15. Avoid gotos completely if you can keep the program readable. – Tránh hoàn toàn việc dùng goto 16. Don't patch bad code /{ rewrite it. – Không chắp vá mã xấu – Viết lại đoạn code đó 17. Write and test a big program in small pieces. – Viết và kiểm tra 1 CT lớn thành từng CT con SE-SoICT KTLT-3.38 Last update 6-2010
17. GOOD PROGRAMMING STYLE 24. Use uniform input formats. – Hãy dùng các đầu vào theo các định dạng chuẩn. 25. Make sure all variable are initialized before use.- Hãy đảm bảo các biến được khởi tạo trước khi sử dụng 26. Test programs at their boundary values. – Hãy kiểm tra CT tại các cận 26. Check some answers by hand. – Kiểm tra 1 số câu trả lời bằng tay 27. 10.0 times 0.1 is hardly ever 1.0. – 10 nhân 0.1 không chắc đã = 1.0 28. 7/8 is zero while 7.0/8.0 is not zero. 7/8 =0 nhưng 7.0/8.0 <> 0 ? 29. Make it right before you make it faster. – Hãy làm cho CT chạy đúng, trước khi làm nó chạy nhanh SE-SoICT KTLT-3.40 Last update 6-2010
18. Program Style • Who reads your code? –The compiler –Other programmers This is a working raySE-SoICT tracer! (courtesy of Paul Heckbert)KTLT-3.42 Last update 6-2010
19. Structure: Spacing • Use readable/consistent spacing –VD: Gán mỗi phần tử mảng a[j] = j. –Bad code for (j=0;j<100;j++) a[j]=j; –Good code for (j=0; j<100; j++) a[j] = j; –Thường có thể dựa vào auto-indenting, tính năng trong trình soạn thảo SE-SoICT KTLT-3.44 Last update 6-2010
20. Structure: Indentation (cont.) • Use “else-if” cho cấu trúc đa lựa chọn v low=0 –VD: Bước so sánh trong tìm kiếm 2 nhị phân - binary search. 4 if (x v[mid]) low = mid + 1; 8 else 10 return mid; high=6 17 if (x v[mid]) x –Good code low = mid + 1; else 10 return mid; SE-SoICT KTLT-3.46 Last update 6-2010
21. Structure: “Paragraphs” • Dùng dòng trống để chia code thành các phần chính diam = 2 * radius; circum = PI * (double)diam; printf("A circle with radius %d has diameter %d\n", radius, diam); printf("and circumference %f.\n", circum); return 0; } SE-SoICT KTLT-3.48 Last update 6-2010
22. Structure: Expressions (cont.) • Dùng () để tránh nhầm lẫn –VD: Kiểm tra nếu n thỏa mãn j ”) có độ ưu tiên cao hơn các toán tử logic (vd “&&”), nhưng ai nhớ điều đó ? SE-SoICT KTLT-3.50 Last update 6-2010
23. Structure: Expressions (cont.) • Đơn giản hóa các biểu thức phức tạp –VD: Xác định các ký tự tương ứng với các tháng của năm –Bad code if ((c == 'J') || (c == 'F') || (c == 'M') || (c == 'A') || (c == 'S') || (c == 'O') || (c == 'N') || (c == 'D')) if ((c == 'J') || (c == 'F') || –Good code (c == 'M') || (c == 'A') || (c == 'S') || (c == 'O') || (c == 'N') || (c == 'D')) Nên xắp xếp các cơ cấu song song ! SE-SoICT KTLT-3.52 Last update 6-2010
24. Naming • Dùng tên gợi nhớ, có tính miêu tả cho các biến và hàm – VD : hovaten, CONTROL, CAPACITY • Dùng tên nhất quán cho các biến cục bộ – VD, i (not arrayIndex) cho biến chạy vòng lặp • Dùng chữ hoa, chữ thường nhất quán – VD., Buffer_Insert (Tên hàm) CAPACITY (hằng số) buf (biến cục bộ) • Dùng phong cách nhất quánkhi ghép từ – VD., frontsize, FrontSize, front_size • Dùng động từ cho tên hàm – VD., docsolieu(), inkq(), Check_Octal(), SE-SoICT KTLT-3.54 Last update 6-2010
25. Comments (cont.) • Chú thích cả đoạn (“paragraphs”) không chú thích#include từng dòng code #include int main(void) /* Read a circle's radius from stdin, and compute and write its diameter and circumference to stdout. Return 0 if successful. */ { const double PI = 3.14159; int radius; int diam; double circum; /* Read the circle’s radius. */ printf("Enter the circle's radius:\n"); if (scanf("%d", &radius) != 1) { fprintf(stderr, "Error: Not a number\n"); exit(EXIT_FAILURE); /* or: return EXIT_FAILURE; */ SE-SoICT KTLT-3.56 Last update} 6-2010
26. Function Comments • Mô tả những gì cần thiết đểgọi hàm 1 cách chính xác – Mô tả Hàm làm gì, chứ không phảinó làm như thế nào – Bản thân Code phải rõ ràng, dễ hiểu để biết cách nó làm việc – Nếu không, hãy viết chú thích bên trong định nghĩa hàm • Mô tả đầu vào: Tham số truyền vào, đọc file gì, biến tổng thể được dùng • Mô tả outputs: giá trị trả về, tham số truyền ra, ghi ra files gì, các biến tổng thể mà nó tác động tới SE-SoICT KTLT-3.58 Last update 6-2010
27. Function Comments (cont.) • Good function comment /* decomment.c */ int main(void) { /* Đọc 1 CT C qua stdin. Ghi ra stdout với mỗi chú thích thay bằng 1 dấu cách. Trả về 0 nếu thành công, EXIT_FAILURE nếu không thành công. */ } –Describes what the function does SE-SoICT KTLT-3.60 Last update 6-2010
28. Bottom-Up Design is Bad • Bottom-up design  1 2 – Thiết kế chi tiết 1 phần – Thiết kế chi tiết 1 phần khác – Lặp lại cho đến hết • Bottom-up design in programming – Viết phần đầu tiên của CT 1 cách chi tiết cho đến hết – Viết phần tiếp theo của CT 1 cách chi tiết cho đến hết 1 2 – Lặp lại cho đến hết 3 4 SE-SoICT KTLT-3.62 Last update 6-2010
29. Top-Down Design in Reality • Thiết kế CT Top-down trong thực tiễn : – Định nghĩa hàm main() = pseudocode – Tinh chỉnh từng lệnh pseudocode • Nếu gặp sự cố Oops! Xem lại thiết kế, và • Quay lại để tinh chỉnh pseudocode đã có, và tiếp tục – Lặp lại (mostly) ở mức sâu hơn, cụ thể hơn, cho đến khi các hàm đc định nghĩa xong 1 1’ 1’ 1’’ 2 Oops 2’ 3 2’ 3 2’’ 3’ 4 Oops 4’ 5 SE-SoICT KTLT-3.64 Last update 6-2010
30. Ví dụ về Input and Output I Tune every heart and every voice. Bid every bank withdrawal. N Let's all with our accounts rejoice. P In funding Old Nassau. In funding Old Nassau we spend more money every year. U Our banks shall give, while we shall live. T We're funding Old Nassau. O U Tune every heart and every voice. Bid every bank T withdrawal. Let's all with our accounts rejoice. In funding Old Nassau. In funding Old Nassau we P spend more money every year. Our banks shall give, U while we shall live. We're funding Old Nassau. T SE-SoICT KTLT-3.66 Last update 6-2010
31. Writing the Program • Key constructs – Từ - Word – Dòng - Line • Các bước tiếp theo – Viết pseudocode cho hàm main() – Tinh chỉnh • Lưu ý : Chú thích hàm và một số dòng trống được bỏ qua vì những hạn chế không gian Trình tự thiết kế là lý tưởng Trong thực tế, nhiều backtracking sẽ xảy ra SE-SoICT KTLT-3.68 Last update 6-2010
32. Reading a Word #include • nghĩa enum {MAX_WORD_LEN = 20}; int main(void) { char word[MAX_WORD_LEN + 1]; là gì? Việc này khá int wordLen; phức tạp nên cần for (;;) { wordLen = ReadWord(word); tách thành 1 hàm if ( ) { riêng return 0; } if ( ) { } int ReadWord(char *word) { } return 0; } } SE-SoICT KTLT-3.70 Last update 6-2010
33. Reading a Word (cont.) int ReadWord(char *word) { • Hmmm. ReadWord() int ch, pos = 0; chứa 1 vài đoạn code /* Bỏ qua whitespace. */ lặp lại => tách thành 1 ch = getchar(); hàm riêng : while (IsWhitespace(ch)) ch = getchar(); IsWhitespace(ch) /* Lưu các ký tự vào từ cho đến MAX_WORD_LEN . */ while (!IsWhitespace(ch) && (ch != EOF)) { if (pos < MAX_WORD_LEN) { word[pos] = (char)ch; pos++; } ch = getchar(); } word[pos] = '\0'; int IsWhitespace(int ch) { return (ch == ' ') || (ch == '\n') || (ch == '\t'); /* trả về đọ dài từ. */ } return pos; } SE-SoICT KTLT-3.72 Last update 6-2010
34. Saving a Word (cont.) • AddWord() void AddWord(const char *word, char *line, int *lineLen) { /* Nếu dòng đã chứa 1 số từ, thêm 1 dấu trắng. */ if (*lineLen > 0) { line[*lineLen] = ' '; line[*lineLen + 1] = '\0'; (*lineLen)++; } strcat(line, word); (*lineLen) += strlen(word); } SE-SoICT KTLT-3.74 Last update 6-2010
35. Deciding When to Print int main(void) { char word[MAX_WORD_LEN + 1]; int wordLen; char line[MAX_LINE_LEN + 1]; int lineLen = 0; • for (;;) { vừa dòng> wordLen = ReadWord(word); /* If no more words, print line Nghĩa là gì? with no justification. */ if ((wordLen == 0) && (lineLen > 0)) { puts(line); return 0; } /* Nếu từ không vừa dòng, thì */ if ((wordLen + 1 + lineLen) > MAX_LINE_LEN) { } AddWord(word, line, &lineLen); } SE-SoICT KTLT-3.76 Lastreturn update 06-2010; }
36. Printing with Justification (cont.) • Viết pseudocode cho WriteLine() void WriteLine(const char *line, int lineLen, int numWords) { for (i = 0; i ) else { } } } SE-SoICT KTLT-3.78 Last update 6-2010
37. Clearing the Line • Cuối cùng. nghĩa là gì ? • Tuy đơn giản, nhưng ta cũng xd thành 1 hàm int main(void) { int numWords = 0; ClearLine(line, &lineLen, &numWords); for (;;) { /* If word doesn't fit on this line, then */ if ((wordLen + 1 + lineLen) > MAX_LINE_LEN) { WriteLine(line, lineLen, numWords); ClearLine(line, &lineLen, &numWords); } addWord(word, line, &lineLen); void ClearLine(char *line, int numWords++; *lineLen, int *numWords) { } line[0] = '\0'; return 0; *lineLen = 0; } *numWords = 0; } SE-SoICT KTLT-3.80 Last update 6-2010
38. The “justify” Program #include #include enum {MAX_WORD_LEN = 20}; enum {MAX_LINE_LEN = 50}; int IsWhitespace(int ch) { return (ch == ' ') || (ch == '\n') || (ch == '\t'); } int ReadWord(char *word) { int ch, pos = 0; ch = getchar(); while (IsWhitespace(ch)) ch = getchar(); while (!IsWhitespace(ch) && (ch != EOF)) { if (pos < MAX_WORD_LEN) { word[pos] = (char)ch; pos++; } ch = getchar(); } word[pos] = '\0'; return pos; } SE-SoICT KTLT-3.82 Last update 6-2010
39. void WriteLine(const char *line, int lineLen, int numWords) { int extraSpaces, spacesToInsert, i, j; extraSpaces = MAX_LINE_LEN - lineLen; for (i = 0; i < lineLen; i++) { if (line[i] != ' ') putchar(line[i]); else { spacesToInsert = extraSpaces / (numWords - 1); for (j = 1; j <= spacesToInsert + 1; j++) putchar(' '); extraSpaces -= spacesToInsert; numWords ; } } putchar('\n'); } SE-SoICT KTLT-3.84 Last update 6-2010
40. Optimizing C and C++ Code • Đặt kích thước mảng = bội của 2 Với mảng, khi tạo chỉ số, trình dịch thực hiện các phép nhân, vì vậy, hãy đặt kích thước mảng bằng bôi số của 2 để phép nhân có thể đc chuyển thành phép toán dịch chuyển nhanh chóng • Đặt các case labels trong phạm vi hẹp Nếu số case label trong câu lệnh switch nằm trong phạm vi hẹp, trình dịch sẽ biến đổi thành if – else - if lồng nhau, mà tạo thành 1 bảng các chỉ số, như vậy thao tác sẽ nhanh hơn • Đặt các trường hợp thường gặp trong lệnh switch lên đầu Khi số các trường hợp tuyển chọn là nhiều và tách biệt, trình dịch sẽ biến lệnh switch thành các nhóm if – else –if lồng nhau. Nếu bố trí các case thường gặp lên trên, việc thực hiện sẽ nhanh hơn • Tái tạo các switch lớn thành các switches lồng nhau Khi số cases nhiều, hãy chủ động chia chúng thành các switch lồng nhau, nhóm 1 gồm những cases thường gặp, và nhóm 2 gồm những cases ít gặp=> kết quả là các phép thử sẽ ít hơn, tốc độ nhanh hơn SE-SoICT KTLT-3.86 Last update 6-2010
41. Optimizing C and C++ Code (tt) • Nên dùng int thay vì char hay short ( mất thời gian convert ), nếu biết int không âm, hãy dùng unsigned int • Hãy định nghĩa các hàm khởi tạo đơn giản • Thay vì gán, hãy khởi tạo giá trị cho biến • Hãy dùng danh sách khởi tạo trong hàm khởi tạo Employee::Employee(String name, String designation) { m_name = name; m_designation = designation; } /* === Optimized Version === */ Employee::Employee(String name, String designation): m_name(name), m_destignation (designation) { } • Đừng định nghĩa các hàm ảo tùy hứng : "just in case" virtual functions • Các hàm gồm 1 đến 3 dòng lệnh nên định nghĩa inline SE-SoICT KTLT-3.88 Last update 6-2010
42. switch ( queue ) { case 0 : letter = 'W'; break; case 1 : letter = 'S'; break; case 2 : letter = 'U'; break; } Hoặc có thể là : if ( queue == 0 ) letter = 'W'; else if ( queue == 1 ) letter = 'S'; else letter = 'U'; static char *classes="WSU"; letter = classes[queue]; SE-SoICT KTLT-3.90 Last update 6-2010
43. Tối ưu đoạn code sau : found = FALSE; for(i=0;i<10000;i++) { if( list[i] == -99 ) { found = TRUE; Nên thay bởi while } } if( found ) printf("Yes, there is a -99. !\n"); SE-SoICT KTLT-3.92 Last update 6-2010
44. • Tránh dùng ++, trong biểu thức lặp , vd while ( n ) { } • Dùng x * 0.5 thay vì x / 2.0. • x+x+x thay vì x*3 • Mảng 1 chiều nhanh hơn mảng nhiều chiều • Tránh dùng đệ quy SE-SoICT KTLT-3.94 Last update 6-2010