Thay thế một danh sách các số với TV phụ dãy

Question

Cho một danh sách các số, như thế này:

lst = [0, 10, 15, 17] 

Tôi muốn một danh sách đó có các yếu tố từ i -> i + 3 cho tất cả i trong lst. Nếu có phạm vi chồng chéo, tôi muốn chúng được hợp nhất.

Vì vậy, đối với ví dụ trên, trước tiên chúng ta nhận được:

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

Nhưng đối với 2 nhóm cuối cùng, phạm vi chồng chéo lên nhau, vì vậy khi sáp nhập chúng, bạn phải:

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

Đây là sản lượng mong muốn của tôi.

Đây là những gì tôi đã nghĩ:

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] 

Tuy nhiên, đây là chậm (10000 loops, best of 3: 56 µs per loop). Tôi muốn một giải pháp numpy nếu có thể, hoặc một giải pháp python đó là nhanh hơn này.

Answer 1

Approach # 1: Một cách tiếp cận dựa trên broadcasted tổng kết và sau đó sử dụng np.unique để có được con số duy nhất -

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

Cách tiếp cận # 2: Một dựa trên tổng kết phát sóng và sau đó che -

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] 

Kiểm tra thời gian chạy

gốc cách tiếp cận -

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

Thời gian -

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 

Các nút cổ chai với hai cách tiếp cận posted vẻ như là với việc chuyển đổi sang array, mặc dù điều đó dường như được đền đáp xứng đáng tốt sau đó. Chỉ để biết thời gian dành cho chuyển đổi cho tập dữ liệu cuối cùng -

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