Cách hiệu quả hơn để đếm giao lộ?

Question

tôi có một danh sách 300000 danh sách (sợi track), trong đó mỗi bài hát là danh sách (x, y, z) tuples/phối:

tracks= 
[[(1,2,3),(3,2,4),...] 
[(4,2,1),(5,7,3),...] 
... 
] 

Tôi cũng có một nhóm các mặt nạ, nơi mỗi mặt nạ được định nghĩa là một danh sách các (x, y, z) tuples/phối:

mask_coords_list= 
[[(1,2,3),(8,13,4),...] 
[(6,2,2),(5,7,3),...] 
... 
] 

tôi cố gắng để tìm kiếm, cho tất cả các cặp có thể có của mặt nạ:

1. các số bản nhạc cắt nhau cặp mặt nạ-mặt nạ (để tạo ra một conn ma trận ectivity)
2. các tập hợp con của ca khúc đó cắt nhau mặt nạ, để thêm 1 cho mỗi (x, y, z) phối hợp cho mỗi ca khúc trong tập hợp con (để tạo ra một "mật độ" hình ảnh)

tôi hiện đang làm phần 1 như sau:

def mask_connectivity_matrix(tracks,masks,masks_coords_list): 
    connect_mat=zeros((len(masks),len(masks))) 
    for track in tracks: 
     cur=[] 
     for count,mask_coords in enumerate(masks_coords_list): 
      if any(set(track) & set(mask_coords)): 
       cur.append(count) 
      for x,y in list(itertools.combinations(cur,2)): 
       connect_mat[x,y] += 1 

và phần 2 như sau:

def mask_tracks(tracks,masks,masks_coords_list): 
    vox_tracks_img=zeros((xdim,ydim,zdim,len(masks))) 
    for track in tracks: 
     for count,mask in enumerate(masks_coords_list): 
      if any(set(track) & set(mask)): 
       for x,y,z in track: 
        vox_tracks_img[x,y,z,count] += 1 

Sử dụng bộ để tìm nút giao thông đã tăng tốc quá trình này tăng lên đáng kể nhưng cả hai phần stil Tôi mất hơn một giờ khi tôi có danh sách 70 mặt nạ trở lên. Có cách nào hiệu quả hơn để thực hiện việc này hơn là lặp lại cho mỗi bản nhạc không?

Answer 1

Căn chỉnh tọa độ voxel và đặt chúng thành hai ma trận scipy.sparse.sparse.csc.

Cho v là số lượng voxels, m số mặt nạ và số lượng bản nhạc.
Cho M là ma trận csc mặt nạ, kích thước (m x v), trong đó 1 tại (i, j) có nghĩa là mặt nạ tôi trùng lặp voxel j.
Cho T là ma trận csc theo dõi, kích thước (t x v), trong đó 1 tại (k, j) có nghĩa là theo dõi k chồng lên nhau voxel j.

Overlap = (M * T.transpose() > 0) # track T overlaps mask M 
Connected = (Overlap * Overlap.tranpose() > 0) # Connected masks 
Density[mask_idx] = numpy.take(T, nonzero(Overlap[mask_idx, :])[0], axis=0).sum(axis=0) 

Tôi có thể đã sai trên phiên bản cuối cùng và tôi không chắc chắn css_matrices có thể được vận hành bởi nonzero &. Bạn có thể cần phải kéo ra từng cột trong một vòng lặp và chuyển đổi nó thành một ma trận đầy đủ.

---

Tôi đã chạy một số thử nghiệm để mô phỏng những gì tôi nghĩ là một lượng dữ liệu hợp lý. Mã dưới đây mất khoảng 2 phút trên một chiếc MacBook cũ 2 năm. Nếu bạn sử dụng csr_matrices, nó mất khoảng 4 phút. Có thể có một sự cân bằng tùy thuộc vào thời lượng mỗi bản nhạc.

from numpy import * 
from scipy.sparse import csc_matrix 

nvox = 1000000 
ntracks = 300000 
nmask = 100 

# create about 100 entries per track 
tcoords = random.uniform(0, ntracks, ntracks * 100).astype(int) 
vcoords = random.uniform(0, nvox, ntracks * 100).astype(int) 
d = ones(ntracks * 100) 
T = csc_matrix((d, vstack((tcoords, vcoords))), shape=(ntracks, nvox), dtype=bool) 

# create around 10000 entries per mask 
mcoords = random.uniform(0, nmask, nmask * 10000).astype(int) 
vcoords = random.uniform(0, nvox, nmask * 10000).astype(int) 
d = ones(nmask * 10000) 
M = csc_matrix((d, vstack((mcoords, vcoords))), shape=(nmask, nvox), dtype=bool) 

Overlap = (M * T.transpose()).astype(bool) # mask M overlaps track T 
Connected = (Overlap * Overlap.transpose()).astype(bool) # mask M1 and M2 are connected 
Density = Overlap * T.astype(float) # number of tracks overlapping mask M summed across voxels 

