Как я могу сделать возобновляемым класс генерации чисел касательных? ⇐ Python

[Anonymous]

Я решил реализовать код для генерации чисел касательных в качестве добровольной задачи программирования. Мне это удалось, но не так эффективно, как хотелось бы.
Что такое касательные числа? Ну, это следующие серии:

Код: Выделить всё

1
2
16
272
7936
353792
22368256
1903757312
209865342976
29088885112832
4951498053124096
1015423886506852352
246921480190207983616
70251601603943959887872
23119184187809597841473536
8713962757125169296170811392
3729407703720529571097509625856
1798651693450888780071750349094912
970982810785059112379399707952152576
583203324917310043943191641625494290432

Это A000182 в OEIS.
Я реализовал бесконечный генератор касательных чисел, используя следующую формулу: a(n) = Sum_{k = 1..n-1} binomial(2 * n-2, 2 * k-1) * a(k) * a(n-k), с a(1) = 1, но я не буду вставлять ее сюда, так как она довольно длинная и не Суть вопроса в том, что она не так эффективна, как следующая функция, которую я опубликую ниже. Чтобы этот вопрос сосредоточился на одной конкретной теме, я не буду вставлять сюда код, но вы можете просмотреть его по этой ссылке.
Я реконструировал следующую функцию Питера Лушни, которую нашел на связанной странице OEIS, она занимает около 2/3 времени, которое требуется моей исходной функции генератора для того же ввода.
Функция выглядит следующим образом:

Код: Выделить всё

def A000182_list(n):
T = [0 for i in range(1, n+2)]
T[1] = 1
for k in range(2, n+1):
T[k] = (k-1)*T[k-1]
for k in range(2, n+1):
for j in range(k, n+1):
T[j] = (j-k)*T[j-1]+(j-k+2)*T[j]
return T[1:]

И я точно знаю, почему это работает, но я знаю, что это делает. Я буду объяснять код построчно, но понятия не имею, что за ним стоит, хотя я знаю все тождества и симметрии, которые использовал в своем генераторе.
Что делает эта строка: T = [0 for i in range(1, n+2)]? Ну, очевидно, что он инициализирует список длиной n-1, заполненный нулями. И это неэффективно.
Вторая строка: T[1] = 1, таким образом, элементу с индексом 1 присваивается значение 1. Мы видим, что индексация 0 никогда не используется и не доступна в коде. Поэтому нам нужен только список длины n.
Поэтому я реорганизовал его так: result = [1] * n. Повторение списка с помощью оператора * — наиболее эффективный способ получить список длины n в Python.
Что делает следующий цикл?

Код: Выделить всё

for k in range(2, n+1):
T[k] = (k-1)*T[k-1]

Ну, очевидно, что он циклически переходит от k=2 к k=n и присваивает T[K] какое-то число. Хорошо, но какой номер? Очевидно, что k-1 начинается с 1 и идет до 1, 2, 3, 4, 5, 6, 7, пока k идет до 2, 3, 4, 5, 6, 7, 8. Выражение k-1 используется дважды, и второе использование приводит к избыточным вычислениям. При k = 2 он вычисляет 1 * T[1] = 1 и присваивает это T[2]. При k = 3 он вычисляет 2 * T[2] = 2 и присваивает это T[3]. При k = 4 он вычисляет 3 * T[3] = 6 и присваивает это T[4]. При k = 5 он вычисляет 4 * T[4] = 24 и присваивает его T[5], а при k = 6 он вычисляет 5*24=120...
Другими словами, он просто вычисляет факториалы, каждый член является продуктом предыдущего термина и текущего положительного целого числа, которое увеличивается на 1 на каждой итерации. Поскольку термины используются сразу же на следующей итерации и ровно один раз после присвоения, T[k-1] требует избыточной индексации списка.
Я переработал код следующим образом:

Код: Выделить всё

result = [1] * n
last = 1
for i in range(1, n):
result[i] = last = last * i

Что же делает следующий вложенный цикл? Выглядит это довольно сложно:

Код: Выделить всё

for k in range(2, n+1):
for j in range(k, n+1):
T[j] = (j-k)*T[j-1]+(j-k+2)*T[j]

Но на самом деле вложенный цикл for довольно прост. Во-первых, очевидно, что k — это просто последовательные положительные целые числа, начиная с 2 и заканчивая n (2, 3, 4, 5, 6, 7, 8, 9...n). А что насчет Дж? Ну, j — это просто последовательные целые числа, начинающиеся с k, независимо от значения k в текущей итерации, а j заканчивается на n. Так, например, если n = 10, значения k, j на всех итерациях будут следующими:

