파이썬에서 교환 시간을 찾는 가장 빠른 방법

Question

나는 두 가지 목록을 가지고 있습니다. list1의 각 포인트부터 list2에서 가장 가까운 후속 (더 큰) 시간을 찾고 싶습니다.

목록 1 = [280, 290]

리스트 2 = [282, 295]

교환 (리스트 1,리스트 2) = 2, 5]

I : 예

이 일을 빨리 처리하는 데 어려움이 있습니다. 내가 생각할 수있는 유일한 방법은 list1의 각 요소를 반복하고 list1 요소보다 큰 목록 y에서 첫 번째 히트를 취하는 것입니다 (목록이 정렬 됨). 아래 내 두 개의 시도를 한 팬더, 한/w 팬더 O :

나는 np.searchsorted과 솔루션 제안

# dictionary containing my two lists 
transition_trj = {'ALA19': [270.0, 280.0, 320.0, 330.0, 440.0, 450.0, 
470.0], 'ALA88': [275.0, 285.0, 325.0, 333.0, 445.0, 455.0, 478.0]} 
# for example, exchange times for ('ALA19','ALA88') = [5.0, 5.0, 5.0, 3.0, 5.0, 5.0, 8.0] 
#find all possible combinations 
names = list(transition_trj.keys()) 
import itertools 
name_pairs = list(itertools.combinations_with_replacement(names, 2)) 

# non-pandas loop, takes 1.59 s 

def exchange(Xk,Yk): # for example, a = 'phiALA18', b = 'phiARG11' 
    Xv = transition_trj[Xk] 
    Yv = transition_trj[Yk] 
    pair = tuple([Xk,Yk]) 
    XY_exchange = [] # one for each pair 
    for x in range(len(Yv)-1): # over all transitions in Y 
     ypoint = Yv[x] # y point 
     greater_xpoints = [] 
     for mini in Xv: 
      if mini > ypoint: 
       greater_xpoints.append(mini) # first hit=minimum in sorted list 
       break 
     if len(greater_xpoints) > 0: 
      exchange = greater_xpoints[0] - ypoint 
      XY_exchange.append(exchange) 
    ET = sum(XY_exchange) * (1/observation_t) 
    return pair, ET 




# pandas loop, does same thing, takes 11.58 s...I am new to pandas... 
import pandas as pd 
df = pd.DataFrame(data=transition_trj) 

def exchange(dihx, dihy): 
    pair = tuple([dihx, dihy]) 
    exchange_times = [] 
    for x in range(df.__len__()): 
     xpoint = df.loc[x, dihx] 
     for y in range(df.__len__()): 
      ypoint = df.loc[y, dihy] 
      if ypoint > xpoint: 
       exchange = ypoint - xpoint 
       exchange_times.append(exchange) 
       break 
    ET = sum(exchange_times) * (1/observation_t) 
    return pair, ET 


# here's where I call the def, just for context. 
exchange_times = {} 
for nm in name_pairs: 
    pair, ET = exchange(nm[0],nm[1]) 
    exchange_times[pair] = ET 
    if nm[0] != nm[1]: 
     pair2, ET2 = exchange(nm[1], nm[0]) 
     exchange_times[pair2] = ET2 

Answer 1

타에서 목록의 느릅 나무를 찾기 삽입 점 (NumPy와는 팬더 골격이다). 그것은 각 루프에서 시작 (for mini in Xv:)부터 최소값을 검색하므로 O(N²) 일 때 O(N ln (N)) 솔루션입니다.

이 예제는 사용자의 작업에 영향을 미치지 만 두 목록의 길이가 같지 않거나 인터리브가 적절하지 않은 경우 원하는 내용을 알 수 없습니다. 그럼에도 불구하고 길이가 같으면 해결책이 제시됩니다.

대신 [POS]의 .reindex 사용하려는 사용자를위한

df=pd.DataFrame(transition_trj) 
pos=np.searchsorted(df['ALA88'],df['ALA19']) 
print(df['ALA88'][pos].reset_index(drop=True)-df['ALA19']) 

# 0 5.0 
# 1 5.0 
# 2 5.0 
# 3 3.0 
# 4 5.0 
# 5 5.0 
# 6 8.0 
# dtype: float64