Как я могу сделать возобновляемым класс генерации чисел касательных? ⇐ 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 числа касательных за два прохода генерируются неправильно, функция возобновления не работает. Но, как вы можете ясно видеть, в обоих случаях структура цикла и комбинации индексов одинаковы, но результаты разные.
Я понятия не имею, почему это так, математика мне не под силу, мне не удалось перепроектировать использованную математику. Я не могу исправить ошибку.
Как правильно реализовать возобновление?

Обновить
Я вижу, что люди не нажимали на предоставленную ссылку. Сначала я реализовал формулу a(n) = Sum_{k = 1..n-1} binomial(2 * n-2, 2 * k-1) * a(k) * a(n-k), с a(1) = 1, используя бесконечный генератор. Он предоставлен по ссылке выше. Но он менее эффективен, чем версия списка (

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

A000180_fast

).
Мой метод прост.

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

                                       1

1    1

1    2    1

1    3    3    1

1    4    6    4    1

1    5    10   10   5    1

1    6    15   20   15   6    1

1    7    21   35   35   21   7    1

1    8    28   56   70   56   28   8    1

1    9    36   84  126  126   84   36   9    1

1    10   45  120  210  252  210  120   45   10   1

1    11   55  165  330  462  462  330  165   55   11   1

1    12   66  220  495  792  924  792  495  220   66   12   1

1    13   78  286  715  1287 1716 1716 1287 715  286   78   13   1

1    14   91  364  1001 2002 3003 3432 3003 2002 1001 364   91   14   1

1    15  105  455  1365 3003 5005 6435 6435 5005 3003 1365 455  105   15   1

Выше представлен треугольник Паскаля. Он показывает значения гребенки (n,k), строки — n, а столбцы — k. Поскольку верхняя строка имеет значение Comb(0, 0) = 1, индексация начинается с нуля.
Из треугольника хорошо видны закономерности, а именно:

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

comb(n, 0) = comb(n, n) = 1
comb(n, 1) = comb(n, n-1) = n
comb(n, k) = comb(n, n-k) = comb(n-1, k-1) + comb(n-1, k)

Я не буду объяснять, что означают формулы, поскольку смысл формул полностью задается треугольником Паскаля.
Треугольник Паскаля генерируется с помощью следующего кода:

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

class Pascal_Triangle:
def __init__(self, end_row: int = 3):
self.data = [[1], [1, 1], [1, 2, 1]]
self.length = 3
if end_row > 3:
self.add_rows(end_row)

def add_rows(self, end_row: int):
last_row = self.data[-1]
for n in range(self.length, end_row):
row = [1, n] + [0] * (n - 3) + [n, 1]
half = n >> 1
even = not n & 1
for i, j, k in zip(
range(1, half), range(2, half + 1), range(n - 2, half - even, -1)
):
row[j] = row[k] = last_row[i] + last_row[j]

self.data.append(last_row := row)

self.length = end_row

