Создайте список, накапливающий результаты многократного вызова функции для входного значения
Есть ли библиотечная функция, которая создает рекурсивные списки в следующем смысле:
recursive_list(f, x0, n) = [x0, f(x0), f(f(x0)), f(f(f(x0))), ...]
с элементами n в возвращаемом списке?
Если нет, то как это можно написать?
Ответы 4
В стандартной библиотеке такой функции нет, но для ее написания не потребуется много кода:
def recursive_list(f, x, n):
return [x] + [x := f(x) for i in range(n-1)]
@EvanAad, потому что = будет синтаксической ошибкой, которая является частью оператора присваивания, вам нужно выражение присваивания, которое использует :=
Этот код выполняет ненужное добавление списка (с использованием ненужной копии списка O(n)).
@pts, это правда, но, по моему опыту профессионального написания Python, это почти никогда не является серьезной проблемой, копирование одного буфера в другой — одна из самых быстрых вещей, которые вы можете сделать, а с точки зрения памяти это редко является проблемой.
Вы можете использовать itertools.accumulate, который работает как сокращение, но дает вам все промежуточные значения.
def repeated_application(f_unary, x0, n):
def f_binary(acc, _):
return f_unary(acc)
return itertools.accumulate(range(n), f_binary, initial=x0)
Вам просто нужно превратить унарную функцию в бинарную.
Обратите внимание: это возвращает итератор (более общий).
Кроме того, способ работы n недостаточно определен, вы можете поэкспериментировать с ним в соответствии со своими требованиями.
Я также хочу отметить, что простой способ использования основных языковых конструкций вполне приемлем;
def recursive_application(f, x0, n):
acc = x0
result = [acc]
for _ in range(n):
acc = f(acc)
result.append(acc)
return result
Или как генератор, он очень чистый:
def repeated_application(f, x0, n):
acc = x0
yield acc
for _ in range(n):
acc = f(acc)
yield acc
Как предложено здесь используйте повторите и уменьшите:
from itertools import repeat
from functools import reduce
def repeated(func, n):
def apply(x, f):
return f(x)
def ret(x):
return reduce(apply, repeat(func, n), x)
return ret
recursive_list = [repeated(f, i) for i in range(5)]
Элементы рекурсивного списка являются функциями.
Например:
def f(x):
return x*x
recursive_list[3](2)
# 256
ооо, это повторяется fi количество раз от i=0 -> n, что масштабируется квадратично, но вам нужно применить только fn раз (линейно) (я не понижал голос, кстати)
@juanpa.arrivillaga Конечно, f вызывается только «по требованию», а не при составлении списка. Это делает создание списка довольно бессмысленным, хотя repeated можно просто использовать напрямую.
@mkrieger1 да, список бессмысленен, но вопрос требовал список
Да, список значений, а не список функций.
@mkrieger1 правильно, спасибо за указание, я проследил за тем, чтобы список содержал значения, а не функции
Не входит в стандартную библиотеку Python, но в more-itertools (рекомендованном документацией Python itertools ) есть iterate и take:
from more_itertools import iterate, take
f, x0, n = lambda x: 2*x, 1, 10
print(take(n, iterate(f, x0)))
Выход:
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
Хороший. Почему
:=? Не=подойдет?