gxmatmars

考虑到以下问题：

无论是游戏进度还是系统还原点，随着时间增长，都会产生N个备份。实际生产生活中，距离时间最近的备份，往往更重要，比如每天一次备份，而太长时间以前的备份，可能每月一次备份就足够了。

尝试找到一个特定的删除函数D(X)，表示第X个备份，会在D(X)的步骤被删除，使得无论在哪个步骤Y，移除掉所有的X_i满足Y>=D(X_i)，剩下的数据，始终满足“越小的数据间距越大”的特点。

为此，我们考察以下数列：

[1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128]

这是一个间距逐渐增大的数列，其中1,2,3间距为1，4,6,8间距为2，8,12,16间距为4，…，64,96,128间距为32。只可惜这个数列的间距随着数据的增加而增加。用128减去这个数列，得到：

[127, 126, 125, 124, 122, 120, 116, 112, 104, 96, 80, 64, 32, 0]

看到结尾是32，从这里我们得到一点启发，是否可以让2的幂次（如2,4,8,16,32,…）存活时间更长，更难被删除？

到这里算法思路就很明确了：如果第X的存档如果在第Y步被保留，则X含2的因子的数量p需满足p>log₂(Y-X)。

这里给出以下Python代码，实现此算法：

def calc_delete_step(value, scale):
    if value == 0:
        return 0

    order = 0
    x = value
    while x % 2 == 0:
        x //= 2
        order += 1
    return value + scale * (2 ** (order + 1) - 1)

def generate_remains(value, scale):
    data = [value]
    step = 1

    while value > 0:
        for _ in range(scale):
            value -= step
            if value > 0:
                data.append(value)
        if value % (step * 2) != 0:
            value += step
        step *= 2
    return data

这里calc_delete_step的实现略有改变，这是为了使generate_remains的结果能从大到小分为长度为scale，间隔为1,2,4,…的多个组。

接下来考察结果，默认取scale=1，考察不同的N：

N	Remains
10	[10, 9, 8, 4]
30	[30, 29, 28, 24, 16]
100	[100, 99, 98, 96, 88, 80, 64]
200	[200, 199, 198, 196, 192, 176, 160, 128]
300	[300, 299, 298, 296, 288, 272, 256, 192, 128]
500	[500, 499, 498, 496, 488, 480, 448, 384, 256]
500 (scale=3)	[500, 499, 498, 497, 496, 494, 492, 488, 484, 480, 472, 464, 456, 448, 432, 416, 384, 352, 320, 256, 192, 128]

计算Remains从N倒数的差，明显发现存档的间隔是从1到2到4的逐渐增长。

N	N – r for r in Remains[::-1]
10	[0, 1, 2, 6]
30	[0, 1, 2, 6, 14]
100	[0, 1, 2, 4, 12, 20, 36]
200	[0, 1, 2, 4, 8, 24, 40, 72]
300	[0, 1, 2, 4, 12, 28, 44, 108, 172]
500	[0, 1, 2, 4, 12, 20, 52, 116, 244]
500 (scale=3)	[0, 1, 2, 3, 4, 6, 8, 12, 16, 20, 28, 36, 44, 52, 68, 84, 116, 148, 180, 244, 308, 372]

效果还是很不错的，并且还有2点需要提出：

这个算法是o(logN)的算法，可以在对数时间计算出第N步需要保留的存档。
N较大时，Remains的数量与N趋近于对数关系，与scale是线性关系。

一个优雅的存档删除方案

博客复活！