hiệu quả thực hiện Python so sánh mảng NumPy

Question

nền

Tôi có hai mảng NumPy mà tôi muốn sử dụng để thực hiện một số thao tác so sánh trong thư mục/cách nhanh chóng hiệu quả nhất có thể. Cả hai chỉ chứa int không dấu.

pairs là một mảng n x 2 x 3, nắm giữ một danh sách dài các tọa độ 3D cặp (đối với một số thuật ngữ, các mảng pairs chứa một tập các cặp ...) - tức là

# full pairs array 
In [145]: pairs 
Out[145]: 
    array([[[1, 2, 4], 
     [3, 4, 4]], 
     ..... 
     [[1, 2, 5], 
     [5, 6, 5]]]) 

# each entry contains a pair of 3D coordinates 
In [149]: pairs[0] 
Out[149]: 
array([[1, 2, 4], 
     [3, 4, 4]]) 

positions là một mảng n x 3 nắm giữ một bộ 3D phối

In [162]: positions 
Out[162]: 
array([[ 1, 2, 4], 
     [ 3, 4, 5], 
     [ 5, 6, 3], 
     [ 3, 5, 6], 
     [ 6, 7, 5], 
     [12, 2, 5]]) 

Goal tôi muốn tạo ra một mảng whi ch là một tập hợp con của mảng pairs, nhưng chứa các mục chỉ có tối đa một trong các cặp nằm trong mảng vị trí - nghĩa là không có cặp nào mà cặp BOTH nằm trong mảng vị trí. Đối với một số thông tin tên miền, mỗi cặp sẽ có ít nhất một trong các vị trí ghép đôi bên trong danh sách vị trí.

phương pháp tiếp cận cố gắng cho đến nay cách tiếp cận ngây thơ ban đầu của tôi là để lặp qua mỗi cặp trong mảng pairs, và trừ mỗi hai vị trí cặp từ positions vector, việc xác định nếu trong cả hai trường hợp, chúng tôi thấy một trận đấu chỉ định bởi sự hiện diện của một 0 ở cả các vectơ mà đến từ các hoạt động trừ:

if (~(positions-pair[0]).any(axis=1)).any() and 
    (~(positions-pair[1]).any(axis=1)).any(): 
    # both members of the pair were in the positions array - 
    # these weren't the droids we were looking for 
    pass 
else: 
    # append this set of pairs to a new matrix 

này hoạt động tốt, và lợi dụng một số vector hóa, nhưng có lẽ là một cách tốt hơn để làm điều này?

Đối với một số phần nhạy cảm về hiệu suất của chương trình này, tôi đã viết lại những thứ với Cython, nó đã mang lại một tốc độ lớn, mặc dù trong trường hợp này (ít nhất là dựa trên một thực thi lồng nhau ngây thơ) chậm hơn so với cách tiếp cận được nêu ở trên.

Nếu mọi người có đề xuất, tôi vui mừng được hồ sơ và báo cáo lại (Tôi có tất cả các cơ sở hạ tầng định cấu hình).

Answer 1

Approach # 1

Như đã đề cập trong câu hỏi, cả hai mảng chỉ chứa unsigned ints, có thể bị khai thác để trộn XYZ 's vào một chỉ số tuyến tính phiên bản tương đương với đó sẽ là duy nhất cho mỗi XYZ triplet độc đáo . Việc thực hiện sẽ giống như thế này -

maxlen = np.max(pairs,axis=(0,1)) 
dims = np.append(maxlen[::-1][:-1].cumprod()[::-1],1) 

pairs1D = np.dot(pairs.reshape(-1,3),dims) 
positions1D = np.dot(positions,dims) 
mask_idx = ~(np.in1d(pairs1D,positions1D).reshape(-1,2).all(1)) 
out = pairs[mask_idx] 

Vì bạn đang đối phó với 3D tọa độ, bạn cũng có thể sử dụng để kiểm tra cdist giống hệt XYZ ba giữa các mảng đầu vào. Danh sách tiếp theo là hai triển khai với ý tưởng đó trong tâm trí.

Cách tiếp cận # 2

from scipy.spatial.distance import cdist 

p0 = cdist(pairs[:,0,:],positions) 
p1 = cdist(pairs[:,1,:],positions) 
out = pairs[((p0==0) | (p1==0)).sum(1)!=2] 

Approach # 3

mask_idx = ~((cdist(pairs.reshape(-1,3),positions)==0).any(1).reshape(-1,2).all(1)) 
out = pairs[mask_idx] 

---

kiểm tra Runtime -

In [80]: n = 5000 
    ...: pairs = np.random.randint(0,100,(n,2,3)) 
    ...: positions= np.random.randint(0,100,(n,3)) 
    ...: 

