Tìm kiếm trong mảng có kích thước cao có các thuộc tính cụ thể

Question

Tôi có một mảng 3D trong đó các giá trị là đơn điệu. Cách tìm tất cả (x, y), | f (X, Y, Z) - v1 | < t.

Answer 1

Có các điểm Omega (n^2) có tọa độ tổng bằng n - 1. Không có gì được biết là ưu tiên về cách các giá trị của các điểm này so sánh với nhau, vì vậy, trong trường hợp xấu nhất, tất cả chúng phải là được kiểm tra. Một giới hạn trên phù hợp với các yếu tố không đổi được cung cấp bằng cách chạy thuật toán 2D trong mỗi lát liên tục-z.

Answer 2

Đối với mỗi giá trị, thực hiện các bước sau đây (ví dụ v1.):

1. Thực hiện các thuật toán 2D cho 4 khối đối mặt tiếp xúc với trục X (Y = 0, Y = n-1, Z = 0, Z = n-1). Lập chỉ mục tập hợp các ô kết hợp (X, Y, Z) theo X phối hợp cho bước tiếp theo.
2. Thực hiện thuật toán 2D cho tất cả n lát dọc theo trục X (X = 0..n-1), sử dụng kết quả của bước 1 để khởi tạo điểm ranh giới đầu tiên cho thuật toán 2D. Nếu không có ô nào phù hợp với tọa độ x đã cho, hãy chuyển sang lát tiếp theo trong thời gian không đổi.

Trường hợp phức tạp nhất sẽ là O (O (thuật toán 2D) * n).

Đối với nhiều giá trị (v2, v.v.) giữ bộ nhớ cache đánh giá chức năng và thực thi lại thuật toán cho từng giá trị. Đối với 100^3, một mảng dày đặc sẽ đủ.

Có thể hữu ích khi nghĩ về điều này như một thuật toán trích xuất isosurface, mặc dù ràng buộc đơn điệu của bạn giúp dễ dàng hơn.

Answer 3

Vì hàm không giảm, tôi nghĩ bạn có thể làm điều gì đó với tìm kiếm nhị phân.
Bên trong một véc tơ (x, 1, 1) (cột), bạn có thể thực hiện tìm kiếm nhị phân để tìm phạm vi phù hợp với yêu cầu của bạn sẽ là O(log(n)).
Để tìm các vectơ cột nào nhìn vào, bạn có thể thực hiện tìm kiếm nhị phân trên các vectơ (x, y, 1) (lát) chỉ kiểm tra điểm đầu tiên và cuối cùng để biết liệu giá trị có thể rơi vào chúng hay không sẽ mất một lần nữa O(log(n)).
Để biết những lát để tìm trong bạn có thể tìm kiếm nhị phân toàn bộ khối kiểm tra 4 điểm ((0, 0), (x, 0), (x, y), (0, y)) sẽ mất O(log(n)).
Vì vậy, tổng số, thuật toán sẽ mất log(z) + a * log(y) + b * log(x) trong đó a là số lượng các lát phù hợp và b là số cột phù hợp.
Đồng thời tính toán trường hợp xấu nhất là O(y * z * log(x)).

Answer 4

Nếu mảng 3d là đơn điệu không giảm trong mỗi chiều sau đó chúng ta biết rằng nếu

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

sau đó không có yếu tố của tiểu mảng f(x0...x1, y0...y1, z0...z1) có thể chứa bất kỳ điểm nào thú vị. Để xem này xem xét ví dụ rằng

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

giữ cho mỗi (x, y, z) của tiểu mảng, và một mối quan hệ tương tự tổ chức (với hướng đảo ngược) cho (x1, y1, z1). Do đó, f(x0, y0, z0) và f(x1, y1, z1) là giá trị tối thiểu và tối đa của mảng phụ, tương ứng.

Một cách tiếp cận tìm kiếm đơn giản sau đó có thể được thực hiện bằng cách sử dụng một chương trình phân đệ quy:

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; 
} 

Mã này về cơ bản chấp nhận một phụ mảng và chỉ đơn giản là bỏ qua việc tìm kiếm nếu các yếu tố thấp nhất là quá lớn hoặc các yếu tố cao nhất là quá nhỏ và chia mảng trong 8 hình khối con khác. Phép đệ quy kết thúc khi mảng phụ nhỏ (2x2x2 trở xuống) và quét toàn bộ được thực hiện trong trường hợp này.

Thử nghiệm với phương pháp này khá đơn giản, một mảng với các phần tử 100x200x300 được tạo bằng cách đặt phần tử f(i,j,k) thành max(f(i-1,j,k), f(i,j-1,k), f(i,j,k-1)) + random(100) có thể được tìm kiếm với giá trị trung bình và t = 1 chỉ kiểm tra khoảng 3%. tìm thấy phần tử trong phạm vi).

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%)