更換號碼的清單，平子範圍

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 loops, best of 3: 56 µs per loop）。如果可能的話，我想要一個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