Ricerca in array con dimensioni elevate con proprietà specifiche

Question

Ho una matrice 3D in cui i valori sono monotoni. Come trovare tutti (x, y), | f (X, Y, Z) - v1 | < t.

Answer 1

Ci sono punti Omega (n^2) le cui coordinate sono pari a n - 1. Nulla è noto a priori su come i valori di questi punti si confrontino, quindi, nel peggiore dei casi, devono essere tutti ispezionato. Un limite superiore che corrisponde a fattori costanti viene fornito eseguendo l'algoritmo 2D in ogni slice z costante.

Answer 2

Per ogni valore, eseguire le seguenti operazioni (es v1.):

1. Eseguire l'algoritmo 2D per 4 cubo affaccia tangente all'asse X (Y = 0, Y = n-1, Z = 0, Z = n-1). Indicizza il set risultante di celle corrispondenti (X, Y, Z) per coordinate X per il passaggio successivo.
2. Eseguire l'algoritmo 2D per tutte le n fette lungo l'asse X (X = 0..n-1), utilizzando il risultato del passaggio 1 per inizializzare il primo punto di delimitazione dell'algoritmo 2D. Se non ci sono celle corrispondenti per la coordinata x data, passare alla slice successiva in tempo costante.

La complessità del caso peggiore sarà O (O (algoritmo 2D) * n).

Per valori multipli (v2, ecc.) Mantenere una cache delle valutazioni delle funzioni e rieseguire l'algoritmo per ciascun valore. Per 100^3, una matrice densa sarebbe sufficiente.

Potrebbe essere utile considerarlo come un algoritmo di estrazione di isosurface, sebbene il vincolo di monotonicità lo renda più semplice.

Answer 3

Poiché la funzione non è decrescente, penso che si possa fare qualcosa con le ricerche binarie.
All'interno di un vettore (x, 1, 1) (colonna) è possibile eseguire una ricerca binaria per trovare l'intervallo corrispondente alla propria richiesta che sarebbe O(log(n)).
Per trovare i vettori di colonne da esaminare, è possibile eseguire una ricerca binaria su vettori (x, y, 1) (sezioni) che controllano solo il primo e l'ultimo punto per sapere se il valore può ricadere in essi e che sarà nuovamente pari a O(log(n)).
Per sapere quali sezioni cercare, è possibile eseguire una ricerca binaria su tutto il cubo controllando i 4 punti ((0, 0), (x, 0), (x, y), (0, y)) che richiederebbero lo O(log(n)).
Quindi, in totale, l'algoritmo impiegherà log(z) + a * log(y) + b * log(x) dove a è il numero di sezioni corrispondenti e b è il numero di colonne corrispondenti.
Il calcolo ingenuo del caso peggiore è O(y * z * log(x)).

Answer 4

Se la matrice 3d è monotona non decrescente in ogni dimensione allora sappiamo che se

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

quindi nessun elemento del sub-array f(x0...x1, y0...y1, z0...z1) può contenere qualsiasi punto interessante. Per vedere questo consideri ad esempio che

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

vale per ogni (x, y, z) del sub-array, e una relazione simile vale (con direzione inversa) per (x1, y1, z1). Pertanto, f(x0, y0, z0) e f(x1, y1, z1) rappresentano rispettivamente il valore minimo e massimo dell'array secondario.

Un semplice metodo di ricerca che possono essere attuati utilizzando uno schema di suddivisione ricorsivo:

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

Il codice accetta fondamentalmente un sub-array e semplicemente ignora la ricerca se l'elemento più basso è troppo grande o l'elemento più alto è troppo piccolo e divide l'array in 8 sub-cubi altrimenti. La ricorsione termina quando l'array secondario è piccolo (2x2x2 o meno) e in questo caso viene eseguita una scansione completa.

Sperimentalmente ho trovato che con questo abbastanza semplice approccio un array con 100x200x300 elementi generati modificando elemento f(i,j,k) a max(f(i-1,j,k), f(i,j-1,k), f(i,j,k-1)) + random(100) può essere ricercato il valore medio e t = 1, verifica solo circa il 3% degli elementi (25 elementi controllati per ciascun elemento trovato nel raggio d'azione).

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