Последовательность Фибоначчи в Python и пользовательский тип Sequence

АвторДмитрий Захаров Часы

В этом руководстве вы узнаете, как определить пользовательский тип последовательности в Python и как реализовать последовательность Фибоначчи с использованием пользовательского типа Sequence.

Содержание

Введение в пользовательский тип Sequence в Python

Иногда полезно реализовать собственный тип последовательности, который имеет функции, аналогичные встроенному типу последовательности, например кортежи и списки.

Как вы уже узнали, последовательность может быть изменяемой или неизменяемой. В этом руководстве вы сосредоточитесь на определении пользовательского неизменяемого типа последовательности.

По сути, неизменяемый тип последовательности должен поддерживать две основные функции:

  • Возвращает количество элементов последовательности. Технически это требование не является необходимым.
  • Возвращать элемент по заданному индексу или вызывать IndexError, если индекс выходит за пределы.

Если объект соответствует вышеуказанным требованиям, вы можете:

  • Использовать синтаксис квадратных скобок [] для получения элемента по индексу.
  • Перебрать элементы последовательности, используя цикл for, comprehension и т. д.

Технически пользовательский тип Sequence должен реализовывать следующие методы:

  • __getitem__ — возвращает элемент по заданному индексу.
  • __len__ – возвращает длину последовательности.

1) Метод __getitem__

Метод __getitem__ имеет аргумент индекса, который является целым числом. ___getitem__ должен возвращать элемент из последовательности на основе указанного индекса.

Диапазон индекса должен быть от нуля до длины — 1. Если индекс выходит за пределы, метод __getitem__ должен вызвать исключение IndexError. Кроме того, метод __getitem__ может принимать объект среза для поддержки нарезки.

2) Метод __len__

Если пользовательская последовательность имеет метод __len__, вы можете использовать встроенную функцию len, чтобы получить количество элементов из последовательности.

Последовательность Фибоначчи

Последовательность Фибоначчи была впервые открыта Леонардо Фибоначчи, итальянским математиком, в 1170 году.

В последовательности Фибоначчи каждое число представляет собой сумму двух предшествующих ему чисел. Например:

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

Следующая формула описывает последовательность Фибоначчи:

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) if n > 2

Некоторые источники утверждают, что последовательность Фибоначчи начинается с нуля, а не с 1, например:

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

Но мы будем придерживаться исходной последовательности Фибоначчи, которая начинается с единицы.

Чтобы вычислить число Фибоначчи в Python, вы определяете рекурсивную функцию следующим образом:

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

В этой рекурсивной функции fib(1) и fib(2) всегда возвращают 1. А когда n больше 2, fib(n) = fib(n-2) – fib(n-1)

Следующее добавляет оператор в начало функции fib для отладки целей:

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

А здесь показан результат функции fib при вычислении Фибоначчи, равного 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

Как ясно видно из выходных данных, функция Fib имеет много повторений. Например, она должна вычислить Фибоначчи 3 три раза. Это неэффективно. Чтобы решить эту проблему, Python предоставляет декоратор lru_cache из модуля functools.

lru_cache позволяет кэшировать результат функции. Когда вы передаете в функцию тот же аргумент, функция просто получает результат из кеша, а не пересчитывает его.

Ниже показано, как использовать декоратор lru_cache для ускорения функции 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)

Выход:

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

Как ясно видно из результатов, количество вычислений значительно сокращается.

Пример последовательности Фибоначчи в Python

  • Сначала определите класс, реализующий последовательность Фибоначчи:
class Fibonacci:
    def __init__(self, n):
        self.n = n

Метод __init__ принимает целое число n, указывающее длину последовательности.

  • Во-вторых, определите статический метод, который вычисляет число Фибоначчи для целого числа:
@staticmethod
@lru_cache(2**16)
def fib(n):
    if n < 2:
        return 1
    return Fibonacci.fib(n-2) + Fibonacci.fib(n-1)
  • В-третьих, реализуйте метод __len__, чтобы можно было использовать встроенную функцию len для получения количества элементов последовательности Фибоначчи:
def __len__(self):
    return self.n
  • Наконец, реализуйте метод __getitem__ для поддержки индексации с помощью синтаксиса квадратных скобок:
def __getitem__(self, index):
    if isinstance(index, int):
        if index < 0 or index > self.n - 1:
            raise IndexError

        return Fibonacci.fib(index)

Метод __getitem__ принимает индекс, который является целым числом. __getitem__ проверяет, является ли индекс целым числом, используя функцию isinstance.

Метод __getitem__ вызывает исключение IndexError, если индекс выходит за пределы. В противном случае он возвращает число Фибоначчи индекса.

Собираем все вместе.

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 or 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)

Нет, вы можете сохранить класс Фибоначчи в модуле fibonacci.py и использовать его в новом скрипте.

Использование последовательности Фибоначчи

Ниже показано, как использовать последовательность Фибоначчи из модуля fibonacci:

from fibonacci import Fibonacci

fibonacci = Fibonacci(10)

# access elements via indices
print('Accessing Fibonacci sequence using []:')
print(fibonacci[0])
print(fibonacci[1])
print(fibonacci[2])

print('Accessing Fibonacci sequence using for loop:')
# using for loop
for f in fibonacci:
    print(f)

Выход:

Accessing Fibonacci sequence using []:
1
1
2
Accessing Fibonacci sequence using for loop:
1
1
2
3
5
8
13
21
34
55

Как это работает.

  • Сначала создайте новый экземпляр последовательности Фибоначчи, содержащий 10 элементов.
  • Во-вторых, получите доступ к элементам последовательности Фибоначчи, используя квадратные скобки [].
  • В-третьих, используйте последовательность Фибоначчи в цикле for.

Добавление поддержки нарезки

Чтобы поддержать нарезку следующим образом:

fibonacci[1:5]

… вам нужно добавить логику для обработки объекта среза.

В fibonacci[1:5] индексный аргумент метода __getitem__ представляет собой объект среза, начало которого равно 1, а конец — 5.

И вы можете использовать метод index объекта среза, чтобы получить индексы элементов, возвращаемых из последовательности:

indices = index.indices(self.n)

Self.n — это длина последовательности, которая будет нарезана. В данном случае это количество элементов последовательности Фибоначчи.

Чтобы вернуть список чисел Фибоначчи из среза, вы можете передать индексы в функцию range и использовать понимание списка следующим образом:

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

Ниже показана новая версия последовательности Фибоначчи, поддерживающая нарезку:

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 or 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)

Теперь вы можете нарезать последовательность Фибоначчи следующим образом:

from fibonacci import Fibonacci

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

Выход:

[1, 2, 3, 5]

Python Web Developer

Похожие посты
Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *