Dãy số Fibonacci trong Python

Trong bài viết này, bạn sẽ học cách định nghĩa một loại chuỗi (Sequence) tùy chỉnh trong Python và cách triển khai chuỗi Fibonacci bằng loại chuỗi tùy chỉnh này. Việc hiểu và tạo ra các loại chuỗi tùy chỉnh giúp bạn mở rộng khả năng lập trình và tối ưu hóa các thao tác trên dữ liệu. Chuỗi Fibonacci, với cấu trúc đơn giản nhưng mạnh mẽ, sẽ là ví dụ hoàn hảo để minh họa cho quá trình này. Bằng cách xây dựng một loại chuỗi tùy chỉnh cho Fibonacci, bạn sẽ nắm vững cách thức hoạt động của các phương thức quan trọng và cách áp dụng chúng vào các tình huống thực tế.

Giới thiệu về loại chuỗi tùy chỉnh trong Python

Đôi khi, việc triển khai một loại chuỗi tùy chỉnh có các chức năng tương tự như các loại chuỗi tích hợp sẵn như tuples và lists là rất hữu ích.

Như bạn đã học được cho đến nay, một chuỗi có thể là bất biến hoặc có thể thay đổi. Trong bài hướng dẫn này, bạn sẽ tập trung vào việc định nghĩa một loại chuỗi bất biến tùy chỉnh.

Về cơ bản, một loại chuỗi bất biến nên hỗ trợ hai chức năng chính:

Bài viết này được đăng tại [free tuts .net]

• Trả về số lượng phần tử của chuỗi. Về mặt kỹ thuật, yêu cầu này không cần thiết.
• Trả về một phần tử tại một chỉ số nhất định hoặc ném ra ngoại lệ IndexError nếu chỉ số vượt quá giới hạn.

Nếu một đối tượng có thể thực hiện các yêu cầu trên, thì bạn có thể:

• Sử dụng cú pháp ngoặc vuông [] để truy xuất một phần tử theo chỉ số.
• Duyệt qua các phần tử của chuỗi bằng vòng lặp for, comprehension, v.v.

Về mặt kỹ thuật, một loại chuỗi tùy chỉnh cần triển khai các phương thức sau:

• __getitem__ – trả về một phần tử tại một chỉ số nhất định.
• __len__ – trả về độ dài của chuỗi.

Phương thức __getitem__

Phương thức __getitem__ có tham số chỉ số là một số nguyên. __getitem__ nên trả về một phần tử từ chuỗi dựa trên chỉ số được chỉ định.

Phạm vi của chỉ số nên từ 0 đến độ dài - 1. Nếu chỉ số vượt quá giới hạn, phương thức __getitem__ nên ném ra ngoại lệ IndexError.

Ngoài ra, phương thức __getitem__ có thể chấp nhận một đối tượng slice để hỗ trợ slicing.

Phương thức __len__

Nếu một chuỗi tùy chỉnh có phương thức __len__, bạn có thể sử dụng hàm tích hợp len để lấy số lượng phần tử từ chuỗi.

Giới thiệu về chuỗi Fibonacci trong Python

Chuỗi Fibonacci được phát hiện lần đầu tiên bởi Leonardo Fibonacci, một nhà toán học người Ý, vào khoảng năm 1170 sau Công nguyên.

Trong chuỗi Fibonacci, mỗi số là tổng của hai số đứng trước nó. Ví dụ:

1, 1, 2, 3, 5, 8, 13, 21, ...

Công thức sau mô tả chuỗi Fibonacci:

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) nếu n > 2

Một số nguồn tài liệu cho rằng chuỗi Fibonacci bắt đầu từ số 0, không phải 1 như sau:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Nhưng chúng ta sẽ tuân theo chuỗi Fibonacci gốc bắt đầu từ số 1.

Để tính toán một số Fibonacci trong Python, bạn định nghĩa một hàm đệ quy như sau:

def fib(n):
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)

Trong hàm đệ quy này, fib(1) và fib(2) luôn trả về 1. Và khi n lớn hơn 2, fib(n) = fib(n-2) + fib(n-1).

Để thêm câu lệnh ghi log để debug trong hàm fib, bạn có thể làm như sau:

def fib(n):
    print(f'Calculate Fibonacci of {n}')
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)

Và đây là kết quả của hàm fib khi tính toán Fibonacci của 6:

Calculate the Fibonacci of 6
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 5
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 1
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1

Như rõ ràng từ đầu ra, hàm fib có nhiều phép tính lặp lại. Ví dụ, nó phải tính Fibonacci của 3 ba lần. Điều này không hiệu quả.

Để giải quyết điều này, Python cung cấp một decorator gọi là lru_cache từ module functools.

lru_cache cho phép bạn lưu trữ kết quả của một hàm. Khi bạn truyền cùng một đối số cho hàm, hàm chỉ cần lấy kết quả từ bộ nhớ đệm thay vì tính toán lại.

Dưới đây là cách sử dụng decorator lru_cache để tăng tốc hàm fib:

from functools import lru_cache

@lru_cache
def fib(n):
    print(f'Calculate the Fibonacci of {n}')
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)

fib(6)

Kết quả:

Calculate the Fibonacci of 6
Calculate the Fibonacci of 4
Calculate the Fibonacci of 2
Calculate the Fibonacci of 0
Calculate the Fibonacci of 1
Calculate the Fibonacci of 3
Calculate the Fibonacci of 5    

Như rõ ràng từ đầu ra, số lượng phép tính đã giảm đáng kể.

