def fib(x):
if x>1:
ar=fib(x-1)
ar.append(ar[len(ar)-1]+ar[len(ar)-2])
return ar
else:
ar=[]
ar.append(1)
ar.append(1)
return ar
print(fib(10))
Что плохого в этом коде?
Ну... вроде никто не сказал, что этот код можно переписать более функционально.
Основной недостаток в том, что если мы хотим просто распечатать миллион чисел Фиббоначи, то нам будет сформировать в памяти список из миллиона элементов, и только потом распечатать. Хотя выделения миллиона элементов в памяти можно избежать.
Для этого есть генераторы. Мы можем просто написать
def fibb():
a, b = 1, 1
while True:
yield a
a, b = b, a+b
в результате fibb() будет возвращать генератор чисел Фиббоначи. Его преимущества в том, что он будет возвращать элементы по мере необходимости, а не вычислять всё сразу (ленивые вычисления). В результате мы получаем очень простой код, в котором нет ни списков, ни append, только правило получения очередного числа Фиббоначчи.
Например, распечатать первые 10 чисел можно так:
it = iter(fibb())
for _ in range(10):
print(next(it))
Тут мы получаем итератор на последовательность, и последовательно читаем первые 10 значений. Мы так можем прочитать хоть миллион — в памяти они не будут выделены, а будут возвращаться по требованию. Итератор он как-бы контекст функции. Каждый раз после
yield мы возвращаем текущий элемент, и сохраняем все локальные переменные функции. Каждый раз, когда нам нужен следующий элемент, мы востанавливаем локальные переменные функции и выполняем следующую инструкцию после
yeildМы можем работать со значением, которое возвращает fibb() как со списком. Например, вот ещё один способ распечатать 10 элементов:
fibb_list = fibb()
for index, value in enumerate(fibb_list, 1):
print(value)
if index >= 10:
break
Можно думать, что fibb_list это бесконечный список чисел Фиббоначи, а метод enumerate возвращает бесконечный список пар, где первое число — номер числа Фиббоначчи, второе — само число Фиббоначчи. Мы перебираем бесконечный список, и как только номер превышает десять, мы выходим из цикла печати.
Можно поиграться с enumerate, например, запустив следующий код
>>> print(list(enumerate([3,4,5],0)))
[(0, 3), (1, 4), (2, 5)]
>>> print(list(enumerate([3,4,5],1)))
[(1, 3), (2, 4), (3, 5)]
>>> print(list(enumerate([3,4,5],3)))
[(3, 3), (4, 4), (5, 5)]
>>> print(list(enumerate([3,4,5])))
[(0, 3), (1, 4), (2, 5)]
>>> print(enumerate([3,4,5]))
<enumerate object at 0x7f126df63948>
Тут видно, что метод принимает в качестве первого элемента массив, второго — начальный индекс (по умолчанию нуль) и возвращает массив пар. Тут же видна «ленивость» вычисление, если мы не будет преобразовывать результат явно в список, то ответом будет
enumerate object at 0x7f126df63948, что следует понимать примерно так, что по указанному адресу располагается объект, от которого можно получать одним за другим элементы данной последовательности.
Ну... получить первые 10 элементов генератора стандартными средствами средствами несколько извратно, но есть метод islice из itertools, который позволит это сделать
import itertools
print(list(itertools.islice(fibb(), 10)))
# Или так, печатаем элементы в столбик
list(map(lambda x: print(x), itertools.islice(fibb(), 10)))
# Или 10 элементов начиная с 1000-го, при этом никакого списка из 1000 элементов в памяти не будет (!) выделено.
print(list(itertools.islice(fibb(), 1000, 1010)))
но хотелось бы узнать соотношение затрат по сравнению с питоновским же массивом.)