def pretty_print(self):
longest = len(str(self.data[-1][self.length // 2]))
line_length = (longest + 1) * (self.length - 1) + longest
for row in self.data:
print(" ".join(f"{n:^{longest}}" for n in row).center(line_length))
print()

Я получил следующий ряд из треугольника Паскаля, он кодирует нужные нам числа из треугольника Паскаля для касательных чисел:

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

[[4, 6],
[5, 10],
[6, 15, 20],
[7, 21, 35],
[8, 28, 56, 70],
[9, 36, 84, 126],
[10, 45, 120, 210, 252],
[11, 55, 165, 330, 462],
[12, 66, 220, 495, 792, 924],
[13, 78, 286, 715, 1287, 1716],
[14, 91, 364, 1001, 2002, 3003, 3432],
[15, 105, 455, 1365, 3003, 5005, 6435],
[16, 120, 560, 1820, 4368, 8008, 11440, 12870],
[17, 136, 680, 2380, 6188, 12376, 19448, 24310],
[18, 153, 816, 3060, 8568, 18564, 31824, 43758, 48620],
[19, 171, 969, 3876, 11628, 27132, 50388, 75582, 92378]]

Он генерируется с использованием следующего кода:

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

def func(n):
row = [4, 6]
level = 5
length = 2
result = []
for _ in range(n + 1>>1):
result.append(row)
new = [level] * length
next(it := iter(row))
for j, (a, b) in enumerate(zip(row, it), start=1):
new[j] = a + b

result.append(row := new)
length += 1
level += 1
new = [level] * length
next(it := iter(row))
for j, (a, b) in enumerate(zip(row, it), start=1):
new[j] = a + b

new[-1] = b + b
row = new
level += 1

return result

Что, черт возьми, на самом деле означает a(n) = Sum_{k = 1..n-1} бином (2 * n-2, 2 * k-1) * a(k) * a(n-k)?
Ну, a(1) = 1, a(2) = 2. Хорошо. Что дальше? Начиная с a(3), мы используем формулу суммирования. n=3, таким образом, 2 * n - 2 равно 4, для n=4, 2 * n - 2=6, для n=5, 2 * n - 2=8, для n=6, 2 * n - 2=10, числа просто идут 4, 6, 8, 10, 12, другими словами, это четные числа. 2 * k - 1, очевидно, нечетное число, k изначально равно 1, поэтому сначала 2 * k - 1 = 1. Фактически используются все нечетные числа ниже n, а именно range(1, n, 2).
Теперь, что означает a(k) * a(n - k)?
Ну, формула говорит об этом:

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

A(3) = comb(4, 1) * A(1) * A(2) + comb(4, 3) * A(2) * A(1)
A(4) = comb(6, 1) * A(1) * A(3) + comb(6, 3) * A(2) * A(2) + comb(6, 5) * A(3) * A(1)
A(5) = comb(8, 1) * A(1) * A(4) + comb(8, 3) * A(2) * A(3) + comb(8, 5) * A(3) * A(2) + comb(8, 7) * A(4) * A(1)
A(6) = comb(10, 1) * A(1) * A(5) + comb(10, 3) * A(2) * A(4) + comb(10, 5) * A(3) * A(3) + comb(10, 7) * A(4) * A(2) + comb(10, 9) * A(5) * A(1)
A(7) = comb(12, 1) * A(1) * A(6) + comb(12, 3) * A(2) * A(5) + comb(12, 5) * A(3) * A(4) + comb(12, 7) * A(4) * A(3) + comb(12, 9) * A(5) * A(2) + comb(12, 11) * A(6) * A(1)

Строки генерируются с помощью простого кода:

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

def func1(n):
level = 4
for i in range(3, n + 3):
print(
f"A({i}) = "
+ " + ".join(
f"comb({level}, {j}) * A({k}) * A({i-k})"
for j, k in zip(range(1, level, 2), range(1, i))
)
)
level += 2

Я не выбрал большее число, потому что это нарушит форматирование строк, строки станут длиннее.
Как вы можете видеть, здесь много симметрий, симметрий, которые можно использовать.
Вместо этого мы можем использовать это:

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

A(3)=comb(4,1)*A(1)*A(2)*2
A(4)=comb(6,1)*A(1)*A(3)*2+comb(6,3)*A(2)**2
A(5)=comb(8,1)*A(1)*A(4)*2+comb(8,3)*A(2)*A(3)*2
A(6)=comb(10,1)*A(1)*A(5)*2+comb(10,3)*A(2)*A(4)*2+comb(10,5)*A(3)**2
A(7)=comb(12,1)*A(1)*A(6)*2+comb(12,3)*A(2)*A(5)*2+comb(12,5)*A(3)*A(4)*2
A(8)=comb(14,1)*A(1)*A(7)*2+comb(14,3)*A(2)*A(6)*2+comb(14,5)*A(3)*A(5)*2+comb(14,7)*A(4)**2
A(9)=comb(16,1)*A(1)*A(8)*2+comb(16,3)*A(2)*A(7)*2+comb(16,5)*A(3)*A(6)*2+comb(16,7)*A(4)*A(5)*2
A(10)=comb(18,1)*A(1)*A(9)*2+comb(18,3)*A(2)*A(8)*2+comb(18,5)*A(3)*A(7)*2+comb(18,7)*A(4)*A(6)*2+comb(18,9)*A(5)**2
A(11)=comb(20,1)*A(1)*A(10)*2+comb(20,3)*A(2)*A(9)*2+comb(20,5)*A(3)*A(8)*2+comb(20,7)*A(4)*A(7)*2+comb(20,9)*A(5)*A(6)*2
A(12)=comb(22,1)*A(1)*A(11)*2+comb(22,3)*A(2)*A(10)*2+comb(22,5)*A(3)*A(9)*2+comb(22,7)*A(4)*A(8)*2+comb(22,9)*A(5)*A(7)*2+comb(22,11)*A(6)**2
A(13)=comb(24,1)*A(1)*A(12)*2+comb(24,3)*A(2)*A(11)*2+comb(24,5)*A(3)*A(10)*2+comb(24,7)*A(4)*A(9)*2+comb(24,9)*A(5)*A(8)*2+comb(24,11)*A(6)*A(7)*2
A(14)=comb(26,1)*A(1)*A(13)*2+comb(26,3)*A(2)*A(12)*2+comb(26,5)*A(3)*A(11)*2+comb(26,7)*A(4)*A(10)*2+comb(26,9)*A(5)*A(9)*2+comb(26,11)*A(6)*A(8)*2+comb(26,13)*A(7)**2

Строка печатается следующим образом:

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

def func2(n):
level = 4
end = 3
middle = 2
for i in range(3, n + (n&1) + 3, 2):
print(
f"A({i})="
+ "+".join(
f"comb({level},{j})*A({k})*A({i-k})*2"
for j, k in zip(range(1, end, 2), range(1, i))
)
)
i+=1
level += 2
print(
f"A({i})="
+ "+".join(
f"comb({level},{j})*A({k})*A({i-k})*2"
for j, k in zip(range(1, end, 2), range(1, i))
) + f"+comb({level},{level>>1})*A({middle})**2"
)
level += 2
middle += 1
end += 2

А вот мой генератор, я объяснил весь код:

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

from itertools import batched, islice

def tangent_numbers_gen():
yield 1
yield (length := 2)
series = [1, 2]
level = 5
end = 0
odd = 1
even = 2
row = [4, 6]
while True:
new = [level] * length
it_row = iter(row)
it_series = iter(series)
it_seires = reversed(series)
term = (last := next(it_row)) * next(it_series) * next(it_seires) 

Подробнее здесь: [url]https://stackoverflow.com/questions/79902424/how-can-i-make-my-tangent-numbers-generating-class-resumable[/url]