효율적인 파티클 링킹 알고리즘

Question

시간이 지남에 따라 다양한 파티클의 XY 위치를 가진 파일 묶음이 있습니다. 나는 입자를 통과하려고 노력하고 있으며, 어떤 거리 기준을 만족시키면서 함께 결합되어야 하는지를 알아 본다. 나는 프로그래밍에 익숙하지 않고, 지금까지 시도한 모든 것이 정말로 느리다. 나는 팬더 데이터 프레임에이 모든 데이터를 저장하고 있습니다. 일부 프레임이 누락 된 경우에도

particle frame x y 
    1   2 300 400 
    1   3 301 401 
    1   4 300 400 
    1   5 301 400 
    1   10 302 401 
    1   11 301 402 
    1   12 300 401 

입자가 같은 자리에 기본적으로 있기 때문에 :

particle frame x y 
1    2 300 400 
1    3 301 401 
1    4 300 400 
1    5 301 400 
2    10 302 401 
2    11 301 402 
2    12 300 401 

을하고되고 싶은 : 그래서 예를 들면, 나는이있을 수 있습니다. 실제 데이터 프레임에는 수백에서 수천 개의 입자가있을 수 있습니다.

I 먼저 간단히 모든 다른 입자의 첫 번째 프레임을 반복하는, 즉 루프 내에서 각 입자의 마지막 프레임을 통해 반복하고, 시도이 30 분 파일에 복용 하였다

data=pd.read_excel(os.path.join(mydir,file),header=None,names=['particle','frame','x','y'],sheetname='Sheet3') 
    exits=data.groupby('particle', as_index=False).apply(lambda p: p.tail(1)) 
    exits=exits.groupby('particle', as_index=False).filter(lambda p: p.frame.values[0]<301) #find all particle exits. 301 is the last frame, so nothing will be joined after this 
    particles=exits['particle'].unique() #list of unique particles to check for links 
    entries=data.groupby('particle').apply(lambda p: p.iloc[0]) 
    entries=entries.groupby('particle',as_index=False).filter(lambda p: p.frame.values[0]>2) #find all entry points for particles. if it enters in the first frame, it won't be linked to anything prior 

    entries.sort_values('frame',inplace=True) # make sure the entries are in order, as we will stop after the closest match is found 
    for i in range (0,len(particles)): # loop through each particle exit 

     inddata=exits.iloc[i] # get current exit 

     subset_entries=entries[entries['frame'].values>inddata['frame']]# get list of particles that enter after this one exits 
     for j in range (0,subset_entries.shape[0]): # go through all entries 
      entry=subset_entries.iloc[j] # get current entry 
      msd=conversion**2*((entry['x']-inddata['x'])**2+(entry['y']-inddata['y'])**2) # calculate distance requirement 
      if msd<cutoff: # check if it is a match 
       droppart=entry['particle'] # particle must be removed from list of entries so we don't match it to some other particle later 
       entries=entries.drop(droppart) # drop the particle from entries 
       if len(exits[exits['particle']==droppart])>0: #if the entry particle that was just linked is in the list of exits, we have to update the particleid 
        id=exits[exits['particle']==droppart].index.labels[0][0] 
        exits.loc[id,'particle']=exits.iloc[i].particle # now any future exit has that particle number 
       ind=data[data['particle']==droppart].index # find location of linked particle in original dataframe 
       data.loc[ind,'particle']=exits.iloc[i].particle #link the particles together in the original dataframe 

       break # stop looking for matches to this particle 

. ,

exits.groupby('particle').apply(lambda p: find_entries(p,entries,conversion,cutoff)) 

def find_entries(particle,entries,conversion,cutoff):  
comp_entries=entries.groupby('particle').filter(lambda q: q.frame.values[0]>particle.frame.values[0]) 
comp_entries=comp_entries.groupby('particle').filter(lambda q: conversion**2*((q.x.values[0]-particle.x.values[0])**2+(q.y.values[0]-particle.y.values[0])**2)<cutoff) 
dist=comp_entries.groupby('particle').apply(lambda q: q.frame.values[0]-particle.frame.values[0]) 
if len(dist)>0: 
    min_particle=dist.argmin() 
    return min_particle 
else: 
    return NAN 

이 된 여러 번 느리게 모든 항목에 대해 계산되기 때문이 아니라 중지 : 나는 다음 출구를 통과, 주로 내가 무엇을하고 있었는지 모르고, 어떤 람다 함수와 일치하는 항목을 확인하려 일치하는 것을 찾은 후에 실제로 입자 당 일치하는 시간을 줄이기 위해 어쨌든 존재합니까? 나는 충분히 프로그래밍 할만큼 충분히 새롭다. 그런 것을 최적화하는 방법을 모른다. 또한 나쁜 코딩 형식 등의 작업이있는 경우 일반적인 팁을 주시면 감사하겠습니다.

Answer 1

데이터 프레임은 다른 종류의 계산에 효율적입니다. 여기에 필요한 것은 dict (연관 배열, 해시)입니다. 파이썬에서 데이터를 읽을 때 나는 다음과 같이 할 것이다 :

particles = {} 
for line in open(datafile): 
    particle,frame,x,y = line.split(delimiter) 
    success = False 
    for xcoord in range(x-1,x+2): 
     for ycoord in range(y-1,y+2): 
      #Try adding frame to existing location 
      try: 
       particle = particles[(xoord,ycoord)] 
       #Guess it exists 
       frames[particle].append((frame,xcoord,ycoord) 
       success = True 
       break 
      except KeyError: pass 
     if success: break 
    if not success: 
     particles[(x,y)] = particle 
     frames[particle] = [(frame,xcoord,ycoord)] 

이것은 편곡이다. 나는 그것을 짧은 것보다 더 읽기 쉽도록 만들려고 노력했다. 기존 파티클의 해시를 유지합니다. 각 파티클은 튜플 ​​(프레임, x, y) 목록에 연결됩니다. 이 방법을 읽으면 더 효율적이라고 생각합니다. 팬더가 필요한 경우 나중에 전송할 수 있습니다.