Генератор натурального ряда
Учебная задача на знание языка и не только:
g = (...)
for n in g:
print(n)
if n > 20:
break
На первой строке выражение-генератор. Генератор должен бесконечно производить натуральные числа: 1, 2, 3, …. Три задачки в порядке увеличения сложности:
- Написать выражение-генератор с использованием стандартной библиотеки. Можно импортировать стандартные модули.
- То же, без импортов.
- То же, без импортов и глобальных функций и объектов.
P.S. Подразумеваю, что в третьем пункте нет импортов, не вызываются встроенные функции, нет обращений ко встроенным объектам, не определяются именованные функции или объекты.
Ответы (8 шт):
2 вариант задачи:
g = (i for i, _ in enumerate(iter(int, 1), 1))
Через (iter(int, 1))
получаем вечный итератор, который возвращает нули.
А с enumerate()
получаем возрастающие натуральные числа, но без необходимости создавать переменную для счетчика итераций.
Не забываем указать параметр start = 1
, чтобы начать enumerate()
с 1, а не 0.
P.S.: бесконечно 0 можно получать и иначе:
g = (i for i, _ in enumerate(iter(lambda: 0, 1), 1))
Можно сделать простой, но условно-бесконечный цикл. Вряд ли кто-то возьмётся его перебирать до конца:
g = range(1, 10**1_000_000)
Формулировка п. 3, лично мне, немного не понятна, ну вот вариант без рабочих глобальных функций и объектов.
def test():
def numbersN():
n = 1
while True:
yield n
yield n + 1
yield n + 2
yield n + 3
yield n + 4
yield n + 5
yield n + 6
yield n + 7
yield n + 8
yield n + 9
n += 10
def test(g, n):
for i in g:
if i > n:
break
return i
print(test(numbersN(), 10))
nn = 1000_000
%timeit test(numbersN(), nn)
test()
Конечно, проигрывает range(1, 10**18)
процентов ≈50%, зато длинный и формально честный. Или нет? Кто знает?
Вариант решения через type()
:
g = type(
"NaturalNumbers",
(),
{
'__iter__': lambda x: x,
'__next__': lambda x: setattr(x, 'counter', x.counter + 1) or x.counter,
'counter': 0
}
)()
Вышеуказанный код "сворачивается" и в одну строку:
g = type("NaturalNumbers", (), {'__iter__': lambda x: x, '__next__': lambda x: setattr(x, 'counter', x.counter + 1) or x.counter, 'counter': 0})()
Функция type()
позволяет не только проверять тип объекта, но и создавать новые типы. Для этого передаем:
- название создаваемого типа;
- кортеж с родительскими классами (в нашем случае ничего);
- словарь с именами, которые передадутся в
__dict__
- для нас это значит, что можно задать магические методы__iter__
и__next__
, а также создать переменную counter.
В iter
просто определяем, чтобы возвращался объект итератора, а в counter
задаем и храним переменную для счетчика натуральных чисел.
Вся магия в next
:
- при каждой итерации будет вызываться lambda-функция, которая выполняет
or
; - сначала значение counter прибавит 1 через
setattr
- с её помощью обходим проблемы с использованием присваивания через=
; - из
setattr
возвращается None и функция переходит ко второй частиor
- просто возврату текущего значения counter.
Не забываем в конце добавить ()
для получения экземпляра свежеопределенного типа.
Можно использовать как указано, так и передать для создания выражения-генератора:
g = (i for i in type("NaturalNumbers"...)())
1.
Первый вариант, с импортами, самый простой. Наружные скобки в определении g
не нужны, оставлены только для формального соответствия условию. itertools.count
умеет считать натуральные числа без остановки:
import itertools
g = (itertools.count(1))
2.
Второй вариант я утащу из ответа mrgervant. Поставьте ему плюсик.
g = (i for i, _ in enumerate(iter(int, 1), start=1))
iter
создаёт бесконечный генератор из нулей, enumerate
превращает его в последовательность натуральных чисел.
И это, кажется, единственный вариант решить задачу. Но неугомонный mrgervant предложил решение на основе type
, который позволяет собрать объект-итератор.
3.
Лямбда в Питоне позволяет использовать выражения (yield ...)
, (yield from ...)
. При этом лямбда из обычной функции превращается в генератор. Выражение для g
совмещает Y-комбинатор с рекурсивной лямбдой-генератором:
g = (lambda f, n: f(f, n))(lambda f, n: ((yield n), (yield from f(f, n + 1))), 1)
Читать это невозможно. Разберём на составляющие:
y = lambda f, n: f(f, n)
f = lambda f, n: ((yield n), (yield from f(f, n + 1)))
g = y(f, 1)
Если убрать комбинатор, получится:
f = lambda n: ((yield n), (yield from f(n + 1)))
g = f(1)
Но в этом варианте нужен глобальный символ f
, чтобы сделать рекурсивный вызов. А в выражении с комбинатором он не нужен.
3.1.
Предыдущий вариант решает задачу, но глубина рекурсии ограничивает длину "бесконечного" генератора примерно тысячью элементов. Это просто смешно! Заменим линейную рекурсию на древовидную. Добавится ещё один комбинатор.
Этим кодом можно испугать любого, зато для глубины стека в одну тысячу вызовов он способен произвести 2499 - 1 натуральных чисел.
g = (lambda f, n, d: f(f, n, d))(
lambda f, n, d: ((
yield from (lambda h, n, d: h(h, n, d))(
lambda h, n, d: (yield n) if d == 0 else ((yield from h(h, n, d - 1)), (yield from h(h, n + 2 ** (d - 1), d - 1))),
n,
d
)
), (
yield from f(f, n + 2 ** d, d + 1)
)),
1,
0
)
P.S. Последние два варианта не используют никаких встроенных или глобальных символов, только ключевые слова lambda
, yield
, from
, if
, else
. Вопрос со звёздочкой: можно ли решить задачу без from
, if
, else
?
P.P.S. Когда я задавал вопрос, я думал что у последнего пункта нет решения. И даже придумал доказательство этого факта. Но я вам его не покажу. :)
Получилась следующая махина:
a=(lambda:0).__class__((lambda:0).__code__.__class__(0, 0, 0, 1, 2, 35, b'K\x00\x01\x00\x97\x00d\x01}\x00\t\x00|\x00\x96\x01\x97\x01\x01\x00|\x00d\x01z\r\x00\x00}\x00\x8c\n\xad\x03w\x01', (1, 1), (), ('i',), '', '', '', 140, b'\xe8\x00\xf8\x80\x00\xd8\x08\t\x80A\xd8\n\x0e\xd8\x0e\x0f\x8a\x07\xd8\x08\t\x88Q\x89\x06\x88\x01\xf0\x05\x00\x0b\x0f\xf9', b'\x82\x0e\x10\x01', (), ()),{},"")()
for i in a:
print(i)
Запускал на Python 3.12.5, на других не факт, что будет работать.
Фактически, это нечто вида:
def f():
i = 1
while True:
yield i
i += 1
code = type(function.__code__)(*Данные функции f*)
a = function(code)()
from itertools import count
g = count(1)
g = (x + 1 for x in range(10**100))
g = (lambda f: f(f))(lambda f: (n := [0]) and iter(lambda: (n.__setitem__(0, n[0]+1), n[0])[1], None))
for n in g:
print(n)
if n > 20: break
3.1)
g = (lambda f: f(f))(lambda f: (n := [0]) and (lambda: (n.__setitem__(0, n[0]+1), n[0])[1]))
i = 0
while True:
i += 1
print(g())
if i >= 21: break
Последние два варианта не используют никаких встроенных или глобальных символов, только ключевые слова lambda, yield, from, if, else. Вопрос со звёздочкой: можно ли решить задачу без from, if, else?
Строго говоря, достаточно одного ключевого слова - lambda
. Оно достаточно мощное, что бы многие предложенные варианты свести только к нему одному (хотя для некоторых, нужны for
и in
).
def test_StanislavVolodarskiy_1():
return (lambda:0).__globals__['__builtins__'].__import__(
'itertools').count(1)
def test_mrgervant_1():
return (i for i, _ in
(lambda:0).__globals__['__builtins__'].enumerate(
(lambda:0).__globals__['__builtins__'].iter(
int, 1), 1))
mrgervant_2 = (lambda:0).__globals__['__builtins__'].type(
"NaturalNumbers",
(),
{
'__iter__': lambda x: x,
'__next__': lambda x: (x.__setattr__('counter', x.counter + 1)
or x.counter),
'counter': 0
}
)
def test_CrazyElf():
return (lambda:0).__globals__['__builtins__'].range(1, 2**63 - 1)
def test_FoxFox_3():
return (lambda f: f(f))(
lambda f: (n := [0]) and
(lambda:0).__globals__['__builtins__'].iter(
lambda: (n.__setitem__(0, n[0]+1), n[0])[1],
None
)
)
def test_gen(g, n):
j = 1
for i in g:
assert i == j, f"{i, j=}"
if i > n:
return True
j += 1
assert False
for nn in [1, 100, 10_000]:
assert test_gen(test_StanislavVolodarskiy_1(), nn)
assert test_gen(test_mrgervant_1(), nn)
assert test_gen(mrgervant_2(), nn)
assert test_gen(test_CrazyElf(), nn)
assert test_gen(test_FoxFox_3(), nn)
print(f"{nn} - Хорь")
def test_bench(g, n):
for i in g:
if i > n:
return True
assert False
nn = 1_000_000
%timeit test_bench(test_StanislavVolodarskiy_1(), nn)
%timeit test_bench(test_mrgervant_1(), nn)
%timeit test_bench(mrgervant_2(), nn)
%timeit test_bench(test_CrazyElf(), nn)
%timeit test_bench(test_FoxFox_3(), nn)
print("Хорь")
1 - Хорь
100 - Хорь
10000 - Хорь
29.6 ms ± 936 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
65.2 ms ± 2.26 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
222 ms ± 13.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
29.2 ms ± 225 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
202 ms ± 8.03 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Хорь