効率的なパーティクルリンクアルゴリズム

Question

私は時間の経過とともに様々なパーティクルのXY位置を持つファイルがたくさんあります。私は粒子を通過しようとしているし、いくつかの距離の基準を満たすことに基づいて一緒に結合する必要があるかどうかを確認しています。私はプログラミングに非常に新しいです、そして、これまでに試したことはすべて、本当に遅いです。私はこのデータをすべてパンダのデータフレームに保存しています。したがって、たとえば、私が持っているかもしれません：

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 

、それがなりたい：

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 

粒子は、いくつかのフレームが失われたにも関わらず、同じ場所で、基本的なので。実際のデータフレームには数百〜数千の粒子が含まれている可能性があります。

Iは、まず、各粒子の最後のフレームをループし、そのループ内で、他のすべての粒子の最初のフレームをループ単に試み：

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 

これは30分のファイルに取りました。私は、主に私が何をしているのかを知らない、終了を通過し、いくつかのラムダ関数と一致するエントリををチェックしてみました：

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（連想配列、ハッシュ）だと思います。私はPythonでデータを読むとき、私は次のような何かをするでしょう：

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）のリストに接続します。このように読んで私はより効率的だと思います。パンダが必要な場合は、後に転送することができます。