In [81]: def cdist_split(pairs,positions): 
    ...: p0 = cdist(pairs[:,0,:],positions) 
    ...: p1 = cdist(pairs[:,1,:],positions) 
    ...: return pairs[((p0==0) | (p1==0)).sum(1)!=2] 
    ...: 
    ...: def cdist_merged(pairs,positions): 
    ...: mask_idx = ~((cdist(pairs.reshape(-1,3),positions)==0).any(1).reshape(-1,2).all(1)) 
    ...: return pairs[mask_idx] 
    ...: 
    ...: def XYZ_merged(pairs,positions): 
    ...: maxlen = np.max(pairs,axis=(0,1)) 
    ...: dims = np.append(maxlen[::-1][:-1].cumprod()[::-1],1) 
    ...: pairs1D = np.dot(pairs.reshape(-1,3),dims) 
    ...: positions1D = np.dot(positions,dims) 
    ...: mask_idx1 = ~(np.in1d(pairs1D,positions1D).reshape(-1,2).all(1)) 
    ...: return pairs[mask_idx1] 
    ...: 

In [82]: %timeit cdist_split(pairs,positions) 
1 loops, best of 3: 662 ms per loop 

In [83]: %timeit cdist_merged(pairs,positions) 
1 loops, best of 3: 615 ms per loop 

In [84]: %timeit XYZ_merged(pairs,positions) 
100 loops, best of 3: 4.02 ms per loop 

kiểm chứng kết quả -

In [85]: np.allclose(cdist_split(pairs,positions),cdist_merged(pairs,positions)) 
Out[85]: True 

In [86]: np.allclose(cdist_split(pairs,positions),XYZ_merged(pairs,positions)) 
Out[86]: True 

Answer 2

Xây dựng trên nhận xét của tôi:

Mở rộng pairs là thú vị hơn. Cảm thấy tự do để thử nghiệm với lớn hơn, thực tế hơn, mảng:

In [260]: pairs = np.array([[[1,2,4],[3,4,4]],[[1,2,5],[5,6,5]],[[3,4,5],[3,5,6]],[[6,7,5],[1,2,3]]]) 

In [261]: positions = np.array([[ 1, 2, 4], 
     [ 3, 4, 5], 
     [ 5, 6, 3], 
     [ 3, 5, 6], 
     [ 6, 7, 5], 
     [12, 2, 5]]) 

Mở rộng cả hai mảng thành các hình dạng broadcastable:

In [262]: I = pairs[None,...]==positions[:,None,None,:] 

In [263]: I.shape 
Out[263]: (6, 4, 2, 3) 

lớn mảng boolean, cho thấy phần tử bằng yếu tố phù hợp trên tất cả các khía cạnh. Giảm miễn phí để thay thế các so sánh khác (difference ==0, np.isclose cho phao, v.v.).

In [264]: J = I.all(axis=-1).any(axis=0).sum(axis=-1) 

In [265]: J 
Out[265]: array([1, 0, 2, 1]) 

Hợp nhất kết quả ở các kích thước khác nhau. Ghép tất cả các số trên tọa độ, so khớp bất kỳ vị trí nào trên các vị trí, đếm số trận đấu theo cặp.

In [266]: pairs[J==1,...] 
Out[266]: 
array([[[1, 2, 4], 
     [3, 4, 4]], 

     [[6, 7, 5], 
     [1, 2, 3]]]) 

J==1 đại diện cho các phần tử chỉ có một giá trị của cặp khớp. (xem lưu ý cuối)

Sự kết hợp của any, and và sum làm việc này cho trường hợp thử nghiệm, nhưng có thể cần điều chỉnh với (các) trường hợp thử nghiệm lớn hơn. Nhưng ý tưởng thường được áp dụng.

---

Đối với kích thước mảng là https://stackoverflow.com/a/31901675/901925 kiểm tra, giải pháp của tôi khá chậm. Đặc biệt nó đang thực hiện thử nghiệm == dẫn đến I với hình dạng (5000, 5000, 2, 3).

Nén kích thước cuối cùng sẽ giúp rất nhiều

dims = np.array([10000,100,1]) # simpler version of dims from XYZmerged 
pairs1D = np.dot(pairs.reshape(-1,3),dims) 
positions1D = np.dot(positions,dims) 
I1d = pairs1D[:,None]==positions1D[None,:] 
J1d = I1d.any(axis=-1).reshape(pairs.shape[:2]).sum(axis=-1) 

Tôi đã thay đổi biểu hiện J1d để phù hợp với tôi - để đếm số lượng các trận đấu mỗi cặp.

Các in1d1 rằng Divakar sử dụng thậm chí còn nhanh hơn:

mask = np.in1d(pairs1D, positions1D).reshape(-1,2) 
Jmask = mask.sum(axis=-1) 

---

Tôi chỉ nhận ra rằng OP là yêu cầu cho at most one of the pairs is in the positions array. Khi tôi đang thử nghiệm cho exactly one match per pair. Vì vậy, tất cả các bài kiểm tra của tôi nên được đổi thành pairs[J<2,...].

(trong mẫu ngẫu nhiên cụ thể của tôi cho n = 5000, hóa ra là mọi thứ. Không có bất kỳ số nào trong số .).