Làm cách nào tôi có thể cải thiện hiệu quả của vòng lặp cố định này

Question

Tôi có một mảng có chứa các nhãn sần. Tôi muốn tính toán số cho mỗi nhãn dựa trên kích thước và khung giới hạn của nó. Làm thế nào tôi có thể viết này hiệu quả hơn để nó thực tế để sử dụng trên mảng lớn (~ 15.000 nhãn)?

A = array([[ 1, 1, 0, 3, 3], 
      [ 1, 1, 0, 0, 0], 
      [ 1, 0, 0, 2, 2], 
      [ 1, 0, 2, 2, 2]]) 

B = zeros(4) 

for label in range(1, 4): 
    # get the bounding box of the label 
    label_points = argwhere(A == label) 
    (y0, x0), (y1, x1) = label_points.min(0), label_points.max(0) + 1 

    # assume I've computed the size of each label in a numpy array size_A 
    B[ label ] = myfunc(y0, x0, y1, x1, size_A[label]) 

Answer 1

Tôi thực sự không thể thực hiện điều này một cách hiệu quả bằng cách sử dụng một số chức năng vectơ của NumPy, vì vậy có thể triển khai Python thông minh sẽ nhanh hơn.

def first_row(a, labels): 
    d = {} 
    d_setdefault = d.setdefault 
    len_ = len 
    num_labels = len_(labels) 
    for i, row in enumerate(a): 
     for label in row: 
      d_setdefault(label, i) 
     if len_(d) == num_labels: 
      break 
    return d 

Hàm này trả về một cuốn từ điển lập bản đồ mỗi nhãn để chỉ số của dòng đầu tiên nó xuất hiện trong. Áp dụng các chức năng để A, A.T, A[::-1] và A.T[::-1] cũng cung cấp cho bạn cột đầu tiên cũng như hàng cuối cùng và cột.

Nếu bạn muốn danh sách thay vì từ điển, bạn có thể biến từ điển thành danh sách bằng cách sử dụng map(d.get, labels). Ngoài ra, bạn có thể sử dụng một mảng NumPy thay vì từ điển ngay từ đầu, nhưng bạn sẽ mất khả năng rời khỏi vòng lặp sớm ngay khi tất cả các nhãn được tìm thấy.

Tôi muốn được quan tâm liệu (và bao nhiêu) điều này thực sự tăng tốc mã của bạn, nhưng tôi tự tin rằng nó nhanh hơn giải pháp ban đầu của bạn.

Answer 2

Nút cổ chai thực hiện dường như thực sự là cuộc gọi đến argmax. Nó có thể tránh được bằng cách thay đổi vòng lặp như sau (chỉ tính y0, y1, nhưng dễ dàng để khái quát để x0, x1):

for label in range(1, 4): 
    comp = (A == label) 
    yminind = comp.argmax(0) 
    ymin = comp.max(0) 
    ymaxind = comp.shape[0] - comp[::-1].argmax(0) 
    y0 = yminind[ymin].min() 
    y1 = ymaxind[ymin].max() 

Tôi không chắc chắn về lý do cho sự khác biệt hiệu suất, nhưng một lý do có thể là tất cả các hoạt động như ==, argmax và max có thể preallocation mảng đầu ra của chúng trực tiếp từ hình dạng của mảng đầu vào, điều này là không thể cho argwhere.

Answer 3

Thuật toán:

1. thay đổi mảng một chiều
2. có được chỉ số sắp xếp theo argsort()
3. có được phiên bản sắp xếp của trên mảng chiều như sorted_A
4. sử dụng ở đâu() và diff() để tìm vị trí thay đổi nhãn trong sắp xếp_A
5. sử dụng vị trí thay đổi và chỉ mục sắp xếp để lấy vị trí ban đầu của nhãn trong một thứ nguyên.
6. tính hai vị trí thứ nguyên từ vị trí thứ nguyên trên.

cho mảng lớn như (7000, 9000), có thể hoàn thành phép tính trong 30 giây.

đây là mã:

import numpy as np 

A = np.array([[ 1, 1, 0, 3, 3], 
      [ 1, 1, 0, 0, 0], 
      [ 1, 0, 0, 2, 2], 
      [ 1, 0, 2, 2, 2]]) 

def label_range(A): 
    from itertools import izip_longest 
    h, w = A.shape 
    tmp = A.reshape(-1) 

    index = np.argsort(tmp) 
    sorted_A = tmp[index] 
    pos = np.where(np.diff(sorted_A))[0]+1 
    for p1,p2 in izip_longest(pos,pos[1:]): 
     label_index = index[p1:p2] 
     y = label_index // w 
     x = label_index % w 

     x0 = np.min(x) 
     x1 = np.max(x)+1 
     y0 = np.min(y) 
     y1 = np.max(y)+1 
     label = tmp[label_index[0]] 

     yield label,x0,y0,x1,y1 

for label,x0,y0,x1,y1 in label_range(A): 
    print "%d:(%d,%d)-(%d,%d)" % (label, x0,y0,x1,y1) 

#B = np.random.randint(0, 100, (7000, 9000)) 
#list(label_range(B)) 

Answer 4

Một phương pháp:

sử dụng bincount() để có được nhãn đếm trong mỗi hàng và cột, và lưu các thông tin trong các hàng và cols mảng.

Đối với mỗi nhãn, bạn chỉ cần tìm kiếm dải ô theo hàng và cột.Nó nhanh hơn sắp xếp, trên máy tính của tôi, nó có thể thực hiện phép tính trong vài giây.

def label_range2(A): 
    maxlabel = np.max(A)+1 
    h, w = A.shape 
    rows = np.zeros((h, maxlabel), np.bool) 
    for row in xrange(h): 
     rows[row,:] = np.bincount(A[row,:], minlength=maxlabel) > 0 

    cols = np.zeros((w, maxlabel), np.bool) 
    for col in xrange(w): 
     cols[col,:] =np.bincount(A[:,col], minlength=maxlabel) > 0 

    for label in xrange(1, maxlabel): 
     row = rows[:, label] 
     col = cols[:, label] 
     y = np.where(row)[0] 
     x = np.where(col)[0] 
     x0 = np.min(x) 
     x1 = np.max(x)+1 
     y0 = np.min(y) 
     y1 = np.max(y)+1   
     yield label, x0,y0,x1,y1 

Answer 5

Sử dụng PyPy bạn chỉ có thể chạy vòng lặp và không phải lo lắng về vectơ. Nó phải nhanh.