더 효율적인 교차로 수 계산 방법은 무엇입니까?

Question

난 각 트랙 (X, Y, Z) 튜플/목록이다 300,000 목록 (섬유 트랙)의 목록을하는 좌표

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

I 또한, 여기서 각각의 마스크가 마스크의 그룹 (X, Y, Z) 튜플/목록으로 정의되는 좌표

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

I 마스크의 모든 가능한 쌍에 대한 찾기 위해 시도하고있다 :

1. 서로 교차하는 트랙의 개수 마스크 - 마스크 쌍 (conn ectivity 행렬) 각각의 (X, Y, Z에 1을 추가하기 위해, 각각의 마스크를 교차 트랙
2. 서브 세트)은 "밀도"이미지를 생성하기 위해 (서브 세트 트랙마다 좌표)

크게

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 

교차점을 찾기 위해 세트를 사용하여이 질주하고있다이 과정을하지만 두 부분 STIL :과 같이

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 

와 2 부 :

나는 현재과 같이 1 부하고 있어요 내가 70 개 이상의 가면 목록을 가지고있을 때 한 시간 이상 걸릴거야. 각 트랙을 반복하는 것보다 더 효율적인 방법이 있습니까?

Answer 1

보셀 좌표를 선형화하고 두 개의 scipy.sparse.sparse.csc 행렬에 넣습니다.

v를 voxels의 수 m 마스크의 수 t 트랙의 수로하자.
M을 마스크 csc 행렬, size (m x v)라고하면, 여기서 i 1은 마스크 i가 복셀 j와 겹치는 것을 의미합니다.
T를 트랙 csc 행렬, 크기 (t x v)라고하면, 여기서 a 1 (k, j)는 트랙 k가 복셀 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) 

나는 마지막에 잘못 될 수도 있고, 나는 확실히 css_matrices가 0 & 걸릴에 의해 조작 할 수 아니에요. 루프의 각 열을 꺼내 전체 행렬로 변환해야 할 수도 있습니다.

---

합리적인 양의 데이터를 시뮬레이션하려고 시도한 일부 실험을 실행했습니다. 아래의 코드는 2 년 된 MacBook에서 약 2 분이 소요됩니다. csr_matrices를 사용하면 약 4 분이 걸립니다. 아마도 각 트랙의 길이에 따라 절충안이있을 수 있습니다.

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

아마도 두 가지 기능을 결합하여 한 번에 두 결과를 모두 만들 수 있습니다. 또한 반복 전에 조합 목록을 만들 필요가 없습니다. 이미 생성기이므로 시간을 절약 할 수 있습니다. 가장 좋은 방법은 결국 파이썬의 C 모듈로 사이 썬과 함께 컴파일하는 것입니다, 그래서 "우리가 죽기 전에 완료"

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 

또한, 이것은 아마도 같이 "빠른"으로하지 않습니다.

Answer 3

각 마스크 세트를 (1,2,3), (1,2,4), (1,3,1)과 같은 사전으로 저장 한 경우 : {1: [{2: set([3, 4])}, {3: set([1])}]}으로 끝날 수 있습니다. 일치하는 항목을 더 빨리 확인할 수는 있지만 어쩌면 불가능할 수도 있습니다.

Answer 4

사소한 최적화 (같은 큰-O, sligthly 작은 승수)를 제거 중복 조작에 의해 가지게 될 수있다 :

이

1. 는 각 트랙 및 마스크에 set 많은 시간을 호출하지 않는 : 트랙 당 한 번만 호출 마스크에 한 번, if someset:으로 의미하는
2. if any(someset): 작업 후, 동일한 세트의 보조 "병렬"목록입니다 설정하되 약간 느린

, 극적인 차이를 만들하지 않습니다하지만, 섬세하게 도움이 될지도 모릅니다.

Answer 5

절름발이가 될 수있는 또 다른 점진적 개선, 내가 아는을 제안하지만합니다 : 작은 정수의

세트 파이썬의 길이의 int를 사용하여 비트 벡터로 모델링 할 수있다. 각 튜플을 작은 정수 id로 바꾼 다음 각 트랙과 각 마스크 코드 집합을 작은 ID 집합으로 변환한다고 가정 해보십시오. 이러한 집합을 long int로 표현할 수 있으므로 교차 연산을 조금 더 빠르게 할 수 있습니다 (그러나 점근 적으로 빠르지는 않음).

Answer 6

좋아요, 마침내 복잡성을 줄이는 뭔가가 있다고 생각합니다. 이 코드는 여러분이 가지고있는 것과 비교할 때 실제로 비행해야합니다.

어떤 트랙이 어떤 마스크와 일치하는지 먼저 알아야 할 것 같습니다 (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 당신이 찾고있는이 m * m.T입니다.

지금까지 가지고있는 코드는 위 삼각형만을 계산합니다. triu을 사용하면 그 절반을 움켜 쥘 수 있습니다.

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

보셀 계산도 입사 매트릭스를 사용할 수 있습니다.

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 

내게는 수백 개의 마스크와 트랙이있는 데이터 세트에서 초 단위로 실행됩니다.

마스크에 표시되지만 트랙에없는 많은 포인트가있는 경우 루프에 들어가기 전에 해당 포인트의 항목을 masks_by_point에서 삭제하는 것이 좋습니다.