특정 속성을 가진 높은 차원의 배열로 검색

Question

값이 단조로운 3D 배열이 있습니다. 모든 (x, y), f (X, Y, Z)를 찾는 법 - v1 | < t.

Answer 1

좌표가 n - 1 인 합계가 오메가 (n^2) 점입니다. 이러한 점의 값이 어떻게 서로 다른지에 대한 선험적 인 지식은 없으므로, 최악의 경우 모두가 검사했다. 상수 요소와 일치하는 상한은 각 상수 -Z 슬라이스에서 2D 알고리즘을 실행하여 제공됩니다. 각 값

Answer 2

다음 단계를 실행 (예 v1.)

1. 4 큐브 차원 알고리즘이 X 축 (Y = 0에 접하는 대향 실행 Y = N-1, Z = 0, Z = n-1). 다음 단계에서 일치하는 (X, Y, Z) 셀의 결과 집합을 X 좌표로 인덱싱합니다.
2. 1 단계의 결과를 사용하여 2D 알고리즘의 첫 번째 경계 지점을 초기화하여 X 축 (X = 0..n-1)을 따라 모든 n 조각에 대해 2D 알고리즘을 실행합니다. 주어진 x 좌표에 일치하는 셀이 없으면 일정 시간 내에 다음 슬라이스로 이동합니다.

최악의 경우의 복잡도는 O (O (2D 알고리즘) * n)입니다.

값이 여러 개인 경우 (v2 등) 함수 평가 캐시를 유지하고 각 값에 대해 알고리즘을 다시 실행하십시오. 100^3의 경우, 조밀 한 배열이면 충분합니다.

단조 로움 제약 조건을 사용하면 쉽게 등고선 추출 알고리즘으로 생각하는 것이 유용 할 수 있습니다.

Answer 3

이 함수는 감소하지 않으므로 바이너리 검색으로 뭔가를 할 수 있다고 생각합니다.
(x, 1, 1) (열) 벡터 내부에서 이진 검색을 수행하여 요구 사항과 일치하는 범위를 찾을 수 있습니다 (O(log(n))).
어떤 열 벡터를 찾으려면 (x, y, 1) (조각) 벡터를 통해 이진 검색을 수행하면 첫 번째 점과 마지막 점만 확인하여 그 값이 속할 수 있는지 다시 확인하면 O(log(n))이 다시 나타납니다.
어떤 조각을 보는지 알아 보려면 O(log(n))이 걸릴 4 점 ((0, 0), (x, 0), (x, y), (0, y))을 확인하면서 전체 큐브를 이진 검색 할 수 있습니다.
총 알고리즘은 log(z) + a * log(y) + b * log(x)입니다. 여기서 a은 일치하는 슬라이스의 수이고 b은 일치하는 열의 수입니다.
최악의 경우를 순진하게 계산하면 O(y * z * log(x))입니다. 3 차원 배열 단조 경우

Answer 4

각 차원에서 비 감소 우리는

f(x0, y0, z0) < v1 - t 
      or 
f(x1, y1, z1) > v1 + t 

다음 하위 배열 f(x0...x1, y0...y1, z0...z1)의 어떤 요소가 흥미로운 지점을 포함 할 수 있습니다 경우에 것을 알고있다. (x1, y1, z1)위한

f(x0, y0, z0) <= f(x, y0, z0) <= f(x, y, z0) <= f(x, y, z) 

가 서브 어레이의 각 (x, y, z) 위해 보유하고 유사한 관계 (반대 방향)이 보관 유지하는 예를 들면 볼을 고려한다. 따라서 f(x0, y0, z0) 및 f(x1, y1, z1)은 각각 서브 어레이의 최소 및 최대 값입니다.

template<typename T, typename CBack> 
int values(Mat3<T>& data, T v0, T v1, CBack cback, 
      int x0, int y0, int z0, int x1, int y1, int z1) { 
    int count = 0; 
    if (x1 - x0 <= 2 && y1 - y0 <= 2 && z1 - z0 <= 2) { 
     // Small block (1-8 cells), just scan it 
     for (int x=x0; x<x1; x++) { 
      for (int y=y0; y<y1; y++) { 
       for (int z=z0; z<z1; z++) { 
        T v = data(x, y, z); 
        if (v >= v0 && v <= v1) cback(x, y, z); 
        count += 1; 
       } 
      } 
     } 
    } else { 
     T va = data(x0, y0, z0), vb = data(x1-1, y1-1, z1-1); 
     count += 2; 
     if (vb >= v0 && va <= v1) { 
      int x[] = {x0, (x0 + x1) >> 1, x1}; 
      int y[] = {y0, (y0 + y1) >> 1, y1}; 
      int z[] = {z0, (z0 + z1) >> 1, z1}; 
      for (int ix=0; ix<2; ix++) { 
       for (int iy=0; iy<2; iy++) { 
        for (int iz=0; iz<2; iz++) { 
         count += values<T, CBack>(data, v0, v1, cback, 
                x[ix], y[iy], z[iz], 
                x[ix+1], y[iy+1], z[iz+1]); 
        } 
       } 
      } 
     } 
    } 
    return count; 
} 

코드는 기본적으로 서브 어레이를 받아 단순히 최저 요소가 너무 큰 경우, 탐색 또는 높은 소자를 스킵 :

간단한 검색 방법

는 재귀 세분 기법을 이용하여 구현 될 수있다 배열이 너무 작아서 배열을 8 개의 하위 큐브로 분할합니다. 이 재귀는 서브 어레이가 작고 (2x2x2 이하)이 경우 전체 스캔이 수행 될 때 종료됩니다.

실험적으로이 간단한 접근법을 사용하면 f(i,j,k)을 으로 설정하여 생성 된 100x200x300 요소가있는 배열은 중간 값을 검색 할 수 있으며 t = 1은 요소의 약 3 % 만 검사 할 수 있습니다 요소가 범위 내에 있음).

Data 100x200x300 = 6000000 elements, range [83, 48946] 
Looking for [24594-1=24593, 24594+1=24595] 
Result size = 6850 (5.4 ms) 
Full scan = 6850 (131.3 ms) 
Search count = 171391 (25.021x, 2.857%)