Ghi nhớ
Ghi nhớ
Ghi nhớ là một kỹ thuật lưu trữ kết quả để tránh thực hiện các phép tính giống nhau nhiều lần.
Sử dụng tính năng ghi nhớ để tìm số Fibonacci thứ \(n\)
Số Fibonacci thứ \(n\) có thể được tìm thấy bằng cách sử dụng đệ quy. Đọc thêm về cách thực hiện trên trang này .
Vấn đề với cách triển khai này là số lượng tính toán và lệnh gọi đệ quy "bùng nổ" khi cố gắng tìm số Fibonacci cao hơn, bởi vì các phép tính tương tự được thực hiện lặp đi lặp lại.
Ví dụ
Tìm số Fibonacci thứ 6 bằng đệ quy:
def F(n):
print('Computing F('+str(n)+')')
if n <= 1:
return n
else:
return F(n - 1) + F(n - 2)
print('F(6) = ',F(6)) Chạy ví dụ »Như bạn có thể thấy khi chạy ví dụ trên, có 25 phép tính, với cùng một phép tính được thực hiện nhiều lần, ngay cả khi chỉ tìm số Fibonacci thứ 6.
Nhưng việc sử dụng tính năng ghi nhớ có thể giúp tìm số Fibonacci thứ \(n\)th bằng cách sử dụng đệ quy hiệu quả hơn nhiều.
Chúng tôi sử dụng tính năng ghi nhớ bằng cách tạo một memo mảng để giữ các số Fibonacci, sao cho số Fibonacci n có thể được tìm thấy dưới dạng phần tử memo[n] . Và chúng ta chỉ tính số Fibonacci nếu nó chưa tồn tại trong mảng memo .
Ví dụ
Tìm số Fibonacci thứ 6 bằng đệ quy nhưng sử dụng tính năng ghi nhớ để tránh các lệnh gọi đệ quy không cần thiết:
def F(n):
if memo[n] != None: # Already computed
return memo[n]
else: # Computation needed
print('Computing F('+str(n)+')')
if n <= 1:
memo[n] = n
else:
memo[n] = F(n - 1) + F(n - 2)
return memo[n]
memo = [None]*7
print('F(6) = ',F(6))
print('memo = ',memo) Chạy ví dụ »Như bạn có thể thấy bằng cách chạy các ví dụ trên, tính năng ghi nhớ rất hữu ích để giảm số lượng tính toán.
Số lượng tính toán giảm từ 25 trong mã ban đầu xuống chỉ còn 7 trong ví dụ cuối cùng bằng cách sử dụng tính năng ghi nhớ và lợi ích của việc sử dụng tính năng ghi nhớ tăng lên rất nhanh theo mức độ cao của số Fibonacci mà chúng ta muốn tìm.
Việc tìm số Fibonacci thứ 30 yêu cầu 2.692.537 phép tính trong mã ban đầu, nhưng nó chỉ yêu cầu 31 phép tính trong thuật toán được triển khai bằng cách sử dụng tính năng ghi nhớ!
Bạn nhận được kết quả này bằng cách chạy mã bên dưới.
Ví dụ
Xem sự khác biệt trong các phép tính để tìm số Fibonacci thứ 30, có và không có tính năng ghi nhớ:
computation_count = 0
def F(n):
global computation_count
computation_count += 1
if n <= 1:
return n
else:
return F(n - 1) + F(n - 2)
computation_count_mem = 0
def F_mem(n):
if memo[n] != None: # Already computed
return memo[n]
else: # Computation needed
global computation_count_mem
computation_count_mem += 1
if n <= 1:
memo[n] = n
else:
memo[n] = F_mem(n - 1) + F_mem(n - 2)
return memo[n]
print('F(30) = ',F(30))
print(f'Number of computations: {computation_count}')
print('\nUsing memoization:')
memo = [None]*31
print('F(30) = ',F_mem(30))
print(f'Number of computations with memoiztion: {computation_count_mem}') Chạy ví dụ »Ghi nhớ trong cây AVL
Để biết thêm chi tiết về Cây AVL là gì, vui lòng xem trang này .
Cây AVL là một loại Cây nhị phân có khả năng tự cân bằng.
Mỗi khi một nút được chèn hoặc xóa khỏi cây AVL, hệ số cân bằng phải được tính toán cho tất cả các tổ tiên, sử dụng chiều cao của cây con trái và cây con phải để tìm hiểu xem có cần xoay vòng để khôi phục lại sự cân bằng hay không.
Để tránh tính toán chiều cao của mỗi nút (đi xuống các nút lá) để tính hệ số cân bằng, mỗi nút có chiều cao cây con được lưu trữ.
Ví dụ
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1 Chạy ví dụ »Điều này có nghĩa là để tìm hệ số cân bằng cho một nút, chiều cao của nút con bên trái đã được lưu trữ sẽ được trừ vào chiều cao của nút con bên phải đã được lưu trữ, không cần tính toán nào khác.
Lưu trữ chiều cao trong cây AVL là một hình thức ghi nhớ, vì các giá trị được lưu trữ để tránh phải tính lại. Trong cây AVL, khi chiều cao được lưu trữ như thế này thì nó được gọi là thuộc tính tăng cường .
Thuộc tính tăng cường là thuộc tính của một phần tử không cần phải được lưu trữ nhưng được lưu trữ để giúp hoạt động hiệu quả hơn.
Tất nhiên, độ cao của nút phải được tính toán tại một số điểm, nhưng việc đó chỉ được thực hiện khi thực sự cần thiết, bằng cách sử dụng tính năng truy tìm lại .
