python - 用平坦的子范围替换数字列表

Question

给定一个数字列表，如下所示:

lst = [0, 10, 15, 17]

我想要一个列表，其中包含 i -> i + 3 中的元素，用于 lst 中的所有 i。如果存在重叠范围，我希望将它们合并。

所以，对于上面的例子，我们首先得到:

[0, 1, 2, 3,     10, 11, 12, 13,     15, 16, 17, 18,   17, 18, 19, 20]

但是对于最后 2 组，范围重叠，所以在合并它们时，您有:

[0, 1, 2, 3,     10, 11, 12, 13,     15, 16, 17, 18,     19, 20]

这是我想要的输出。

这是我想到的:

from collections import OrderedDict

res = list(OrderedDict.fromkeys([y for x in lst for y in range(x, x + 4)]).keys())
print(res) = [0, 1, 2, 3, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20]

但是，这很慢(10000 次循环，最好的 3 次:每次循环 56 µs)。如果可能的话，我想要一个 numpy 解决方案，或者一个比这更快的 python 解决方案。

Answer 1

方法 #1: 一种基于 broadcasted 的方法求和，然后使用 np.unique 获取唯一数字 -

np.unique(np.asarray(lst)[:,None] + np.arange(4))

方法 #2: 另一种基于广播求和然后掩蔽的方法 -

def mask_app(lst, interval_len = 4):
    arr = np.array(lst)
    r = np.arange(interval_len)
    ranged_vals = arr[:,None] + r
    a_diff = arr[1:] - arr[:-1]
    valid_mask = np.vstack((a_diff[:,None] > r, np.ones(interval_len,dtype=bool)))
    return ranged_vals[valid_mask]

运行时测试

原始方法-

from collections import OrderedDict
def org_app(lst):
    list(OrderedDict.fromkeys([y for x in lst for y in range(x, x + 4)]).keys())

时间 -

In [409]: n = 10000

In [410]: lst = np.unique(np.random.randint(0,4*n,(n))).tolist()

In [411]: %timeit org_app(lst)
     ...: %timeit np.unique(np.asarray(lst)[:,None] + np.arange(4))
     ...: %timeit mask_app(lst, interval_len = 4)
     ...: 
10 loops, best of 3: 32.7 ms per loop
1000 loops, best of 3: 1.03 ms per loop
1000 loops, best of 3: 671 µs per loop

In [412]: n = 100000

In [413]: lst = np.unique(np.random.randint(0,4*n,(n))).tolist()

In [414]: %timeit org_app(lst)
     ...: %timeit np.unique(np.asarray(lst)[:,None] + np.arange(4))
     ...: %timeit mask_app(lst, interval_len = 4)
     ...: 
1 loop, best of 3: 350 ms per loop
100 loops, best of 3: 14.7 ms per loop
100 loops, best of 3: 9.73 ms per loop

这两种已发布方法的瓶颈似乎在于转换为 array，尽管这似乎在之后得到了很好的返回。只是为了了解最后一个数据集的转换所花费的时间 -

In [415]: %timeit np.array(lst)
100 loops, best of 3: 5.6 ms per loop