Python/NumPy: thực hiện một khoản tiền chạy (nhưng không hoàn toàn)

Question

Với hai mảng chiều dài bằng nhau, một dữ liệu tổ chức, một tổ chức kết quả nhưng ban đầu thiết lập để không, ví dụ:

a = numpy.array([1, 0, 0, 1, 0, 1, 0, 0, 1, 1]) 
b = numpy.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]) 

Tôi muốn như để tính toán tổng của tất cả các tập con có thể có của ba phần tử liền kề trong a. Nếu tổng là 0 hoặc 1, ba phần tử tương ứng trong b sẽ không thay đổi; chỉ nếu tổng vượt quá 1 là ba phần tử tương ứng trong b thiết lập để 1, do đó sau khi tính toán b trở nên

array([0, 0, 0, 1, 1, 1, 0, 1, 1, 1]) 

Một vòng lặp đơn giản sẽ thực hiện điều này:

for x in range(len(a)-2): 
    if a[x:x+3].sum() > 1: 
     b[x:x+3] = 1 

Sau này, b có biểu mẫu mong muốn.

Tôi phải làm điều này cho một lượng lớn dữ liệu, vì vậy tốc độ là một vấn đề. Có cách nào nhanh hơn trong NumPy để thực hiện thao tác trên không?

(Tôi hiểu điều này tương tự như một sự giải thể, nhưng không hoàn toàn giống nhau).

Answer 1

Bạn có thể bắt đầu với một chập, chọn các giá trị vượt quá 1, và cuối cùng là sử dụng một "giãn nở":

b = numpy.convolve(a, [1, 1, 1], mode="same") > 1 
b = b | numpy.r_[0, b[:-1]] | numpy.r_[b[1:], 0] 

Vì đây tránh vòng lặp Python, nó phải là nhanh hơn so với cách tiếp cận của bạn, nhưng tôi không làm timings.

Một cách khác là sử dụng một chập thứ hai để giãn ra:

kernel = [1, 1, 1] 
b = numpy.convolve(a, kernel, mode="same") > 1 
b = numpy.convolve(b, kernel, mode="same") > 0 

Nếu bạn có scipy sẵn, tuy nhiên một lựa chọn cho sự giãn nở là

b = numpy.convolve(a, [1, 1, 1], mode="same") > 1 
b = scipy.ndimage.morphology.binary_dilation(b) 

Sửa: Bằng cách some timings, Tôi thấy rằng giải pháp này có vẻ nhanh nhất đối với mảng lớn:

b = numpy.convolve(a, kernel) > 1 
b[:-1] |= b[1:] # Shift and "smearing" to the *left* (smearing with b[1:] |= b[:-1] does not work) 
b[:-1] |= b[1:] # … and again! 
b = b[:-2] 

Đối với một mảng gồm một triệu mục, nó nhanh hơn 200 lần so với cách tiếp cận ban đầu của bạn trên máy của tôi. Như được chỉ ra bởi EOL trong các ý kiến, giải pháp này có thể được coi là một chút mong manh, mặc dù, vì nó phụ thuộc vào chi tiết thực hiện của NumPy.

Answer 2

Bạn có thể tính toán "chập" tiền một cách hiệu quả với:

>>> a0 = a[:-2] 
>>> a1 = a[1:-1] 
>>> a2 = a[2:] 
>>> a_large_sum = a0 + a1 + a2 > 1 

nhật b sau đó có thể được thực hiện một cách hiệu quả bằng cách viết một cái gì đó có nghĩa là "ít nhất một trong ba nước láng giềng a_large_sum giá trị là True" : bạn lần đầu tiên mở rộng bạn a_large_sum mảng trở lại cùng một số yếu tố như a (ở bên phải, bên trái và bên phải, và sau đó sang bên trái):

>>> a_large_sum_0 = np.hstack([a_large_sum, [False, False]]) 
>>> a_large_sum_1 = np.hstack([[False], a_large_sum, [False]]) 
>>> a_large_sum_2 = np.hstack([[False, False], a_large_sum]) 

sau đó, bạn lấy b một cách hiệu quả:

>>> b = a_large_sum_0 | a_large_sum_1 | a_large_sum_2 

này cung cấp cho các kết quả mà bạn có được, nhưng theo một cách rất hiệu quả, thông qua một đòn bẩy của NumPy vòng nhanh nội bộ.

PS: Cách tiếp cận này về bản chất giống như giải pháp đầu tiên của Sven, nhưng có nhiều cách cho người đi bộ hơn mã trang nhã của Sven; nó là nhanh, tuy nhiên. Giải pháp thứ hai của Sven (đôi convolve()) thậm chí còn thanh lịch hơn, và nó nhanh gấp hai lần.

Answer 3

Bạn cũng có thể muốn xem NumPy's stride_tricks. Sử dụng thiết lập thời gian của Sven (xem liên kết trong câu trả lời của Sven), tôi thấy rằng cho (rất) mảng lớn, đây cũng là một cách nhanh chóng để làm những gì bạn muốn (tức là với định nghĩa của bạn về a):

shape = (len(a)-2,3) 
strides = a.strides+a.strides 
a_strided = numpy.lib.stride_tricks.as_strided(a, shape=shape, strides=strides) 
b = np.r_[numpy.sum(a_strided, axis=-1) > 1, False, False] 
b[2:] |= b[1:-1] | b[:-2] 

Sau khi chỉnh sửa (xem bình luận dưới đây) nó không còn là cách nhanh nhất.

Điều này tạo ra chế độ xem đặc biệt được kéo dài trên mảng ban đầu của bạn. Dữ liệu trong a không được sao chép nhưng chỉ được xem theo cách mới. Về cơ bản, chúng tôi muốn tạo một mảng mới trong đó chỉ mục cuối cùng chứa các mảng con mà chúng tôi muốn tổng hợp (tức là ba phần tử mà bạn muốn tính tổng). Bằng cách này, chúng ta có thể dễ dàng tổng hợp cuối cùng với lệnh cuối cùng.

Phần tử cuối cùng của hình dạng mới này phải là 3 và phần tử đầu tiên sẽ là độ dài a trừ 2 (vì chúng tôi chỉ có thể tổng hợp thành phần tử số -2).

Danh sách sải chân chứa các bước, theo byte, mảng mới a_strided cần thực hiện để đến phần tử tiếp theo trong mỗi kích thước của hình dạng. Nếu bạn đặt các giá trị này bằng nhau, điều đó có nghĩa là a_strided[0,1] và a_strided[1,0] cả hai đều là a[1], chính xác là những gì chúng tôi muốn. Trong một mảng bình thường, đây không phải là trường hợp (bước đầu tiên sẽ là "kích thước-of-first-dimension lần length-of-array-first-dimension (= shape [0])"), nhưng trong trường hợp này chúng ta có thể tận dụng tốt nó.

Không chắc chắn nếu tôi giải thích điều này tất cả thực sự tốt, nhưng chỉ cần in a_strided và bạn sẽ thấy kết quả là gì và làm thế nào dễ dàng điều này làm cho hoạt động.