Una struttura dati 2D ottimale

Question

Ho pensato molto a questo, ma non sono stato in grado di inventare qualcosa.

Supponiamo che io voglia raccogliere X elementi di ordinabili da qualsiasi colonna e qualsiasi riga in O (m * n), e anche la possibilità di inserire o eliminare una riga in O (m + n) o meno .. . È possibile?

Quello che mi è venuto in mente è una griglia collegata, dove i nodi sono inseriti in un vettore, quindi ho indici per loro, e indicizzato la prima riga e colonna per rimuovere la necessità di attraversare l'elenco in qualsiasi direzione. con il mio metodo ho raggiunto la complessità di cui sopra, ma mi chiedevo solo se fosse possibile ridurlo ulteriormente con un fattore non costante.

Esempio per sortability:

1 100 25 34 
2 20 15 16 
3 165 1 27 

Ordinati per 3a fila:

25 1 34 100 
15 2 16 20 
1 3 27 165 

ordinamento che dal 1 ° colonna:

1 3 27 165 
15 2 16 20 
25 1 34 100 

Answer 1

Vorrei creare due matrici di indice, una per le colonne e una per le righe. Così, per i dati

1 100 25 34 
2 20 15 16 
3 165 1 27 

Si creano due matrici:

• cols = [0, 1, 2, 3]
• rows = [0, 1, 2]

Poi, quando si desidera ordinare la matrice dalla 3 ° fila, si mantiene l'originale matrice intatta, ma basta modificare l'array di indici di conseguenza:

• cols = [2, 0, 3, 1]
• rows = [0, 1, 2]

Il trucco ora è quello di accedere al tuo matrice con un riferimento indiretto. Quindi, invece di accedervi con m[x][y] si accede a esso da m[cols[x]][rows[y]]. Devi anche usare m [cols [x]] [rows [y]] quando esegui il riordino dell'array rows/cols.

Questo ordinamento è O(n*log(n)) e l'accesso è O(1).

Per la struttura dei dati, si usa un array con collegamenti a un'altra matrice:

+-+ 
|0| -> [0 1 2 3 4] 
|1| -> [0 1 2 3 4] 
|2| -> [0 1 2 3 4] 
+-+ 

Per inserire una riga, basta inserirla nell'ultima posizione e aggiornare la matrice dell'indice rows conseguenza, con il posizione corretta Per esempio. quando rows era [0, 1, 2] e si desidera inserirlo nella parte anteriore, le righe diventeranno [3, 0, 1, 2]. In questo modo l'inserimento di una riga è O(n).

Per inserire una colonna, aggiungerla anche come ultimo elemento e aggiornare di conseguenza i coli. L'inserimento di una colonna è O(m), la riga è O(n).

La cancellazione è anche O(n) o O(m), qui basta sostituire la colonna/riga che si desidera eliminare con l'ultimo e quindi rimuovere l'indice dall'array di indice.

Answer 2

è possibile utilizzare una tabella di hash e inserire (i , j) -> node dove (i, j) è una tupla 2 contenente 2 numeri interi. Puoi scrivere la tua classe personalizzata che definisce il metodo Equals e un metodo GetHash() per quello ... o Python te lo dà gratuitamente.

Ora ... cosa intendi esattamente: ordinabile per riga o colonna? Dai un esempio con i valori per favore!

Answer 3

Forse creando un piccolo database per questo?

Gli algoritmi di ordinamento dei database sono probabilmente migliori rispetto a reinventare la ruota. MySql farebbe. Per ottenere prestazioni, è possibile creare una tabella in memoria. Quindi è possibile indicizzare le colonne come una normale tabella e lasciare che il motore di database esegua il lavoro sporco (ordine e così via). E poi raccogli i risultati.

Answer 4

Se mi venisse consegnato questo problema, creerei i vettori di remapping di righe e colonne. PER ESEMPIO. per ordinare le righe, determinerei normalmente l'ordine delle righe, ma invece di copiare le righe, cambierei semplicemente il vettore di remapping delle righe.

Sarebbe simile a questa:

// These need to be set up elsewhere. 
size_t nRows, nCols; 
std::vector<T> data; 

// Remapping vectors. Initially a straight-through mapping. 
std::vector<size_t> rowMapping(nRows), colMapping(nCols); 
for(size_t y = 0; y < nRows; ++y) 
    rowMapping[y] = y; 
for(size_t x = 0; x < nCols; ++x) 
    colMapping[x] = x; 

// Then you read data(row, col) with 
T value = data[rowMapping[row] * nCols + colMapping[col]]; 

P.S. una piccola ottimizzazione sarebbe quella di memorizzare i puntatori in rowMapping invece di indici. Ciò ti consente di fare T value = rowMapping[row][colMapping[col]];, tuttavia, dovresti ricalcolare i puntatori ogni volta che le dimensioni delle modifiche di data, che potrebbero essere soggette a errori.

Answer 5

Solo per aggiungere a martinus e le risposte di Mike: ciò di cui hai bisogno è, in sostanza, pivoting, che è quello che suggeriscono e una tecnica molto conosciuta utilizzata in quasi tutti gli algoritmi numerici che coinvolgono le matrici. Ad esempio, è possibile eseguire una ricerca rapida per "decomposizione LU con pivot parziale" e "decomposizione LU con pivot completo". I vettori aggiuntivi che memorizzano le permutazioni sono chiamati "pivot".