더 적은 수의 비교로 두 튜플 목록의 유클리드 거리를 비교하십시오.

Question

임계 값 4 인 두 튜플 목록의 유클리드 거리를 계산하려고합니다. 임계 값이 특정 값보다 작 으면 카운터를 증가시킵니다. 각 튜플은 점의 x, y, z 좌표입니다. 난 ..리스트 2와 목록 1의 비교의

X = [ (1,2,3),(2,3,4), (4,5,6) ] 
    Y = [ (1,2,2) , (3,4,5),(6,7,8) ] 
    from math import sqrt 
    dist_X = [ sqrt((p[0] - 0)**2 + (p[1] - 0)**2 + (p[2] - 0)**2) for p in X] 
    dist_Y = [ sqrt((p[0] - 0)**2 + (p[1] - 0)**2 + (p[2] - 0)**2) for p in Y] 
    for x in dist_X: 
    print (x , [ i for i,y in enumerate(dist_Y) if abs(x-y) <= 4]) 

내가 먼저 있도록 원점 (0,0,0)과 각 지점의 유클리드 거리를 계산하는 생각

을 낮출 수 어쨌든 지금 모두 목록 서로 가까이있는 점을 포함하지만 스칼라 값이기 때문에 작동하지 않습니다. 올바른 방향으로 가고 있습니까? 이것을 목록 1의 모든 요소에서 편집

visited1 = [ (1,2,3),(2,3,4), (4,5,6) ] 
    visited2 = [ (1,2,2) , (3,4,5),(6,7,8) ] 
    def euclidean(a,b): 
     return sqrt((a[0] - b[0])**2+(a[1]-b[1])**2+(a[2]-b[2])**2) 
    comparison = 0 
    for i,j in enumerate(visited2): 
    for k,l in enumerate(visited1): 
     if euclidean(visited2[i],visited1[k]) < 4: 
       count += 1 
     comparison += 1 

는리스트 2에있는 모든 요소와 비교 .. 난 내가 포인트 주어진 비교를 최소화 할 수있는 방법 (X, Y가 있는지 알고 싶어요 , z) 내가 가지고있는?

Answer 1

모양을 보려면 2D로 그립니다. 원점에서 대략 같은 거리에있는 점은 이 아니며이 서로 가깝습니다. 삼각형의 불균등이 뒤쪽에 있습니다. 예를 들어, 점 (0, 10), (0, 11) 및 (-8, -6)을 비교하십시오. 그들은 원산지에서 모두 10-11 유닛이지만, 마지막은 다른 두 근처에 없습니다.

두 점이 서로 가깝게 있는지 알고 싶으면 임의의 세 번째 점까지의 거리가 아니라 두 점 사이의 거리를 계산해야합니다. 문제는 복잡하지 않고 선형이 아닙니다.

Answer 2

때때로 일을 빠르게 할 수있는 사전 계산은 kd-trees입니다. 나는 무력에 대한 빠른 테스트를 실행하고 큰 목록에 대한 상당히 빠를 수 있다는 것을 발견 :

# n = 10 
# trees     0.08512560 ms 
# brute     0.01425540 ms 
# n = 100 
# trees     0.20338160 ms 
# brute     0.09876890 ms 
# n = 1000 
# trees     6.40193820 ms 
# brute    16.15429670 ms 
# n = 10000 
# trees    298.69653380 ms 
# brute    1393.71134270 ms 

코드 :

import numpy as np 
from scipy.spatial import cKDTree 

import types 
from timeit import timeit 

def setup_data(n, k): 
    data = {'d1': np.random.randint(0, 10, (n, 3)), 
      'd2': np.random.randint(0, 10, (n, 3)), 
      'mx': k} 
    return data 

def f_trees(d1, d2, mx): 
    t1 = cKDTree(d1) 
    t2 = cKDTree(d2) 
    return t1.count_neighbors(t2, mx) 

def f_brute(d1, d2, mx): 
    dist2 = np.add.outer(np.einsum('ij,ij->i', d1, d1), np.einsum('ij,ij->i', d2, d2)) - 2*np.einsum('ij, kj', d1, d2) 
    return np.count_nonzero(dist2 <= mx*mx) 



for n in (10, 100, 1000, 10000): 
    data = setup_data(n, 4) 
    ref = np.array(f_trees(**data)) 
    print(f'n = {n}') 
    for name, func in list(globals().items()): 
     if not name.startswith('f_') or not isinstance(func, types.FunctionType): 
      continue 
     try: 
      assert np.allclose(ref, func(**data)) 
      print("{:16s}{:16.8f} ms".format(name[2:], timeit(
       'f(**data)', globals={'f':func, 'data':data}, number=10)*100)) 
     except: 
      print("{:16s} apparently failed".format(name[2:]))