Ricerca di valore efficiente in Elenco di k-Tuples

4

Ho riscontrato un problema in un progetto personale che ritengo possa essere risolto da una particolare struttura di dati, ma non sono sicuro di cosa. Il problema è il seguente:

Dato un insieme di k-tuple, fornire una struttura dati efficiente che, data una posizione, i, e un valore, p, restituisce un elenco di tuple che contengono il valore p nella posizione i.

So che posso farlo in tempo O (n) mappando un filtro attraverso l'elenco (il filtro restituisce true se p è in i nella tupla data). Comunque mi chiedo se possa essere fatto in < O (n)?

So anche che potrei creare mappe k, una per ogni posizione, che mappa un valore in una posizione alla lista di tuple che contengono quel valore in quella posizione. Tuttavia, questo 1) occupa molto spazio (k ^ k?) E 2) se aggiorno il set di tuple (aggiungendo una tupla, rimuovendo una tupla, aggiornando un valore all'interno di una tupla) molte delle k map potrebbero aver bisogno di da aggiornare.

Esiste un compromesso tra queste due soluzioni che sono efficienti nell'interrogazione del tempo e dello spazio di archiviazione?

    
posta geofflittle 03.05.2016 - 19:54
fonte

1 risposta

1

Potresti trovare qualche utile ispirazione dagli indici dei database relazionali , che cercano di risolvere un problema simile di trovare righe che avere un determinato valore in una colonna.

However I wonder if it can be done in < O(n)?

Guarderei alberi , alberi di ricerca auto-bilanciati o (se hai molti dati) B-trees . Probabilmente puoi ottenere O (n) archiviazione e cercare / modificare a O (log (n)). Tuttavia, ogni volta che aggiungi, rimuovi o modifichi una tupla, dovrai aggiornare gli alberi corrispondenti alle sue colonne in modo che le ricerche siano accurate.

Se vuoi davvero diventare attraente, il tuo sistema potrebbe utilizzare diverse strategie di indicizzazione a seconda del numero di righe e della natura dei dati da indicizzare.

    
risposta data 03.05.2016 - 22:18
fonte

Leggi altre domande sui tag