Bài giảng Tối ưu hóa chương trình - Nguyễn Tuấn Đăng

Nguyên lý và phương pháp lập trình Tối ưu hĩa chương trình TS. Nguyễn Tuấn ðăng 1 Tối ưu hĩa chương trình • Tổng quát • Khi nào cần tối ưu hĩa? • Một số kỹ thuật tối ưu hĩa chương trình – Ví dụ minh họa – Chương trình – Các tối ưu hĩa logic – Sử dụng hợp lý các các biểu thức trung gian – Tránh khai căn bậc 2 – Chuyển đổi các cấu trúc dữ liệu – Chuyển vị trí mã chương trình – Thứ tự tính tốn • Tổng kết 2 Tổng quan • Mục đích của tối ưu hĩa chương trình là nhằm giảm thiểu : – Thời gian • Thời gian chạy chương trình • Thời gian trả lời – Khơng gian • Khơng gian lưu trữ thứ cấp • Bộ nhớ chính • Các chiến lược tối ưu hĩa – Tối ưu theo mục tiêu được ưu tiên – Cân đối các mục tiêu: • Khơng gian và thời gian • ðộ phức tạp 3 Tổng quan (tt) • Khĩ khăn của vấn đề tối ưu hĩa chương trình : – Cĩ nhiều chiến lược khác nhau • Phải quyết định : – Tối ưu hĩa cái gì – khơng gian hay thời gian? – Tối ưu hĩa ở đâu trong chương trình? 4 Khi nào cần tối ưu hĩa? • Khi chương trình khơng đạt được hiệu quả hợp lý về khơng gian và thời gian • Khi cĩ khả năng giảm thiểu độ phức tạp của chương trình 5 Một số kỹ thuật tối ưu hĩa chương trình Ví dụ minh họa • Bài tốn: hành trình của người đi bán hàng – Input: n điểm trên bản đồ – Output : một đường đi ngắn nhất, chỉ đi qua mỗi điểm một lần 6 Ví dụ minh họa (tt) n n! n! with exponent 5 120 1.2x10e2 10 3,628,800 3.6x10e6 15 1,307,674,368,000 1.3x10e12 20 2,432,902,008,176,640,000 2.4x10e18 O(n2) O(n!)start 7 Chương trình • Dữ liệu • Thuật tốn begin F F F T 1 n thisPt maxPts real boolean ptArr visited for i in 1..n [khởi tạo visited] loop visited(i) := False end thisPt := n [bắt đầu từ n] visited(n) := True 8 for i in 2..n loop [set closePt = điểm gần nhất với thisPt] [output thisPt "->" closePt] thisPt := closePt [đi tiếp] Chương trình (tt) visited(closePt) := True end end 9 Chương trình (tt) [set closePt = nearest unvisited point] closeDist := maxreal for j in 1..n loop if not visited(j) and dist(thisPt, j) < closeDist then closeDist := dist(thisPt, j) closePt := j end end 10 Các tối ưu hĩa logic • Biến đổi 1: not visited(j) => unvisited(j) – Thời gian: giảm nhẹ – Khơng gian, độ phức tạp: giảm nhẹ • Biến đổi 2: if a and b ... => if a and then b ... [Ada] if (a) { if (b) } ... [Java] – Thời gian: giảm nhiều khi a thường xuyên sai – Khơng gian, độ phức tạp: tăng nhẹ • Các biến đổi 1 & 2 là độc lập 11 Sử dụng hợp lý các biểu thức trung gian • Kết quả của các biến đổi 1 & 2 trong vịng lặp: if unvisited(j) then if dist(thisPt, j) < closeDist then closeDist := dist(thisPt, j) closePt := j end end • Biến đổi 3: p(e) => v := e p(v) 12 Sử dụng hợp lý các biểu thức trung gian (tt) – Qui tắc: if (biểu thức e xuất hiện nhiều hơn một lần và khơng cĩ hiệu ứng lề) and (các biến khơng bị thay đổi bên trong các đánh giá biểu thức) then tính v := e [v là biến để ghi nhớ một giá trị] thay thế e trong p bằng v end – Cĩ thể khĩ kiểm tra các hiệu ứng lề – Thời gian: giảm (giảm nhẹ trong trường hợp này) – Khơng gian: giảm mã chương trình – ðộ phức tạp: giảm 13 Tránh khai căn bậc 2 • Kết quả của phép biến đổi 3 với e=dist(thisPt, j) if unvisited(j) then thisDist := dist(thisPt, j) if thisDist < closePt then closeDist := thisDist closePt := j end End • Biến đổi 4: thay thế dist(i, j) = sqrt(e) bằng distSqrd(i, j) = e 14 Tránh khai căn bậc 2 (tt) • Trong đĩ, e = sqr(ptArr(i).X - ptArr(j).X) + sqr(ptArr(i).Y - ptArr(j).Y) – Qui tắc: x2 x 0 – Thời gian: giảm đáng kể – Khơng gian: giảm nhẹ – ðộ phức tạp: thay đổi ít 15 Chuyển đổi các cấu trúc dữ liệu • Biến đổi 5: biểu diễn unvisited bằng một mảng số nguyên, sao cho: – unvisited(1..highPt) = số điểm chưa viếng thăm, – unvisited(highPt + 1..n) = số điểm đã viếng thăm – Thời gian: giảm ít – Khơng gian: tăng nhiều – ðộ phức tạp: tăng nhưng làm rõ các bất biến vịng lặp 16 Chuyển đổi các cấu trúc dữ liệu begin for i in 1..n loop unvisited(i):=i unvisited(i):=True end thisPt:=unvisited(n) thisPt:=n highPt:=n-1 unvisited(n):=False while highPt>0 <= for j in 2..n loop closeDist:=maxreal 17 Chuyển đổi các cấu trúc dữ liệu (tt) for i in 1..highPt for j in 1..n loop [compare distance] if unvisited(j) end end thisPt:=unvisited(closePt) thisPt:=closePt swapUnvisited(closePt, highPt) highPt:=highPt-1 unvisited(closePt):=False end 18 Chuyển vị trí mã chương trình • Biến đổi 6: distSqrd(...) => mã inline – Thời gian: tiết kiệm thời gian (ít) – Khơng gian: thường tăng – ðộ phức tạp: tăng • Biến đổi 7: chuyển các biểu thức bất biến ra khỏi vịng lặp – Thời gian: giảm – Khơng gian: tăng nhẹ – ðộ phức tạp: thay đổi chút ít 19 Chuyển vị trí mã chương trình (tt) thisX:=ptArr(thisPt).X thisY:=ptArr(thisPt).Y closeDist:=maxreal i in 1..highPt loop thisDist:=sqr(ptArr(unvisited(i)).X - thisX) + sqr(ptArr(unvisited(i)).Y - thisY) if thisDist < closeDist then closePt:=i closeDist:=thisDist end end 20