Код: Выделить всё

In [31]: [list(range(i, 11)) for i in range(2, 11)]
Out[31]:
[[2, 3, 4, 5, 6, 7, 8, 9, 10],
[3, 4, 5, 6, 7, 8, 9, 10],
[4, 5, 6, 7, 8, 9, 10],
[5, 6, 7, 8, 9, 10],
[6, 7, 8, 9, 10],
[7, 8, 9, 10],
[8, 9, 10],
[9, 10],
[10]]

Что такое jk? Поскольку j начинается с k, j-k равно 0, на следующей итерации j увеличивается на 1, поэтому j-k равно 1, на следующей итерации j увеличивается на 1, поэтому j-k равно 2... Очевидно, j-k - это последовательные целые числа, начинающиеся с 0, это просто 0, 1, 2, 3, 4, 5, 6, 7, 8, 9... Следовательно, j-k+2 - это просто 2, 3, 4, 5, 6, 7, 8, 9, 10, 11...
И так же, как и в случае с факториалом, каждый член рассчитывается с использованием предыдущего термина путем индексации. И нам не нужно индексировать T[j - 1], если мы присваиваем его переменной.
Итак, это мой рефакторинг кода:

Код: Выделить всё

def A000182_fast(n):
result = [1] * n
last = 1
for i in range(1, n):
result[i] = last = last * i

for k in range(1, n):
b = 2
last = result[k - 1]
for a, c in enumerate(range(k, n)):
result[c] = last = a * last + b * result[c]
b += 1

return result

Производительность:

Код: Выделить всё

In [34]: A000182_fast(32)
Out[34]:
[1,
2,
16,
272,
7936,
353792,
22368256,
1903757312,
209865342976,
29088885112832,
4951498053124096,
1015423886506852352,
246921480190207983616,
70251601603943959887872,
23119184187809597841473536,
8713962757125169296170811392,
3729407703720529571097509625856,
1798651693450888780071750349094912,
970982810785059112379399707952152576,
583203324917310043943191641625494290432,
387635983772083031828014624002175135645696,
283727921907431909304183316295787837183229952,
227681379129930886488600284336316164603920777216,
199500252157859031027160499643195658166340757225472,
190169564657928428175235445073924928592047775873499136,
196535694915671808914892880726989984967498805398829268992,
219523439106761591280258358007964245987752702449505540243456,
264239411287900883270178745605712648488731058170551223831232512,
341838301335718580350174449297951396847081443826785448952307122176,
474090194351342155974522582010891145370303013658973457042263121068032,
703237958001393736999896827714634659411015090272684227831001161763127296,
1113255345330866700339746218047088280783690575394538814699382505942970007552]

In [35]: A000182_fast(32) == A000182_list(32)
Out[35]: True

In [36]: %timeit A000182_fast(256)
15.1 ms ± 109 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [37]: %timeit A000182_list(256)
15.6 ms ± 211 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Как видите, мой код строго быстрее оригинала, но ненамного.
Остановился ли я на этом? Конечно, нет. Хотя у меня есть работающий эффективный код, он не решает проблему, которую я намеревался решить.
Я хочу генерировать числа касательных по требованию, то есть я хочу, чтобы что-то вроде tangent_numbers(n) возвращало первые n чисел касательных, что я уже сделал, но я также хочу, чтобы код полностью избегал избыточных вычислений, я хочу, чтобы код запоминал уже сгенерированные числа касательных и сохранял их в переменной. Таким образом, если n меньше или равно количеству уже сгенерированных чисел касательных, код вообще не должен выполнять никаких фактических вычислений и вместо этого должен немедленно возвращать фрагмент этой глобальной переменной.
И затем, для числа, большего, чем длина уже сгенерированной последовательности, код должен заполнить глобальную последовательность чисел касательных с помощью [0] * (число - длина), а затем, начиная с длины индекса, он должен продолжить работу сразу после того, где он остановился, и он должен сгенерировать следующее термины, используя уже сгенерированные термины, и сохраняйте новые термины в глобальной переменной и возвращайте эту глобальную переменную после того, как это будет сделано.
Я выполнил функцию возобновления, используя мой бесконечный генератор и itertools.islice, однако, как я объяснил, это не так быстро, как конечная функция.
Я пытался обернуть код в класс, но это не работает:

Код: Выделить всё

OPS = []

class Tangent_numbers:
def __init__(self, n: int = 0):
if not isinstance(n, int) or n < 0:
raise ValueError("argument n must be a nonnegative integer")

