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?