Search…

Memoization - Kỹ Thuật Tối Ưu Hiệu Suất Tính Toán

06/05/20214 min read
Nếu bài toán nào tính toán quá lâu trong quá trình thực thi có thể tính trước và lưu trữ lại kết quả để sử dụng khi cần.

Các phép tính toán tốn kém nhiều thời gian như tính toán lượng giác, các phép lấy căn thường dùng như √2 √3, Fibonacci cần được tối ưu có thể suy nghĩ đến phương pháp tính trước, hiện tại C++ cũng hỗ trợ constexpr để các phép toán thông dụng tính trước trong quá trình biên dịch cho thấy sự hữu dụng của phương pháp này.

Giả sử cần sử dụng nhiều phép tính Sin - Cos - Tang - Cotang (sine, cosine, tangent, cotangent). Việc tính toán trước này hiển hiện trong rất nhiều ứng dụng, có thể xem một số ví dụ sau để tiếp cận nhanh.

Trong lúc xử lý giả sử gọi hàm sin(α) hàm này trả về một số thực và tiến hành tính toán trả về kết quả với công thức.

(-1)0 * x2*0+1 / (2*0 + 1)! + (-1)1 * x2*1+1 / (2*1 + 1)! + (-1)2 * x2*2+1 / (2*2 + 1)! + ... + (-1)n * x2n+1 / (2n + 1)!

Nếu kết quả được giới hạn trong yêu cầu phần mềm, việc tính sin của 1 góc với giới hạn là từ 0 độ cho tới 359 độ và các giá trị của góc là số nguyên, có 1 giải pháp đó là tính trước 360 độ này.

Memoization là thuật ngữ để chỉ kỹ thuật thực hiện điều này.

Hiện thực hàm sin cho 360 độ

Ý tưởng

Tạo một mảng có 360 phần tử kiểu số thực. Lần lượt gán các giá trị cho từng phần tử sao cho tương ứng phần tử thứ 0 chính là giá trị tại sin của 0 độ, phần tử thứ 1 sẽ có giá trị là giá trị của sin 1 độ, và cứ thế cho đến phần tử thứ 359.

static double sins[360] =
{
	0.0,			// Phần tử thứ 0
	0.017452406437284660,
	0.034899496702503266,
	......,
	1.0,			// Phần tử thứ 90
	......,
	-0.017452406436871508	// Phần tử thứ 359
};

Xây dựng hàm sin để lấy giá trị từ mảng đã cho trước, bất kỳ góc nào (lớn hơn 359 độ hoặc nhỏ hơn 0 độ) phải được chuyển về phạm vi từ 0 độ đến 359 độ, do lượng giác của các góc này có tính lặp lại.

double sin(int angle)
{
	return sins[angle % 360];
}

Xây dựng các hàm cos, tang, cotang

Việc xây dựng các hàm khác để tính cos, tang, cotang tương tự như tính sin, nhưng tang và cotang có điểm vô cực, cần kiểm soát được 2 giá trị vô cực.

Thuận lợi & bất lợi

Thuận lợi

  • Việc tính trước và lưu trữ kết quả trước thời điểm thực thi giúp cho chương trình có sẵn kết quả, chỉ cần lấy kết quả sử dụng do đó không tốn nhiều thời gian tính lại, giúp tối ưu hơn về tốc độ.
  • Giúp cho kết quả đồng nhất trên nhiều hệ thống tính toán khác nhau, có thể kết quả tính toán tùy vào độ chính xác mà các hệ thống khác nhau có thể khác nhau đôi chút, nhưng với việc tính toán trước từ một nguyên tắc chung thì kết quả sẽ đồng nhất.

Bất lợi

  • Tốn tài nguyên lưu trữ, nếu việc tính toán trước là hiệu ứng, hình ảnh (như particle trong game thay bằng Sprite) sẽ tốn nhiều vùng nhớ hơn.
  • Giảm độ linh động, ví dụ là particle trong game sẽ giảm đi độ ngẫu nhiên lúc thực thi (do hiệu ứng lưu trong Sprite đã cố định bằng các frame vẽ), về hàm tính sin như trên, ta cũng không thể làm được nhiều hơn như làm thêm cho các góc bất kỳ (kiểu số thực) vì sức ta sẽ có giới hạn.
  • Nếu ứng dụng cần thay đổi quá nhiều, sẽ không có cách nào biết được cần những loại input nào để lưu trước.

Với mỗi ngôn ngữ lập trình khác nhau sẽ có sự hỗ trợ của ngôn ngữ đó hoặc các thư viện hỗ trợ thêm, nên sử dụng các thư viện này trong trường hợp phát triển sản phẩm. Trong lập trình thực tế, có thể thấy được ý tưởng này thông qua các bảng ánh xạ dữ liệu hoặc chỉ mục.

IO Stream

IO Stream Co., Ltd

30 Trinh Dinh Thao, Hoa Thanh ward, Tan Phu district, Ho Chi Minh city, Vietnam
+84 28 22 00 11 12
developer@iostream.co

383/1 Quang Trung, ward 10, Go Vap district, Ho Chi Minh city
Business license number: 0311563559 issued by the Department of Planning and Investment of Ho Chi Minh City on February 23, 2012

©IO Stream, 2013 - 2024