Bài giảng Kỹ thuật lập trình - Chương 2: Tăng hiệu quả chương trình - Vũ Đức Vượng
TĂNG HIỆU QUẢ
CHƯƠNG TRÌNH
VÀ PHONG CÁ CH
LẬP TRÌNH
Efficient Programs
Trước hết là giải thuật
◼ Hãy dùng giải thuật hay nhất có thể
◼ Sau đó hãy nghĩ tới việc tăng tính hiệu quả của code
◼ Ví dụ : Tính tổng của n số tự nhiên kế từ m
void main() {
void main()
{
long n,m,i , sum ;
long n,m , sum ;
cout << ‘ vào n ‘ ; cin << n;
cout << ‘ vào m ‘ ; cin << m;
cout << ‘ vào n ‘ ; cin << n;
cout << ‘ vào m ‘ ; cin << m;
sum =0;
sum =(m + m+ n) * n / 2;
cout << ‘ Tổng = ‘ <<sum;
for(i = m ; i < = m+n; i++)
sum += i;
}
cout << ‘ Tổng = ‘ <<sum;
2
}
Dùng chỉ thị chương trình dịch
Một số compilers có vai trò rất lớn trong việc
tối ưu chương trình
◼ Chúng phân tích sâu mã nguồn và làm mọi điều
“machinely” có thể
◼ Ví dụ GNU g++ compiler trên Linux/Cygwin cho
chương trình viết = c
g++ –O5 –o myprog myprog.c
có thể cải thiện hiệu năng từ 10% đến 300%
3
Nhưng...
Bạn vẫn có thể thực hiện những cải tiến mà
trình dịch không thể
Bạn phải loại bỏ tất cả những chỗ bất hợp lý
trong code
◼ Làm cho chương trình hiệu quả nhất có thể
Có thể phải xem lại khi thấy chương trình chạy
chậm
◼ Vậy cần tập trung vào đâu để cải tiến nhanh nhất,
tốt nhất ?
4
Writing Efficient Code
Xác định nguồn gây kém hiệu quả
◼ Dư thừa tính toán - redundant computation
◼ Chủ yếu
Trong các procedure
Các vòng lặp : Loops
5
Khởi tạo 1 lần, dùng nhiều lần
Before
float f()
{ double value = sin(0.25);
//
…..
}
After
double defaultValue = sin(0.25);
float f()
{ double value = defaultValue;
//
…..
6
}
Inline functions
Nếu 1 hàm trong c++ chỉ gồm những lệnh đơn
giản, không co 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 goi.
◼ Chương trình sẽ lớn hơn chút ít
◼ Nhưng nhanh hơn , không dùng stack– 4 bước khi
1 hàm được gọi …
7
Inline functions
#include <iostream>
#include <cmath>
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;
}
8
Static Variables
Kiểu dữ liệu Static tham chiếu tới global hay 'static'
variables , chúng được cấp phát bộ nhớ khi dịch
compile-time.
int int_array[100];
int main() {
static float float_array[100];
double double_array[100];
char *pchar;
pchar = (char *)malloc(100);
/* .... */
return (0);
}
9
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ẽ bị loại bỏ khi kết thúc ct con.
Khi bạn 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 bạn 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, bạn 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 1 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 1 biến static là nó là local của CT con, => tránh
được các side efects.
10
Stack, heap
Khi thực hiện , vùng dữ liệu data segment của 1 chương
trình được chia làm 3 phần :
◼ - static, stack, và heap data.
Static: global hay static variables
Stack data:
◼ - các biến cục bộ của ct con
- ví dụ double_array trong ví dụ trên.
Heap data:
◼ - Dữ liệu được cấp phát động (vd, pchar trong ví dụ trên).
◼ - Dữ liệu này sẽ còn cho đến khi ta giải phóng hoặc khi kết
thúc CT.
11
Macros
◼
#define max(a,b) (a>b?a:b)
Các hàm Inline cũng giống như macros vì cả 2 được khai triển khi dịch compile
time
◼ macros được khai triển bởi preprocessor, còn inline functions được truyền
bởi compiler.
Tuy nhiên có nhiều điểm khác biệt:
◼ Inline functions tuân thủ các thủ tục như 1 hàm binh thường.
◼ Inline functions có cùng syntax như các hàm khác, chỉ có điều là có thêm từ
khóa inline khi khai báo hàm.
◼ Các biểu thức truyền như là đối số cho inline functions được tính 1 lần.
Trong 1 số trường hợp, biểu thức truyền như tham số cho macros có thể
được tính lại nhiều hơn 1 lần.
◼ Bạn không thể gỡ rối cho macros, nhưng với inline functions thì có thể.
12
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
static int[] values =
int f(int i) {
{0, 0, 2,3*3-3, ..., 9*9-9};
if (i < 10 && i >= 0)
int f(int i) {
{
if (i < 10 && i >= 0)
return i * i - i;
{ return values[i];
}
}
return 0;
return 0;
}
13
}
Loại bỏ những biểu thức thông
thường
Đừng tính cùng một biểu thức nhiều lần!
Một số compilers có thể nhận biết và xử lý.
for (i = 1; i<=10;i++) x += strlen(str);
Y = 15 + strlen(str);
len = strlen(str);
for (i = 1;i<=10;i++) x += len;
Y = 15 + len;
14
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;
if (a *a > b)
x = (a+1)*(a+2);
15
Dùng “lính canh” -Tránh những
kiểm tra không cần thiết
Trước
char s[100], searchValue;
int pos,tim, size ;
….. Gán giá trị cho s, searchValue
…
size = strlen(s);
pos = 0;
while (pos < size) && (s[pos] != searchValue)
do pos++;
If (pos >= size) tim =0 else
tim = 1;
16
Dùng “lính canh” ….
Ý tưởng chung
◼ Đặt giá trị cần tìm vào cuối xâu
◼ Luôn tìm thấy !
◼ Nhưng nếu vị trí > size => khong tim thay !
size = strlen(s);
strcat(s, searchValue);
pos = 0;
while ( s[pos] != searchValue)
do pos++;
If (pos >= size) tim =0 else
tim = 1;
17
Có thể làm tương tự với mảng, danh sách …
Dịch chuyển những biểu thức bất
biến ra khỏi vòng lặp
Đừng lặp các biểu thức tính toán không cần
thiết
Một số Compilers có thể tự xử lý!
for (i =0; i<100;i++)
plot(i, i*sin(d));
M = sin(d);
for (i =0; i<100;i++)
plot(i, i*M);
18
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;
19
Giảm thời gian tính toán
Trong mô phỏng Neural
Network người ta
1
sigmoid (x) =
1+ e−kx
thường dùng hàm có tên
sigmoid
Với X dương lớn ta có
sigmoid(x) 1
Với x âm “lớn”
sigmoid (x) 0
20
Tải về để xem bản đầy đủ
95 trang
20160
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Kỹ thuật lập trình - Chương 2: Tăng hiệu quả chương trình - Vũ Đức Vượng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_ky_thuat_lap_trinh_tang_hieu_qua_chuong_trinh_vu_d.ppt