Answer 2

Bạn có thể bắt đầu bằng cách kết hợp hai hàm để tạo cả hai kết quả cùng một lúc. Ngoài ra không cần phải tạo danh sách các kết hợp trước khi lặp, vì nó đã là một trình tạo và có thể giúp bạn tiết kiệm thời gian.

def mask_connectivity_matrix_and_tracks(tracks,masks,masks_coords_list): 
    connect_mat=zeros((len(masks),len(masks))) 
    vox_tracks_img=zeros((xdim,ydim,zdim,len(masks))) 
    for track in tracks: 
     cur=[] 
     for count,mask_coords in enumerate(masks_coords_list): 
      if any(set(track) & set(mask_coords)): 
       cur.append(count) 
       for x,y,z in track: 
        vox_tracks_img[x,y,z,count] += 1 
      for x,y in itertools.combinations(cur,2): 
       connect_mat[x,y] += 1 

Ngoài ra, điều này có thể sẽ không bao giờ "nhanh" như "hoàn thành trước khi chúng tôi chết", vì vậy cách tốt nhất là biên dịch nó bằng Cython làm mô đun c cho python.

Answer 3

Nếu bạn lưu trữ từng bộ mặt nạ điểm: (1,2,3), (1,2,4), (1,3,1) làm từ điển như sau: {1: [{2: set([3, 4])}, {3: set([1])}]}, bạn có thể kết thúc có thể kiểm tra các trận đấu nhanh hơn ... nhưng có thể không.

Answer 4

Một tối ưu hóa nhỏ (giống lớn-O, hệ số sligthly nhỏ hơn) có thể có bằng cách loại bỏ các hoạt động dự phòng:

1. không gọi set rất nhiều lần trên mỗi track và mặt nạ: gọi nó một lần cho mỗi track và một lần mỗi mặt nạ, để thiết lập phụ trợ "song song" danh sách các bộ, sau đó làm việc trên những
2. if any(someset): được ngữ nghĩa giống như if someset: nhưng chậm hơn một chút

Sẽ không tạo sự khác biệt đáng kể, nhưng có thể giúp đỡ.

Answer 5

Lame cho thấy một tiến bộ gia tăng mà có thể được thực hiện, tôi biết, nhưng:

Sets các số nguyên nhỏ có thể được mô hình hóa như bit vector sử dụng ints dài của Python. Giả sử bạn thay thế mỗi tuple bằng một id số nguyên nhỏ, sau đó chuyển đổi từng bản nhạc và từng bộ mặt nạ thành một tập hợp các id nhỏ. Bạn có thể đại diện cho những bộ như ints dài, làm cho giao lộ hoạt động nhanh hơn một chút (nhưng không nhanh hơn).

Answer 6

OK, tôi nghĩ cuối cùng tôi cũng có điều gì đó sẽ làm giảm sự phức tạp. Mã này thực sự bay so với những gì bạn có.

Dường như trước hết bạn cần phải biết bản nhạc nào trùng với mặt nạ, incidence matrix.

import numpy 
from collections import defaultdict 

def by_point(sets): 
    d = defaultdict(list) 
    for i, s in enumerate(sets): 
     for pt in s: 
      d[pt].append(i) 
    return d 

def calc(xdim, ydim, zdim, mask_coords_list, tracks): 
    masks_by_point = by_point(mask_coords_list) 
    tracks_by_point = by_point(tracks) 

    a = numpy.zeros((len(mask_coords_list), len(tracks)), dtype=int) 
    for pt, maskids in masks_by_point.iteritems(): 
     for trackid in tracks_by_point.get(pt,()): 
      a[maskids, trackid] = 1 
    m = numpy.matrix(a) 

adjacency matrix bạn đang tìm kiếm là m * m.T.

Mã bạn cho đến nay chỉ tính toán hình tam giác phía trên. Bạn có thể sử dụng triu để chỉ lấy một nửa.

am = m * m.T # calculate adjacency matrix 
    am = numpy.triu(am, 1) # keep only upper triangle 
    am = am.A # convert matrix back to array 

Tính toán voxel cũng có thể sử dụng ma trận tỷ lệ.

vox_tracks_img = numpy.zeros((xdim, ydim, zdim, len(mask_coords_list)), dtype=int) 
    for trackid, track in enumerate(tracks): 
     for x, y, z in track: 
      vox_tracks_img[x, y, z, :] += a[:,trackid] 
    return am, vox_tracks_img 

Đối với tôi điều này chạy dưới một giây cho các tập dữ liệu có hàng trăm mặt nạ và bản nhạc.

Nếu bạn có nhiều điểm xuất hiện trong mặt nạ nhưng không xuất hiện trên bất kỳ tuyến đường nào, có thể cần xóa các mục nhập cho các điểm đó từ masks_by_point trước khi vào vòng lặp.