Python 中增加整数序列的快速增量编码

Question

给定 a = [1, 2, 3, 4, 5]

编码后，a' = [1, 1, 1, 1, 1]，每个元素表示与其前一个元素相比的差异。

我知道这可以用

来完成

for i in range(len(a) - 1, 0, -1):
    a[i] = a[i] - a[i - 1]

有没有更快的方法？我在这里处理 20 亿个数字，这个过程大约需要 30 分钟。

Answer 1

您可以使用numpy.diff，例如：

import numpy as np
a = [1, 2, 3, 4, 5]
npa = np.array(a)
a_diff = np.diff(npa)

Answer 2

您可以使用 zip 将列表与偏移版本放在一起并减去这些值

a = [1, 2, 3, 4, 5]

a[1:] = [nxt - cur for cur, nxt in zip(a, a[1:])]
print(a)

输出：

[1, 1, 1, 1, 1]

出于兴趣，我运行这个，原始代码和@ynotzort 通过 timeit 回答，这比短列表的 numpy 代码快得多；保持更快地达到大约 10M 值；两者都比原始代码快约 30%。随着列表大小增加到超过 10M，numpy 代码有更多的加速，最终从大约 20M 值开始变得更快。

更新

还测试了 starmap 代码，在 20M 值时，它比 numpy 代码快大约 40%...

更新 2

@Chris 在他们的回答中有一些更全面的性能数据。通过使用 itertools.islice 生成偏移列表，可以进一步加快这个答案（大约 10%）：

a = [a[0], *[nxt - cur for cur, nxt in zip(a, islice(a, 1, None))]]

Answer 3

使用 itertools.starmap、islice 和 operator.sub 的一种方式：

from operator import sub
from itertools import starmap, islice

l = list(range(1, 10000000))

[l[0], *starmap(sub, zip(islice(l, 1, None), l))]

输出：

[1, 1, 1, ..., 1]

基准：

l = list(range(1, 100000000))

# OP's method
%timeit [l[i] - l[i - 1] for i in range(len(l) - 1, 0, -1)]    
# 14.2 s ± 373 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# numpy approach by @ynotzort
%timeit np.diff(l)
# 8.52 s ± 301 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# zip approach by @Nick
%timeit [nxt - cur for cur, nxt in zip(l, l[1:])]
# 7.96 s ± 243 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# itertool and operator approach by @Chris
%timeit [l[0], *starmap(sub, zip(islice(l, 1, None), l))]
# 6.4 s ± 255 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Python 中增加整数序列的快速增量编码

Fast delta encoding for increasing sequence of integers in Python

python

compression

algorithm