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

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

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

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

У неизменяемой последовательность должно быть две основные возможности:

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

Если объект удовлетворяет вышеуказанным требованиям, получится производить следующие действия:

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

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

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

1) Метод getitem

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

Диапазон значений index: от нуля до length - 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) если 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).

Добавим print() в начало функции, чтобы посмотреть, как она работает, и вызовем функцию fib() с аргументом 6.

def fib(n):
    print(f'Считаю {n} число Фибоначчи')
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)


fib(6)

Вывод

Считаю 6 число Фибоначчи
Считаю 4 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 3 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 5 число Фибоначчи
Считаю 3 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 4 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 3 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи

Как вы видите, функция fib() часто повторяется.

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

Чтобы решить эту проблему, в Python есть декоратор под названием lru_cache из модуля functools.

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

Ниже показано, как использовать декоратор lru_cache для ускорения работы функции fib():

from functools import lru_cache


@lru_cache
def fib(n):
    print(f'Считаю {n} число Фибоначчи')
    if n < 2:
        return 1
    return fib(n-2) + fib(n-1)


fib(6)

Вывод

Считаю 6 число Фибоначчи
Считаю 4 число Фибоначчи
Считаю 2 число Фибоначчи
Считаю 0 число Фибоначчи
Считаю 1 число Фибоначчи
Считаю 3 число Фибоначчи
Считаю 5 число Фибоначчи

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

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

1. Сначала определим класс, реализующий последовательность Фибоначчи:

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

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

2. Теперь определим статический метод, который вычисляет значение определенного числа Фибоначчи:

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

3. Реализуем метод __len__, чтобы мы могли использовать встроенную функцию len() для получения количества элементов из последовательности Фибоначчи:

def __len__(self):
    return self.n

4. Реализуем метод __getitem__ для поддержки индексации с помощью синтаксиса квадратных скобок []:

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

        return Fibonacci.fib(index)

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

Если index выходит за границы последовательности, __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)

Кастомная последовательность Фибоначчи в виде Python-класса готова. Однако вы не сможете просто сохранить этот код в модуле fibonacci.py и использовать его в другом скрипте.

Давайте разберемся, как использовать созданную последовательность.

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

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

from fibonacci import Fibonacci

fibonacci = Fibonacci(10)

# используем []
print('Используем последовательность Фибоначчи с помощью []:')
print(fibonacci[0])
print(fibonacci[1])
print(fibonacci[2])

print('Используем последовательность Фибоначчи с помощью цикла for:')
# используем for
for f in fibonacci:
    print(f)

Вывод

Используем последовательность Фибоначчи с помощью []:
1
1
2
Используем последовательность Фибоначчи с помощью цикла for:
1
1
2
3
5
8
13
21
34
55

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

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

Добавляем поддержку срезов

Чтобы можно было делать срезы нашей последовательности, как показано ниже,

fibonacci[1:5]

... нужно добавить соответствующую логику, которая будет обрабатывать объект среза.

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

Вы можете использовать метод indices() объекта среза, чтобы получить индексы элементов для возврата из последовательности:

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]

Что нужно запомнить

Для создания кастомной последовательно нужно реализовать методы __len__ и __getitem__.
Метод __getitem__ должен возвращать элемент по заданному индексу или вызывать ошибку IndexError, если индекс выходит за границы последовательности.

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

1) Метод __getitem__

2) Метод __len__

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

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

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

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

Добавляем поддержку срезов

Что нужно запомнить

1) Метод getitem

2) Метод len