C++ - 루프

Question

나는 형식으로 입력 파일을 기대하는 C++ 프로그램을하지 않고 희소 행렬 값을 찾는 :

X Y Z 
1 1 .642 
1.1 1 .482 
1.2 1 .394 
1.3 1 .420 
1.4 1 .948 

텍스트 파일이 매우 긴 - 약 20,000 라인 정도. 이제는 모든 (X, Y) 쌍에 대해 Z 검색을 수행하기 위해 이것을 C++ 프로그램에서 읽어야합니다. (X, Y) 쌍이 입력 파일의 어떤 것과 정확히 같지 않으면 가장 가까운 X와 가장 가까운 Y 값을 사용해야합니다. 0이 아닌 값 대신 전체 행렬을 사용하면 X와 Y 좌표가 균등하게 배치됩니다.

제 문제는이를 수행하는 가장 빠른 방법을 결정하는 것입니다. 가장 가까운 X에 대한 벡터를 검색 한 다음 가장 가까운 Y에 대한 벡터를 검색하는 것을 피하고 싶습니다. 반복 및 검색하지 않고이를 수행 할 수있는 방법이 있습니까? 값을 검색하기 위해 일종의 해시 테이블을 사용할 수 있습니까?

나는 스크립팅 녀석이고 C++ 초보자이기 때문에 사소한 것 같아 사과드립니다. 참조를 위해 내가 빠른 방법이 필요합니다 이렇게하려면 :

lookup(1.1,1) 
    >>> .482 

lookup(1.112, 1) 
    >>> .482 // value corresponding to closest x and closest y 

lookup(0,0) 
    >>> .642 // value corresponding to closest x and closest y 

내가 예를 들어, 전체 행렬이 있다면이 직접 가능하다 :

에 관한 Z 값을 찾기 위해

1.1 1.2 1.3 1.4 1.5 
1.1 
1.3 
1.5  (Z values) 
1.7 
1.9 

(1.5 , 1.2) 인덱스 [1.5/(x_spacing), 1.2/(y_spacing)]에있는 Z 값을 간단히 반환 할 수 있습니다.

허용이 띄어쓰기로 내 조회 값을 빼고 정확한 (X, Y) 쌍이없는 경우 둥글게해야합니다. 그러나 결론적으로 검색을 수행하지 않고도 적절한 Z 값을 얻을 수 있습니다. 거대한 풀 매트릭스가 필요로하는 모든 공간을 차지하지 않고 같은 것을 달성하고 싶습니다. 그래서 텍스트 파일에는 0이 아닌 Z 값에 해당하는 쌍만 포함됩니다.

제공 할 수있는 도움이 있으면 크게 감사하겠습니다.

Answer 1

구조화 된 트리에 저장하는 것이 좋습니다. 예를 들어 쿼드 트리. 그것은 공간 절약을위한 스파 스 스토리지되며 그것은 또한 가장 가까운 지점을 검색하는 것은 매우 쉽습니다.

C++의 쿼드 트리에 대한 자습서는 here입니다.