self.series = [1]
self.factorial = 1
self.length = 1
if n > 1:
self.extend(n)

def extend(self, n: int) -> None:
if not isinstance(n, int) or n  0
b = start + 2
for a, c in enumerate(range(k + start, n), start=start):
series[c] = a * series[c - 1] + b * series[c]
OPS.append((k, a, b, c))
b += 1

self.length = (length, n)[length < n]

По сути, класс расширяет ряд до необходимой длины и предварительно заполняет факториалы, а затем возобновляет вычисление для уже встреченных k, которые являются первыми целыми числами длины - 1, начиная с 1, для этих чисел они начинаются не с k, а с k + start, start уменьшается на 1 на каждой итерации, изначально установленной на длину. Так, например, если длина равна 6, то k пар смещений со смещением больше 0 — это [(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)], тогда, начиная с индекса, равного длине, схема цикла и индексы идентичны базовому случаю (

Код: Выделить всё

A000182_fast

).
И это не работает:

Код: Выделить всё

In [39]: tan1 = Tangent_numbers()

In [40]: tan1.extend(32)

In [41]: tan1.series
Out[41]:
[1,
2,
16,
272,
7936,
353792,
22368256,
1903757312,
209865342976,
29088885112832,
4951498053124096,
1015423886506852352,
246921480190207983616,
70251601603943959887872,
23119184187809597841473536,
8713962757125169296170811392,
3729407703720529571097509625856,
1798651693450888780071750349094912,
970982810785059112379399707952152576,
583203324917310043943191641625494290432,
387635983772083031828014624002175135645696,
283727921907431909304183316295787837183229952,
227681379129930886488600284336316164603920777216,
199500252157859031027160499643195658166340757225472,
190169564657928428175235445073924928592047775873499136,
196535694915671808914892880726989984967498805398829268992,
219523439106761591280258358007964245987752702449505540243456,
264239411287900883270178745605712648488731058170551223831232512,
341838301335718580350174449297951396847081443826785448952307122176,
474090194351342155974522582010891145370303013658973457042263121068032,
703237958001393736999896827714634659411015090272684227831001161763127296,
1113255345330866700339746218047088280783690575394538814699382505942970007552]

In [42]: good_ops = OPS.copy()

In [43]: OPS.clear()

In [44]: tan2 = Tangent_numbers()

In [45]: tan2.extend(16)

In [46]: tan2.extend(32)

In [47]: bad_ops = OPS.copy()

In [48]: OPS.clear()

In [49]: tan2.series
Out[49]:
[1,
2,
16,
272,
7936,
353792,
22368256,
1903757312,
209865342976,
29088885112832,
4951498053124096,
1015423886506852352,
246921480190207983616,
70251601603943959887872,
23119184187809597841473536,
8713962757125169296170811392,
2904913076573872266203498954016294449446912,
4691853834639623592590771373697685743890071552,
5130358638144401639057729513343066448970081370112,
4915808771679000034913126880856135752591161113444352,
4532390344824939077129321365233314869866731663798566912,
4203608535388999900804817047351188778825742479186567626752,
4016075105391784162392416168597886026774711180596874221453312,
4006317907309964706114200066419926732731565593907176950571466752,
4206222056177413192157298446480182062802619739270396407035369357312,
4669250237392028942296888593639384792643032067338268907267585686372352,
5494543666053818716762261654491210913657871572416499541257406325993766912,
6862845392986161471745129519783028922048665371026568262534783173188021911552,
9102416468449937394166752814219701116933808763260683657119736372726144394330112,
12818533459855341263183886505243846034060346753317615985094136744918816751827812352,
19157416044307854900780627577605126931202540354102138452037843767399405302510530854912,
30362182612272673641771108733390016965056260526780787823865261029201116235800577941962752]

In [50]: set(good_ops) ^ set(bad_ops)
Out[50]: set()

In [51]: from collections import Counter

In [52]: Counter(good_ops) - Counter(bad_ops)
Out[52]: Counter()

In [53]: Counter(bad_ops) - Counter(good_ops)
Out[53]: Counter()

Первые 32 числа касательных за один проход генерируются правильно, как и ожидалось, но первые 32 числа касательных за два прохода генерируются неправильно, функция возобновления не работает. Но, как вы можете ясно видеть, в обоих случаях структура цикла и комбинации индексов одинаковы, но результаты разные.
Я понятия не имею, почему это так, математика мне не под силу, мне не удалось перепроектировать использованную математику. Я не могу исправить ошибку.
Как правильно реализовать возобновление?

Подробнее здесь: https://stackoverflow.com/questions/799 ... -resumable