Come ottenere un subvector fuori ordinata di un vettore ordinato, veloce

Question

Ho una struttura di dati in questo modo:

struct X {
  float value;
  int id;
};

un vettore di quelli (dimensioni N (si pensi 100000), ordinati per valore (rimane costante durante l'esecuzione del programma):

std::vector<X> values;

Ora, voglio scrivere una funzione

void subvector(std::vector<X> const& values, 
               std::vector<int> const& ids, 
               std::vector<X>& out /*, 
               helper data here */);

che riempie il su parametro con un ordinato sottoinsieme di valori , in passato ids (dimensioni M < N (circa 0,8 volte N )), veloce (memoria non è un problema, e questo sarà fatto ripetutamente, costruendo così lookuptables ( dati helper dai parametri della funzione) o qualcos'altro che è fatto solo una volta è del tutto ok).

La mia soluzione finora:
Costruire LOOKUPTABLE LUT contenente id -> compensato in valori (preparazione, in modo costante runtime)
creare std::vector<X> tmp, dimensione N, pieno di ids non validi (lineare in N )
per ogni ID, copiare values[lut[id]] a tmp[lut[id]] (lineare in M )
un ciclo su tmp , la copia di elementi da il (lineare in N )

questo è lineare nel N (come è più grande di M ), ma la variabile temporanea e bug me la copia ripetuti. C'è un modo per farlo più veloce di questo? Nota che M sarà vicino al N , quindi le cose che sono O ( M di registro N ) sono sfavorevoli.

Modifica: http://ideone.com/xR8Vp è un esempio di implementazione dell'algoritmo detto, per fare il desiderato di uscita chiara e dimostrare che è fattibile in tempo lineare - la domanda riguarda la possibilità di evitare la variabile temporanea o accelerarlo in qualche altro modo, qualcosa che non è lineare non è più veloce:)

.

Answer 1

Un approccio alternativo si può provare è quella di utilizzare una tabella hash invece di un vettore per cercare ids in:

void subvector(std::vector<X> const& values, 
               std::unordered_set<int> const& ids, 
               std::vector<X>& out) {

    out.clear();
    out.reserve(ids.size());
    for(std::vector<X>::const_iterator i = values.begin(); i != values.end(); ++i) {
        if(ids.find(i->id) != ids.end()) {
            out.push_back(*i);
        }
    }
}

Questo viene eseguito in tempo lineare dal unordered_set::find è tempo previsto costante (assumendo che non abbiamo problemi di hashing int). Tuttavia ho il sospetto che potrebbe non essere così veloce, in pratica, come l'approccio hai descritto inizialmente usando vettori.

Answer 2

Dal momento che il vettore è ordinato, e si desidera un sottoinsieme di esso allineati allo stesso modo, presumo possiamo solo tagliare fuori il pezzo che si desidera senza riorganizzare esso.

Perché non usare find_if () due volte. Una volta per trovare l'inizio della gamma che si desidera e una volta per trovare il limite del campo. Questo vi darà le inizio e di fine iteratori del sub vettore. Costruire un nuovo vettore usando quei iteratori. Uno del vettore costruttore sovraccarichi prende due iteratori.

Che o il href="http://www.cplusplus.com/reference/algorithm/partition/" algoritmo rel="nofollow"> partizione

Answer 3

Se ho capito bene il problema, in realtà si tenta di creare un tempo lineare algoritmo di ordinamento (fatta salva la dimensione dell'input di numeri M). Questo non è possibile.

Il tuo attuale approccio è quello di avere un elenco ordinato di valori possibili. Questo richiede tempo lineare per il numero di possibili valori di N (in teoria, dato che la ricerca mappa prende O (1) tempo).

Il meglio che si possa fare, è quello di ordinare i valori (avete trovato dalla mappa) con un metodo rapido di ordinamento (O (MlogM) fe quicksort, mergesort ecc) per piccoli valori di M e magari farlo ricerca lineare per i più grandi valori di M. Ad esempio, se N è 100000 e M è 100 è molto più veloce ad basta usare un algoritmo di ordinamento.

spero che tu possa capire quello che dico. Se avete ancora domande cercherò di rispondere:)

modifica: (commento) Vi ulteriormente spiegare cosa intendo. Diciamo che sa che i numeri varieranno da 1 a 100. Li hai ordinati da qualche parte (in realtà sono "naturalmente" ordinati) e si desidera ottenere un sottoinsieme di essi in forma ordinata. Se fosse possibile farlo più veloce di O (N) o O (MlogM), algoritmi di ordinamento sarebbe solo utilizzare questo metodo per ordinare.

F.e. avendo l'insieme dei numeri {} 5,10,3,8,9,1,7, sapendo che sono un sottoinsieme del set ordinato di numeri {1,2,3,4,5,6,7,8 , 9,10} non è ancora possibile sorta di loro più veloce di o (N) (N = 10) o o (MlogM) (M = 7).