거대한 2 차원 배열에 대한 검색 알고리즘이 있습니까?

Question

이것은 실제 질문이 아니며 단지 이론만으로 만들어집니다.

나는 [1,140,245,123443] 같은 요소로 구성되어 큰 배열, 모든 정수가 또는 낮은 선택도 함께 수레, 그리고 고유 값의 수는 배열의 크기보다 10 배 이하입니다. B * tree 인덱싱은이 경우 좋지 않습니다.

비트 맵 인덱싱을 구현하려고했지만 Ruby에서 이진 연산이 너무 빠르지 않습니다.

고정 크기 벡터의 2 차원 배열 검색에 적합한 알고리즘이 있습니까?

그리고, 주요 질문은 내가 변환 기능은 단순이어야 값의 벡터로 변환 할 방법입니다, 그래서 같은 범위 쿼리를 적용 할 수 있습니다

(v[0]<10, v[2]>100, v[3]=32, 0.67*10^-8<v[4]<1.2154241410*10^-6) 

내가 가지고있는 유일한 아이디어를 벡터 ... 바이너리 검색과 병합의 각 구성 요소에 대해 별도의 정렬 된 인덱스를 만드는 것이지만 최악의 시나리오에서는 O (N * N) 작업이 필요하기 때문에 나쁜 생각입니다 ...

Answer 1

색인 사용 :

기본 아이디어는 2 차원을 (원래 위치를 유지하면서) 1 차원 배열로 변환하고 나중에 이진 검색을 적용합니다.

이 방법은 모든 n 차원 배열에서 작동하며 가변 길이의 n 차원 배열로 볼 수있는 데이터베이스에서 널리 사용됩니다.

Answer 2

각 "열"이 알려진 범위에 모호하게 분포되어 있다고 가정하면 각 열에 대한 일련의 버킷과 버킷을 충족시키는 행 목록을 추적 할 수 있습니다. 각 열의 버킷 수는 동일하거나 다를 수 있습니다. 이는 전적으로 임의적입니다. 버킷이 더 빠르지 만 약간 더 메모리가 필요합니다. 그런 다음

my table: 
range: {1to10} {1to4m} {-2mto2m} 
row1:  {7  3427438335 420645075} 
row2:  {5  3862506151 -1555396554} 
row3:  {1  2793453667 -1743457796} 

buckets for column 1: 
bucket{1-3} : row3 
bucket{4-6} : row2 
bucket{7-10} : row1 

buckets for column 2: 
bucket{1-2m} : 
bucket{2m-4m} : row1, row2, row4 

buckets for column 3: 
bucket{-2m--1m} : row2, row3 
bucket{-1m-0} : 
bucket{0-1m} : 
bucket{1m-2m} : row1 

, 일련의 기준 제공 : {v[0]<=5, v[2]>3*10^10}, 우리는 그 기준에 일치하는 것을 버킷를 꺼내 : 우리가 알고있는 지금

column 1: 
v[0]<=5 matches buckets {1-3} and {4-6}, which is rows 2 and 3. 
column 2: 
v[2]>3*10^10} matches buckets {2m-4m} and {4-6}, which is rows 1, 2 and 3. 
column 3: 
"" matches all , which is rows 1, 2 and 3. 

을 우리가 찾고있는 행 (들) 세 가지 기준을 모두 충족하므로 버킷에있는 모든 행을 나열합니다.이 경우 2와 3 행의 모든 ​​기준과 일치합니다.이 시점에서 잔량 행은 대용량 인 경우에도 작을 것입니다. 데이터, 버킷의 세분성에 따라 달라집니다. 이 시점에 남아있는 각 행을 점검하여 일치하는지 확인하십시오. 이 샘플에서 행 2는 일치하지만 행 3은 일치하지 않습니다.

이 알고리즘은 기술적으로 O는 작은 버킷의 수가 많은 경우 (N), 그러나 실제로,이 알고리즘이 될 수 매우 빠르게.