algorithm - 如何使用固定超时和尝试次数实现指数退避/延迟计算？

Question

我见过的大多数退避/延迟算法都有固定的尝试次数或固定的超时，但不是两者兼而有之。

我想在 T 秒内准确地进行 M 次尝试，它们之间具有指数间隔，因此“T = delay(0) + delay(1) + ... + delay(M-1)”，其中“delay(N) = (e^N - 1) / e"（其中 N - 重试次数）。

如何计算上述描述中的“e”值，以便在整个超时 T 内进行准确的 M 次尝试（预先指定 M 和 T）？

Answer 1

由于“T”是“e”的单调函数，因此您可以执行二进制搜索以找到适合的最佳值。

这是一个示例 Python 程序，用于在给定“T”和“M”的情况下查找此类“e”：

def total_time(e, M):
    current = 1
    total = 0
    for i in range(M):
        total += current-1
        current *= e
    return total

def find_best_e(T, M):
    a, b = 0, T
    while abs(a-b) > 1e-6:
        m = (a+b)/2.0
        if total_time(m, M) > T:
            b = m
        else:
            a = m
    return (a+b)/2


e = find_best_e(10, 3)
print([e**n-1 for n in range(3)])