是什么让 python 的 itertools.groupby 如此之快？

Question

我正在评估外观和说序列的连续术语（更多关于它的信息：https : //en.wikipedia.org/wiki/Look-and-say_sequence）。

我使用了两种方法并对它们进行计时。在第一种方法中，我只是迭代每个术语来构建下一个。在第二个中，我曾经itertools.groupby()这样做过。时差相当大，所以我做了一个图来玩：

是什么让itertools.groupby()效率如此之高？两种方法的代码如下：

第一种方法：

def find_block(seq):
    block = [seq[0]]
    seq.pop(0)

    while seq and seq[0] == block[0]:
        block.append(seq[0])
        seq.pop(0)

    return block

old = list('1113222113')
new = []
version1_time = []

for i in range(40):
    start = time.time()
    while old:
        block = find_block(old)
        new.append(str(len(block)))
        new.append(block[0])
    old, new = new, []
    end = time.time()
    version1_time.append(end-start)

方法二：

seq = '1113222113'
version2_time = []

def lookandread(seq):
    new = ''
    for value, group in itertools.groupby(seq):
        new += '{}{}'.format(len(list(group)), value)
    return new

for i in range(40):
    start = time.time()
    seq = lookandread(seq)
    end = time.time()
    version2_time.append(end-start)

Answer 1

坦率地说，groupby 解决方案并不快，您的其他解决方案很慢。

\n

因为慢速序列不能正确迭代old序列，而是使用 一次解构一个数字seq.pop(0)。每次弹出需要 \xce\x98( len(seq)) 时间，整个while old循环需要 \xce\x98(n^2) 时间，其中 n 是该循环之前的初始长度。

\n

由于字符串的重复串联，groupby 解决方案在 \xce\x98(n) 和 \xce\x98(n^2) 之间的某个时间（取决于 Python 实现和内存分配器）执行相同的操作。您可能使用过 CPython，它的优化主要使其呈线性。您可以通过使用结果列表而不是字符串来保证线性时间。

\n

此外，n 在 40 轮中每轮呈指数增长约 30%（打印长度或参见维基百科文章）。因此，使用二次算法，第 i 轮大约需要 \xce\x98((1.3^i)^2) = \xce\x98(1.69^i) 时间。那增长得很快。尽管奇怪的是你花了这么长时间。对于最后一轮（i=39），你的图显示了 175 秒，而我只需要 5 秒。

\n