python - 如何降低循环大量次数的程序的时间复杂度？

Question

我正在尝试编写(全天)数字生成系统，它从 3 开始，值减 1 直到达到 1。一旦达到 1，它将其数字重置为新的起始值 2x 作为第一个数字。然后将每个新重置 2x 作为早期重置的第一个数字。如下图所示，

3 2 1 6 5 4 3 2 1 12 11 10 9 8 7 6 5 4 3 2 1...

程序应该返回用户请求的第 n 个位置的值。

用户可以输入 n < (10^12)

如果目标位置远离循环的当前位置，则尝试跳过一些步骤

# requesting position
tt = int(input())
# starting t 
t = 1
# starting value
sv = 3
# current value
cv = 3

while (True):

    # check if we have reached target time
    if (t == tt):
        # print the current value
        print("{}".format(cv))
        break

    # if there's a loong way to go, skip some 
    if (t + cv < tt):  # starting_t+current_value<target_t
        t += cv  
        sv = sv * 2  
        cv = sv  

        if cv % 2 == 0:
            if (t + cv // 2 < tt):
                t += cv // 2
                cv = cv // 2
                continue
        continue

    # check if value is 1 and double it
    if (cv == 1):
        # set new starting value
        sv = sv * 2
        # set new current value
        cv = sv
        # elapse time
        t += 1
        continue

    # elapsed time
    t += 1
    # changed value
    cv -= 1

目前，此程序需要 2 分钟以上才能返回 n>10^10 的结果。我需要尽可能地减少这个过程所花费的时间。我可以做些什么来减少这个过程所花费的时间？ (预计将其减少到几秒钟)任何引用都可能有帮助

Answer 1

总结

你可以这样做(索引从0开始，否则你需要将n替换为n - 1):

def my_seq(n):
    k = int(math.log2(n / 3 + 1)) + 1
    return 3 * (2 ** k - 1) - n


print([my_seq(i) for i in range(2)])
# [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]

这基本上是步长等于 2 的几何级数的变体，如下所示。

---

说明

第一步是注意“峰”的基础序列是 geometric progression :

x_k = a * r ** k

几何级数的前 n 项之和是 geometric series :

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 * (r ** k - 1) / (r - 1)

变成:

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

(已编辑以修复分析代码中使用整数除法而不是常规除法的错误)。