파이썬, 목록 2 개 목록 사이에 반복 하나의 목록에서 값이 다른의 값과 비슷한 경우보고 그들에게

Question

를 추출하는 나는 직교 좌표를 포함하는 목록이 목록을 가지고 : 나는 통해 반복 할

LBCoord = [[1195,456],[1324,674],[5644,687],[4679,654]] #very long list 
    CoreCoord = [[1145,466],[1524,644],[5664,657],[4479,654]] #very long list 

이 두 목록은 x (LBCoord [n] [0])과 y (LBCoord [n] [1])의 두 좌표 집합 중 하나가 사용자가 결정한 x와 y 범위에 속하는지 확인합니다.

가

가 LBCoord 포함

#user determined x and y ranges 
    xRange = 3 
    yRange = 5 
    LBCoord = [[1000,400],[1324,674],[5644,687],[4679,654]] #very long list 
    CoreCoord = [[1145,466],[1524,644],[5664,657],[997,395]] #very long 

즉 경우 (I은 X의 범위로 할 필요를 검색하고 좌표의 세트, 명확하고 LBCoord 및 CoreCoord 어떤 위치 내에서 서로 AY 범위) 좌표 [1000,400]과 CoreCoord는 [997,395]를 포함하고 있습니다. 프로그램이 xRange와 yRange에있는 좌표 세트를 인쇄하고 계속 실행하기를 원합니다.

중첩 된 for 루프를 사용해 보았지만 자이 썬 스크립트를 구현할 때 다루기가 어려웠으므로 문제가되는 좌표의 중복/순열을 꺼 냈습니다.

또 다른 문제는 Python 2.5 및 fiji와 호환되는 스크립트로 실행해야하므로 일부 가져온 도구가 작동하지 않습니다.

도움이 될 것입니다.

많은 감사,

벤

Answer 1

두 목록의 직교 제품을 통해 간단한 필터 당신이 원하는 것을 생산하는 것입니다하지만, 실행 시간을 용납 될 수 없다. 그와 함께 시작할 수 :

match_pairs = [] 
for current_lb_coord in LBCoord: 
    for current_core_coord in CoreCoord: 
     if abs(current_lb_coord[0] - current_core_coord[0]) <= xRange 
      and abs(current_lb_coord[1] - current_core_coord[1]) <= yRange: 
      match_pairs.append((current_lb_coord, current_core_coord)) 

이것은 LBCoord 1 및 CoreCoord초와 튜플들의 목록을 생성한다. 그러나 두 목록의 모든 쌍에 대해 비교를 수행해야하므로 실행하는 데 오랜 시간이 걸릴 수 있습니다. 따라서 복잡도는 O(m * n)입니다.

다음은 시도하고 최적화하는 것입니다. 두 필터가 실제로 있기 때문에 하나의 변형이 너무 크면 다른 하나가 좋은 일치인지는 중요하지 않습니다. 이 경우 두 목록을 x 좌표로 정렬 할 수 있습니다. 그런 다음 두 목록을 모두 조작하여 잘 겹치는 지점을 찾을 수 있습니다.

목록을 정렬하려면 O(n log n) 시간이 걸립니다. 일단 완료되면 두 목록을 한 번 병렬로 실행할 수 있어야합니다 (실제보다 약간 복잡합니다). 이렇게하면 다소 시간이 많이 걸릴 것입니다. 복잡성은 특정 항목에 대해 여러 개의 일치 항목을 가질 수 있다는 사실에서 비롯됩니다.

다음 코드에서 나는 x 좌표 만 중요하다고 가장 할 것입니다. 이 코드를 가져 와서 y 좌표를 포함하도록 향상시켜야합니다.

sorted_lb_coords = sorted(LBCoord) 
sorted_core_coords = sorted(CoreCoord) 
lb_index = core_index = 0 
match_pairs = [] 

while lb_index < len(sorted_lb_coords) and core_index < len(sorted_core_coords): 
    current_lb = sorted_lb_coords[lb_index] 
    current_core = sorted_core_coords[core_index] 

    # Remember I am only considering x 
    if abs(current_lb - current_core) < limit: 
     match_pairs.append((current_lb, current_core)) 

    # This part may also be more complex if you want all available matches. 
    # You could run through all the current_core entries till one was out 
    # of range and then reset the current_core index and increment the 
    # current_lb index. 
    if current_lb < current_core: 
     current_lb = current_lb + 1 
    else: 
     current_core = current_core + 1 

그래서이 예제가 크게 단순화, 그러나 희망 그것은 당신이 일치하는 개선 된 방법을 표시 할 수 있습니다 : 모두 목록을 정렬하고 운영의 기본 과정은 당신에게 좋은 속도 향상을 얻을 수 있습니다.

Answer 2

당신은 filter 및 zip 사용할 수 있습니다

이

>>> filter(lambda x : abs(x[0][0]-x[1][0])==145 and abs(x[0][3]-x[1][4])==66 , zip(LBCoord,CoreCoord)) 
[([1000, 400], [1145, 466])]