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á
Chương 3. Viꢀt code
hiꢁu quꢂ
(3LT – 2BT)
SE-SoICT
KTLT-3.1
Last update 8-2010
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 ;
cout << ‘ vào n ‘ ; cin << n;
cout << ‘ vào m ‘ ; cin << m;
sum =0;
long n,m , sum ;
cout << ‘ vào n ‘ ; cin << n;
cout << ‘ vào m ‘ ; cin << m;
sum =(m + m+ n-1) * n / 2;
cout << ‘ Tổng = ‘ <<sum;
}
for(i = m ; i < m+n; i++)
sum += i;
//TD m=3, n=4 => KQ = 18!
cout << ‘ Tổng = ‘ <<sum;
SE-SoICT
KTLT-3.2
}
Dùng chỉ thị chương trình dịch
• Một số Chương trình dịch 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 bằng c:
• g++ –O5 –o myprog myprog.c
có thể cải thiện hiệu năng từ 10% đến 300%
SE-SoICT
KTLT-3.3
Last update 6-2010
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 ?
SE-SoICT
KTLT-3.4
Last update 6-2010
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 procedures
• Các vòng lặp : Loops
SE-SoICT
KTLT-3.5
Last update 6-2010
Khởi tạo 1 lần, dùng nhiều lần
• Before
float f()
{ double value = sin(0.25);
//
…..
}
double defaultValue = sin(0.25);
float f()
• After
{ double value = defaultValue;
//
…..
}
SE-SoICT
KTLT-3.6
Last update 6-2010
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 …
SE-SoICT
KTLT-3.7
Last update 6-2010
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;
}
SE-SoICT
KTLT-3.8
Last update 6-2010
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);
}
SE-SoICT
KTLT-3.9
Last update 6-2010
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
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 cꢀ pháp như các hàm khác, song 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ể.
SE-SoICT
KTLT-3.11
Last update 6-2010
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 =
{0, 0, 2,3*3-3, ..., 9*9-
9};
if (i < 10 && i >= 0)
{
return i * i - i;
int f(int i) {
}
if (i < 10 && i >= 0)
return values[i];
return 0; }
return 0;
}
SE-SoICT
KTLT-3.12
Last update 6-2010
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;
SE-SoICT
KTLT-3.13
Last update 6-2010
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)
ꢀt phꢁp nhân hơn!
x = (a+1)*(a+2);
SE-SoICT
KTLT-3.14
Last update 6-2010
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;
SE-SoICT
KTLT-3.15
Last update 6-2010
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
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);
SE-SoICT
KTLT-3.17
Last update 6-2010
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
Giꢂm thời gian tính toán
• Trong mô phỏng Neural
1
Network người ta
thường dùng hàm có tên
sigmoid
sigmoid (x) =
1+ e−kx
• Với X dương lớn ta có
sigmoid(x) 1
• Với x âm “lớn”
sigmoid (x) 0
KTLT-3.19
Last update 6-2010
SE-SoICT
Tính Sigmoid
float sigmoid (float x )
{
return 1.0 / (1.0 + exp(-x))
};
SE-SoICT
KTLT-3.20
Last update 6-2010
Tải về để xem bản đầy đủ
94 trang
16000
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 3: Viết code hiệu quả - Lương Mạnh Bá", để 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_chuong_3_viet_code_hieu_qua_luo.ppt
