다차원 "볼륨 대여"스케줄러에 대한 데이터 구조 및 알고리즘

Question

추상 문제. 세상이 큐브의 모든 차원을 따라 여러 개의 입방체 셀로 만들어진 큐브라고 상상해보십시오.

이제 일정 기간 동안 특정 볼륨을 임대 할 수 있다고 가정합니다. 예를 들어, 2012 년의 좌표 [1, 1, 1]을 3x3x3 볼륨에 [3, 3, 3]

이제 [1, 2, 2] 좌표로 [2, 2, 1] 좌표의 2x2x2 볼륨을 [5,2,2]에 임대 할 수 있습니다. 임대 한 볼륨을 임대 할 수 있다고 상상해보십시오. 그들을 인수했다. 예를 들어 위에서 정의한대로 볼륨을 대여 한 경우 Q1'2012에 [5, 2, 1] 좌표의 [5,1]에서 5x2x1 셀 볼륨을 출력합니다. 그런 다음 일년 내내 셀 [5, 2, 2]을 밖으로 나가십시오.

여러 개의 "계약서"에서 동일한 볼륨을 임대 할 수 있으며 여러 개의 "계약서"에서도 내보낼 수 있습니다.

문제는 - 어떤 데이터 구조와 알고리즘은 같은 질문에 대답하는 데 사용할 수 있습니다

• 가 언제가 특정 세포를하도록 할 수 있습니까?
• 특정 기간에 어떤 세포를 내보낼 수 있습니까?
• 모든 측정 기준을 포함하지 않고 특정 좌표의 셀을 내보낼 수 있습니까 (예 : 누군가 2012 년에 2와 4 사이의 좌표 X를 가진 셀을 대여하려고합니다.)?

브 루트 포스 방식 (모든 조합을 확인해보십시오)은 문제가되지 않습니다. 이 작업이 필요로하는 데이터 세트는 5 차원이며 (더 많은 차원이 곧 출시 될 예정 임) 치수는 평균 100-200 개입니다.

Answer 1

시간을 다른 차원으로 처리하면 설명하는 내용이 n 차원 공간의 개체 컬렉션에 대해 원하는 것으로 예상되는 쿼리 종류처럼 보입니다.

나에게 http://en.wikipedia.org/wiki/K-d_tree 또는 아마도 n 차원 버전 http://en.wikipedia.org/wiki/Octree과 같은 것을 제안합니다. 물론 캐치 (catch)는 차원의 수가 증가함에 따라 이러한 데이터 구조가 스팀에서 벗어나는 것입니다.

모든 셀을 검사하는 무차별 방식을 배제합니다. 또한 n 차원 공간에있는 각 알려진 객체에 대해 각 쿼리를 확인하는 무차별 대입 방식을 배제해야합니까? 모든 것이 축으로 정렬 된 n 차원 직사각형이기 때문에 쿼리와 객체의 교차점을 검사하는 것이 어렵지 않을 수 있습니다. 문제를 데이터베이스에 던져 시도하는 경우 문제가 발생할 수 있습니다. 쿼리 패키지 또는 일부 매우 높은 수준의 언어 - 데이터베이스 전체 테이블 스캔.

Answer 2

mcdowella가 지적했듯이 Octree와 kd 나무는 크기가 4 또는 5를 초과하여 증가함에 따라 효율성이 떨어집니다. 치수가 무엇인지에 대해 언급하지 않았으므로이 특성이 개체의 속성이라고 가정합니다. 너는 말하고있다. 그냥 RDBMS에 넣고이 필드에 인덱스를 사용하십시오. 좋은 구현은 다중 인덱스 항목에 대한 쿼리를 수행하는 좋은 성능을 가질 수 있습니다.

크기에 2 진 값 (또는 작은 enum)이 있으면 다른 것이 더 나을 수 있습니다.