Что если для ответа на вопрос вам нужно обработать последовательность значений, которую вы не можете хранить в памяти как список?
Например, когда вы читаете огромный файл. Или когда вы вычисляете следующее значение на основании предыдущих значений и какой-то информации, появляющейся в процессе вычисления. Или случайные последовательности. Или бесконечные последовательности, когда вы не знаете, как далеко нужно зайти, чтобы найти ответ.
В этой статье мы посмотрим два решения:
- Простая функция.
- Функция с колбеком (функцией обратного вызова).
Затем можете посмотреть решение с помощью итераторов и другое решение с помощью генераторов.
Чтобы избежать объяснения сложного алгоритма, мы будем использовать хорошо известную последовательность Фибоначчи, а нашим вопрос, на который нужно будет ответить, будет "Какое первое число последовательности делится на 17."
Гораздо более сложный случай типа такого, это если вам нужно обойти цепочки ДНК в базе данных, постоянно улучшая свой запрос для выбора следующей цепочки, пока не будет найдено то, что удовлетворяет вашим требованиям.
В случае последовательности Фибоначчи мы можем заранее посчитать несколько элементов, но в общем случае это не поможет.
Даже в случае последовательности Фибоначчи ни одна заранее посчитанная последовательность не сможет дать ответ на любой произвольный вопрос, и в случае ДНК-цепочек совершенно понятно, что у нас даже не хватит памяти для размещения заранее подготовленного списка.
Простая функция Fibonacci
Давайте посмотрим простую реализацию последовательности Фибоначчи, а затем подправим решение.
examples/python/fibonacci_function.py
#!/usr/bin/env python
from __future__ import print_function
def fibonacci():
values = []
while(True):
if len(values) < 2:
values.append(1)
else:
values = [values[-1], values[-1] + values[-2]]
if __name__ == '__main__':
fibonacci()
Нет ничего необычного в этой реализации, но я не советую запускать этот код, так как он ничего не выводит и не останавливается. Так что если вы его запустите, то будет выглядеть, как будто он завис.
Вы можете добавить:
print(values[-1])
в цикл, чтобы видеть происходящее, а также можете добавить что-то вроде этого:
if (values[-1] > 100):
break;
для ограничения последовательности.
Наш "вопрос" - деление на 17
Напомню, что наша задача - "изучение последовательности Фибоначчи", и первый вопрос, на который нужно ответить, это "Какой первый элемент последовательности Фибоначчи делится на 17?"
Так что мы улучшим функцию, чтобы она возвращала первый элемент, который может делится на 17:
examples/python/fibonacci_function_mod_17.py
#!/usr/bin/env python
from __future__ import print_function
def fibonacci():
values = []
while(True):
if len(values) < 2:
values.append(1)
else:
values = [values[-1], values[-1] + values[-2]]
if values[-1] % 17 == 0:
return(values[-1])
if __name__ == '__main__':
res = fibonacci()
print(res)
Мы просто добавили следующий код, который проверяет, может ли текущее значение последовательности делится без остатка на 17:
if values[-1] % 17 == 0:
return(values[-1])
```оо
Мы также изменили код, чтобы он возвращал число Фибоначчи, которое удовлетворяет нашему требованию.
Теперь значительно лучше, чем программа, просто выводящая результат.
Запущенная программа остановится на 34.
Позже у нас может возникнуть другой вопрос. Что если на него вообще не будет ответа?
В этом случае, нам лучше применить меры безопасности для остановки работы.
## Меры безопасности - ограничение цикла
С помощью добавления ограничения типа этого, мы можем быть уверены,
что код в конечном итоге остановится, даже если мы не получим ответа на свой вопрос.
```python
if values[-1] > 10000:
return
Конечно, мы можем использовать значительно большее число для этого, или можем основываться на количестве элементов для проверки.
Вот полный код:
examples/python/fibonacci_function_with_safety.py
from __future__ import print_function
def fibonacci():
values = []
while(True):
if len(values) < 2:
values.append(1)
else:
values = [values[-1], values[-1] + values[-2]]
if values[-1] % 17 == 0:
return(values[-1])
if values[-1] > 10000:
return
if __name__ == '__main__':
res = fibonacci()
if (res != None):
print(res)
В чем проблема?
У нас есть функция, которая проверяет какое-то особое условие и возвращает первое значение, подходящее под условие. Если завтра мне нужно будет ответить на вопрос "Какое первое число Фибоначчи делится на 19?", или "Какое первое число Фибоначчи, которое является квадратом другого числа?", я могу просто скопировать код и изменить условие.
Звучит просто, но это значит, что у нас будет множество копий кода, реализующего функцию fibonacci. Что если алгоритм будет намного сложнее? Мы все еще хотим копировать тот код снова и снова?
Что если мы найдем ошибку в нашем алгоритме (или просто способ реализации лучше) после 20 копирований для ответов на разные вопросы?
Это явно не очень хороший путь.
Давайте попробуем другой подход. Изменим функцию Fibonacci так, чтобы она принимала функцию как параметр и вызывала эту функцию для каждого элемента последовательности Фибоначчи.
Функция обратного вызова (колбек)
Функция fibonacci теперь выглядит вот так:
она принимает параметр cb, который должен быть функцией,
как только мы вычислили новый элемент последовательности,
вызываем эту колбек-функцию, передавая ей последний элемент: cb(values[-1]).
Ожидается, что возвращаемый элемент будет списком или кортежем (tuple), в котором
первый элемент будет иметь значение True или False и показывать,
нашли мы ответ на вопрос (True) или еще нет (False).
Если значение будет True, мы возвращает второй элемент в качестве результата.
def fibonacci(cb):
values = []
while(True):
if len(values) < 2:
values.append(1)
else:
values = [values[-1], values[-1] + values[-2]]
r = cb(values[-1])
if (r[0]):
return(r[1])
Таким образом, колбек должен принимать одиночное значение и возвращать кортеж (tuple), в котором первый элемент будет True/False, а второй - нужное нам значение последовательности.
Функция обратного вызова выглядит вот так:
Она принимает значение v - текущее значение последовательности.
И возвращает True и найденное значение, если оно может делится на 17.
Она возвращает True и None, если достигнут предел, который мы установили.
Значение True будет указывать функции fibonacci, что поиск завершен,
а None - что ответа не найдено.
Наконец, мы возвращаем кортеж с одним значением False, указывающим функции
fibonacci, что искомое значение еще не нашлось и нужно проверить следующее.
def check_17(v):
if v % 17 == 0:
return (True, v)
if v > 10000:
return (True, None)
return (False,)
Полная реализация выглядит вот так:
examples/python/fibonacci_function_callback.py
#!/usr/bin/env python
from __future__ import print_function
def fibonacci(cb):
values = []
while(True):
if len(values) < 2:
values.append(1)
else:
values = [values[-1], values[-1] + values[-2]]
r = cb(values[-1])
if (r[0]):
return(r[1])
def check_17(v):
if v % 17 == 0:
return (True, v)
if v > 10000:
return (True, None)
return (False,)
if __name__ == '__main__':
res = fibonacci(check_17)
if (res != None):
print(res)
Решение значительно лучше предыдущего. Теперь нам не нужно менять функцию fibonacci, в зависимости от условий. Мы можем переместить функцию fibonacci в модуль, импортировать ее и использовать как внешний ресурс. Если нужно будет ее поправить, то это нужно будет делать в одном месте, и все потребители этой функции будут в выигрыше.
Даже еще лучше, функция, которую мы создали как колбек, может быть переиспользована для передачи в другие функции-генераторы последовательностей.
Итераторы и генераторы
Есть два других решения этой проблемы. Одно это создание итератора, а второе - создание генератора.
