Первый шаг состоит в том, чтобы заметить, что ваша основная последовательность «пиков» представляет собой геометрическую прогрессию :
x_k = a * r ^ k
Сумма первых n членов геометрической прогрессии геометрический ряд :
sum(x_k for k in 1 to n) = a * (1 - r ^ n) / (1 - r)
Целевая последовательность в основном получается путем вычитания индекса из наибольшего члена ряда, не превышающего сам индекс.
В кодеэто выглядит следующим образом:
# note that this uses integer division hence expects integer `r`
def geom_series_int(a, r, n):
return a * (1 - r ** n) // (1 - r)
def my_seq_int(n, a=3, r=2):
i = 1
cumsum = geom_series_int(a, r, i)
while cumsum < n + 1:
i += 1
cumsum = geom_series_int(a, r, i)
return cumsum - n
print([my_seq_int(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
Конечно, можно также вычислять геометрические ряды итеративно, и это будет с вычислительной эффективностью, аналогичной приведенному выше коду, из-за того, что нахождение минимумаcumsum не превышающий индекс n выполняется с помощью цикла, но приведенный выше код работает быстрее:
def i_geom_progression(a, r):
i = 0
while True:
yield a * r ** i
i += 1
def i_geom_series(a, r):
gp = i_geom_progression(a, r)
result = next(gp)
while True:
yield result
result += next(gp)
def my_seq(n, a=3, r=2):
gs = i_geom_series(a, r)
cumsum = next(gs)
while cumsum < n + 1:
cumsum = next(gs)
return cumsum - n
print([my_seq(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
Сложность вычислений в обоих случаях составляет log(n).
Более эффективный подход состоит в том, чтобы сделать это аналитически, решив для k выражение для геометрического ряда и используя индекс n в качестве прокси для кумулятивной суммы:
n = a * (1 - r ^ k) / (1 - r)
становится:
k = log_r(1 - n * (1 - r) / a)
и, принимая неотъемлемую часть, становится:
import math
def my_seq_analytic(n, a=3, r=2):
k = int(math.log2(1 - n * (1 - r) // a) / math.log2(r)) + 1
return geom_series_int(a, r, k) - n
print([my_seq_analytic(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
Это самый быстрый подход.
В целом, предлагаемые методы намного быстрее, чем первоначально предложенный метод, упрощение которого описано в my_seq_loop() ниже:
def my_seq_loop(n, a=3, r=2):
peak = a
for i in range(1, n + 1):
if a == 1:
peak *= r
a = peak
else:
a -= 1
return a
print([my_seq_loop(i) for i in range(25)])
# [3, 2, 1, 6, 5, 4, 3, 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 24, 23, 22, 21]
. Дают некоторое представление осроки, см. тесты ниже:
%timeit my_seq_loop(10 ** 8)
# 1 loop, best of 3: 6.65 s per loop
%timeit my_seq(10 ** 8)
# 100000 loops, best of 3: 14.1 µs per loop
%timeit my_seq_int(10 ** 8)
# 100000 loops, best of 3: 11.7 µs per loop
%timeit my_seq_analytic(10 ** 8)
# 1000000 loops, best of 3: 938 ns per loop