특정 장치 근처의 모든 장치를 찾을 수있는 방법으로 장치의 물리적 위치를 플로팅하려면 어떻게해야합니까?

Question

는 여기에 예제 레이아웃입니다 :

A 
B  C 

D 
    G F 
E 
      H 
K  I 
    J 

각 문자가 물리적 장치를 나타냅니다. 이 예에서는 A이 B 및 C 근처에 있다는 것을 알 수 있습니다. B은 A, D 및 가능하면 C에 모두 인접 해 있습니다.

저는 각 장치를 데이터베이스에 넣고 가능한 모든 관계를 쌍으로 생각했습니다. 예를 들어 :

device | siblings 
-------+--------- 
A  | B,C 
-------+--------- 
B  | A,D,C 
-------+--------- 
D  | B,G,E 

이 방법은, 내가 D에 가까운 장치를 찾아야 할 때 할 수있다 : 더 좋은 방법이 있다면 궁금 해서요

SELECT siblings FROM devices WHERE device = 'D'; 

siblings = siblings.split(',') 

for sibling in siblings: 
    # do something with each sibling device 

. 많은 수의 장치가있을 수 있다는 점을 감안할 때,이 방법은 지저분 해지고 가능성이있는 버그가 발생할 수 있다고 생각합니다 (형제 명단을 구분하여 명령을 추적하는 인간의 실수).

제안 사항?

Answer 1

더 많은 아이디어가 필요하면 Nearest-Neighbour Search에 대한 위키 피 디아 문서를 확인해야 할 것입니다. 그러나 가장 좋은 대답은 아마도 사용하려는 기기의 수에 달려있을 것입니다.

KD-Trees 및 R-Trees은 많은 수의 장치에서도 우수한 성능을 제공하지만, 프로그래밍/디버깅을 잘 수행해야합니다 (적어도 직접 작성해야합니다. 데이터 구조, 그래서 당신은 어딘가에 도서관을 찾을 수있을 것입니다).

작은 수의 장치 만 있으면 ("작은"것은 모든 종류의 것에 달려 있습니다.) 특수한 데이터 구조의 복잡성을 건너 뛰고 전체를 통해 선형 검색을 수행하는 것이 더 빠릅니다 귀하의 장치. 이와 같이 가끔씩 만 쿼리를 수행하는 경우 속도가 느린 선형 검색이 여전히 깨끗하고 직선적 인 코드를 가질 가치가 있습니다.

마지막으로 : 위의 모든 옵션은 모든 장치가 서로 "연결"되어 있다고 가정합니다. 일부 장치 만 서로 연결되어있는 경우 Adjacency List을 사용하여 연결을 저장하고 거리별로 정렬 된 상태로 유지하십시오. 위의 속도보다 빠릅니다.

희망이 도움이됩니다.