min veloce su arco

Question

Dato un elenco di array e un sacco di tempo di configurazione ho bisogno di trovare rapidamente il valore più piccolo in alcuni sub-arco di ogni matrice. Nel concetto:

class SpanThing
{
     int Data;
     SpanThing(int[][] data) /// must be rectangulare
     {
         Data = data;
         //// process, can take a while
     }

     int[] MinsBruteForce(int from, int to)
     {
         int[] result = new int[data.length];
         foreach(int index, int[] dat; Data)
         {
             result[i] = int.max;
             foreach(int v; dat[from .. to]);
                result[i] = min(result[i], v);
         }
         return result;
     }
     int[] MinsSmart(int from, int to)
     {
          // same as MinsBruteForce but faster
     }
}

Il mio pensiero attuale su come farlo sarebbe quello di costruire un albero binario sui dati in cui ogni nodo contiene il minimo nel giro correlati. In questo modo trovare il minimo nel giro di una fila consisterebbe di trovare il minimo di soli i nodi della struttura che lo compongono. Questo insieme sarebbe la stessa per ogni riga così potrebbe essere calcolata una volta.

Se uno vede eventuali problemi con questa idea o noto di modi migliori?

---

Per chiarire bambino, l'albero di cui sto parlando verrebbe istituito Sutch che il nodo principale conterrebbe il valore minimo per l'intera riga e per ogni nodo, è lasciato avrebbe il valore minimo per la metà sinistra del arco dei genitori e lo stesso per il diritto.

 0   5   6  2   7   9   4   1   7   2   8   4   2
 ------------------------------------------------
   | 5 | 6|   | 7 | 9 |   | 1 | 7 | 2 | 8 | 4 | 2  
 0 |   5  | 2 |   7   | 4 |   1   |   2   |   2  
   0      |   2       |   1       |       2
          0           |           1
                      0

Questo albero può essere mappato a un array e definito in modo tale che i limiti di segmento possono essere calcolati con conseguente rapido look-up.

Il caso sto ottimizzazione per è dove ho impostato e un sacco di tempo davanti a un ingresso fisso, ma poi bisogno di fare molti test rapidi su una veriety di campate.

Answer 1

La soluzione proposta sembra dare la risposta utilizzando sovraccarico costante spazio, messa a punto costante di tempo, e il tempo logaritmico per le query. Se siete disposti a pagare lo spazio quadratica (vale a dire, calcolare tutti gli intervalli di anticipo) è possibile ottenere risposte in tempo costante. Il tuo schema logaritmica è quasi certo di essere preferito.

Non mi sorprenderebbe se fosse possibile fare di meglio, ma sarei scioccato se ci fosse un semplice struttura dati che potrebbero fare meglio --- e, in pratica, tempo logaritmico è quasi sempre un sacco abbastanza veloce. Andare per esso.

Answer 2

Il tuo approccio descritto suona come si sta cercando di fare una sorta di Memoizzazione o caching , ma che è solo andando per aiutarti se si sta controllando gli stessi campate o campate nidificati ripetutamente.

Il caso generale per min ([0..n]) sta per essere O (n) , che è quello che hai già.

Il tuo codice sembra preoccuparsi di più sui numeri reali della matrice di quanto il loro ordine nella matrice. Se avete intenzione di essere il check ripetutamente queste campate, è possibile ordinare solo i dati prima, che potrebbe essere un singolo O (n log n) operazione seguita da un gruppo di O (1) ops? La maggior parte delle lingue hanno una sorta di costruito in algoritmo di ordinamento nelle loro librerie standard.

Answer 3

Non è chiaro come si possa rappresentare la gerarchia di intervalli efficiente utilizzando l'approccio dell'albero che hai descritto. Ci sono molti modi per dividere un intervallo --- dobbiamo prendere in considerazione tutte le possibilità?

Sarebbe un approccio semplice come questo basti: data Supponiamo è una matrice N x M. Vorrei creare un M x M x N array in cui l'ingresso (i,j,k) dà il "minimo" di data(k,i:j). Le voci di matrice verranno popolati su richiesta:

int[] getMins(int from, int to)
{
    assert to >= from;

    if (mins[from][to] == null)
    {
        mins[from][to] = new int[N];

        // populate all entries (from,:,:)
        for (int k = 0; k < N; k++)
        {
            int t = array[k][from];

            for (int j = from; j < M; j++)
            {
                if (array[k][j] < t)
                    t = array[k][j];

                mins[from][j][k] = t;
            }
        }
    }

    return mins[from][to];
}