Ví dụ về chuỗi Fibonacci trong Python

Đầu tiên, định nghĩa một lớp triển khai chuỗi Fibonacci:

class Fibonacci:
    def __init__(self, n):
        self.n = n

Phương thức __init__ nhận một số nguyên n chỉ định độ dài của chuỗi.

Thứ hai, định nghĩa một phương thức tĩnh để tính toán một số Fibonacci của một số nguyên:

@staticmethod
@lru_cache(2**16)
def fib(n):
    if n < 2:
        return 1
    return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)

Thứ ba, triển khai phương thức __len__ để bạn có thể sử dụng hàm tích hợp len để lấy số lượng phần tử từ chuỗi Fibonacci

def __len__(self):
    return self.n

Cuối cùng, triển khai phương thức __getitem__ để hỗ trợ việc truy xuất bằng cú pháp ngoặc vuông:

def __getitem__(self, index):
    if isinstance(index, int):
        if index < 0 hoặc index > self.n - 1:
            raise IndexError

        return Fibonacci.fib(index)

Phương thức __getitem__ nhận một chỉ số là một số nguyên. __getitem__ kiểm tra xem chỉ số có phải là số nguyên bằng cách sử dụng hàm isinstance.

Phương thức __getitem__ ném ra ngoại lệ IndexError nếu chỉ số vượt quá giới hạn. Nếu không, nó trả về số Fibonacci của chỉ số.

Đặt tất cả lại với nhau:

from functools import lru_cache

class Fibonacci:
    def __init__(self, n):
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, index):
        if isinstance(index, int):
            if index < 0 hoặc index > self.n - 1:
                raise IndexError

            return Fibonacci.fib(index)

    @staticmethod
    @lru_cache(2**16)
    def fib(n):
        if n < 2:
            return 1
        return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)

Bây giờ, bạn có thể lưu lớp Fibonacci trong module fibonacci.py và sử dụng nó trong một script mới.

Sử dụng chuỗi Fibonacci trong Python

Dưới đây là cách sử dụng chuỗi Fibonacci từ module fibonacci:

from fibonacci import Fibonacci

fibonacci = Fibonacci(10)

# truy xuất các phần tử qua chỉ số
print('Truy xuất chuỗi Fibonacci bằng ngoặc vuông []:')
print(fibonacci[0])
print(fibonacci[1])
print(fibonacci[2])

print('Truy xuất chuỗi Fibonacci bằng vòng lặp for:')
# sử dụng vòng lặp for
for f in fibonacci:
    print(f)

Kết quả:

Truy xuất chuỗi Fibonacci bằng ngoặc vuông []:
1
1
2
Truy xuất chuỗi Fibonacci bằng vòng lặp for:
1
1
2
3
5
8
13
21
34
55

Cách hoạt động:

• Tạo một instance mới của chuỗi Fibonacci chứa 10 phần tử.
• Truy xuất các phần tử của chuỗi Fibonacci bằng ngoặc vuông [].
• Sử dụng chuỗi Fibonacci trong vòng lặp for.

Thêm hỗ trợ slicing

Để hỗ trợ slicing như sau:

fibonacci[1:5]

...bạn cần thêm logic để xử lý đối tượng slice.

Trong fibonacci[1:5], đối số index của phương thức __getitem__ là một đối tượng slice có start là 1 và stop là 5.

Và bạn có thể sử dụng phương thức indices của đối tượng slice để lấy các chỉ số của các phần tử sẽ được trả về từ chuỗi:

indices = index.indices(self.n)

self.n là độ dài của chuỗi sẽ được slice. Trong trường hợp này, đó là số lượng phần tử trong chuỗi Fibonacci.

Để trả về một danh sách các số Fibonacci từ slice, bạn có thể truyền các chỉ số vào hàm range và sử dụng list comprehension như sau:

[Fibonacci.fib(k) for k in range(*indices)]

Dưới đây là phiên bản mới của chuỗi Fibonacci hỗ trợ slicing:

from functools import lru_cache

class Fibonacci:
    def __init__(self, n):
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, index):
        if isinstance(index, int):
            if index < 0 hoặc index > self.n - 1:
                raise IndexError

            return Fibonacci.fib(index)
        else:
            indices = index.indices(self.n)
            return [Fibonacci.fib(k) for k in range(*indices)]

    @staticmethod
    @lru_cache
    def fib(n):
        if n < 2:
            return 1
        return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)

Bây giờ, bạn có thể slice chuỗi Fibonacci như sau:

from fibonacci import Fibonacci

fibonacci = Fibonacci(10)
print(fibonacci[1:5])

Kết quả:

[1, 2, 3, 5]

Kết bài

Triển khai phương thức __len__ và __getitem__ để định nghĩa một chuỗi tùy chỉnh là bước quan trọng trong việc tạo ra các loại chuỗi mạnh mẽ và linh hoạt trong Python. Phương thức __len__ cho phép bạn sử dụng hàm len() để lấy số lượng phần tử trong chuỗi, trong khi phương thức __getitem__ giúp truy xuất phần tử theo chỉ số hoặc ném ra ngoại lệ IndexError nếu chỉ số vượt quá giới hạn. Bằng cách nắm vững cách triển khai hai phương thức này, bạn có thể dễ dàng xây dựng các loại chuỗi tùy chỉnh phù hợp với nhu cầu cụ thể của mình, tối ưu hóa các thao tác trên dữ liệu và làm cho mã nguồn của bạn trở nên hiệu quả hơn.