2
동일한 1 차원 (선형) 공간에 해당하는 두 세트의 간격. 여기에 대략적인 비주얼이 있습니다. 실제로는 더 많은 간격이 있고 훨씬 더 넓어 지지만 기본적인 아이디어가 있습니다. 이 간격의1 차원 공간을 분할하는 알고리즘
각각의 정보를 포함하고 나는 다른 세트 (파란색)에 포함 된 정보에 간격 (빨간색) 한 세트의 정보를 비교하는 프로그램을 쓰고 있어요.
여기 내 문제입니다. 나는 그 공간을 각각의 청크에서 수행 할 비교 작업의 대략 동일한 양 (작업량은 공간의 해당 부분의 간격 수에 따라 다름)으로 n 덩어리로 분할하고 싶습니다. 또한 파티션은 두 청크에서 빨간색 또는 파란색 간격을 분리해서는 안됩니다.
그래서 입력 간격의 두 세트, 그리고 원하는 출력- 간격은 대략적으로 동일하게 분할
- 없는 구간의 각 요소에 분산되도록 상기 공간의 파티션 여러 파티션 요소와 겹치다
누구든지이 작업을 수행하는 방법이나 알고리즘을 제안 할 수 있습니까?
@ 대니얼 : 비교 목록을 작성하기 위해 비교를 시작하기 전에 한 번 전체 공간을 스캔하는 것이 비용이 많이 듭니까? 또한, 같은 수의 빨간색과 파란색 간격을 보장합니까? 간격 (예 : 헤더 또는 무언가에 인코딩 된 일련 번호)을 검사하여 간격의 순서를 식별 할 수있는 방법이 있습니까? –
동일한 수의 간격이 없을 것입니다. 선형 공간의 빠른 초기 스캔은 아마도 필요할 것이고 비싸지 않을 것입니다. 필요한 경우 여러 데이터 구조에 "간격"객체 (시작 및 끝 좌표가있는 객체)에 대한 포인터를 저장할 수 있지만 그 이상을 저장하는 것은 너무 많은 메모리를 필요로합니다. 간격 트리와 동적 배열이 먼저 마음에 떠오 랐지 만, 어떻게 사용할 수 있는지 알아 내려고 노력 중입니다 ... –
@Daniel - 뭔가 빠졌거나 그냥 포인터 쌍 목록을 만들 수 없습니까? 빠른 스캔을 한 다음 처리를 위해 해당 목록을 분할 하시겠습니까? –