Differenza tra due vettori A e B

Question

Ho due oggetti vector<MyType*> chiamati A e B. La classe MyType ha un ID campo e voglio ottenere il MyType* che sono in A ma non in B. Sto lavorando su un'applicazione per l'analisi delle immagini e speravo di trovare una rapida soluzione / ottimizzata.

Answer 1

L'approccio non ordinata in genere hanno la complessità quadratica a meno che i dati vengono ordinati in precedenza (dal campo ID), nel qual caso sarebbe lineare e non richiederebbe ricerche ripetute attraverso B.

struct CompareId
{
    bool operator()(const MyType* a, const MyType* b) const
    {
        return a>ID < b->ID;
    }
};
...
sort(A.begin(), A.end(), CompareId() );
sort(B.begin(), B.end(), CompareId() );

vector<MyType*> C;
set_difference(A.begin(), A.end(), B.begin(), B.end(), back_inserter(C) );

Un'altra soluzione è quella di utilizzare un contenitore ordinato come std :: set con CompareId utilizzato per l'argomento modello StrictWeakOrdering. Credo che questo sarebbe meglio se avete bisogno di applicare un sacco di operazioni di set. Che ha una sua testa (essendo un albero), ma se davvero trovate che sia un problema di efficienza, si potrebbe implementare un allocatore di memoria veloce per inserire e rimuovere elementi super veloce (nota: fare solo se il tuo profilo e determinare che si tratta da un collo di bottiglia).

Attenzione:. Entrare in territorio un po 'complicato

C'è un'altra soluzione si può considerare che potrebbe essere molto veloce se del caso e non avete mai preoccuparsi di ordinamento dei dati. In sostanza, fare qualsiasi gruppo di oggetti MyType che condividono lo stesso Codice del negozio un contatore comune (es: puntatore a unsigned int).

Ciò richiederà la creazione di una mappa di ID ai contatori e richiedono il recupero il contatore dalla mappa ogni volta che un oggetto MyType viene creato in base al relativo ID. Dal momento che si dispone di oggetti MyType con ID duplicati, non si dovrebbero avere per inserire alla mappa tutte le volte che si creano oggetti MyType (la maggior parte può probabilmente solo prendere un contatore già esistente).

In aggiunta a questo, hanno un contatore globale 'attraversamento' che viene incrementato ogni volta che è recuperata.

static unsigned int counter = 0;
unsigned int traversal_counter()
{
    // make this atomic for multithreaded applications and
    // needs to be modified to set all existing ID-associated
    // counters to 0 on overflow (see below)
    return ++counter;
}

Ora torniamo al punto in cui si dispone di vettori A e B memorizzazione MyType *. Per recuperare gli elementi di A che non sono in B, in primo luogo abbiamo traversal_counter call (). Supponendo che è la prima volta che lo chiamiamo noi, che ci darà un valore di attraversamento 1.

Ora iterate attraverso ogni MyType * oggetto in B e impostare il contatore condivisa per ciascun oggetto da 0 fino al valore attraversamento, 1.

Ora iterate attraverso ogni MyType * oggetto in A. Quelli che hanno un valore di contatore che non corrisponde al valore corrente di attraversamento (1) sono gli elementi di A che non sono contenuti in B.

Cosa succede quando si traboccare il contatore attraversamento? In questo caso, l'iterazione attraverso tutti i contatori memorizzati nella mappa ID e azzerato assieme al contatore attraversamento stessa. Questo sarà solo bisogno di verificarsi una volta in circa 4 miliardi di attraversamenti, se si tratta di un 32 bit unsigned int.

Questa è la soluzione più veloce è possibile applicare al vostro dato problema. Si può fare qualsiasi operazione impostata in complessità lineare su dati non ordinati (e sempre, non solo in scenari più caso come una tabella hash), ma lo fa introdurre una certa complessità in modo da prendere in considerazione solo se si ha realmente bisogno.

Answer 2

Ordina entrambi i vettori ( std::sort ) secondo ID e quindi utilizzare std::set_difference . Sarà necessario definire un comparatore personalizzato per passare a due di questi algoritmi, ad esempio

struct comp
{
    bool operator()(MyType * lhs, MyType * rhs) const
    {
        return lhs->id < rhs->id;
    }
};

Answer 3

Primo sguardo al problema. Si vuole "tutto in A non in B". Ciò significa che si sta andando ad avere per visitare "tutto in A". Dovrete anche a visitare tutto in B per avere conoscenza di ciò che è e non è in B. In modo che suggerisce ci dovrebbe essere una soluzione O(n) + O(m), o prendendo la libertà di elidere la differenza tra nem, O(2n).

Consideriamo l'approccio std::set_difference. Ogni specie è O(n log n), e set_difference è O(n). Quindi l'approccio specie-sort-set_difference è O(n + 2n log n). la chiamata di lasciare che O(4n).

Un altro approccio sarebbe quello primo luogo gli elementi di B in un insieme (o mappa). Iterazione attraverso B per creare il set è O(n) inclusa inserimento O(log n) di ciascun elemento, seguita da iterazione attraverso un O (n), con una ricerca per ogni elemento di A (log n), dà un totale: O(2n log n). la chiamata di lasciare che O(3n), che è leggermente migliore.

Infine, utilizzando un unordered_set (o unordered_map), e assumendo otteniamo caso medio di inserimento O(1) e ricerca O(1), abbiamo un approccio O(2n). A-ha!

La vera vittoria qui è che unordered_set (o mappa) è probabilmente la scelta più naturale per rappresentare i dati in primo luogo, vale a dire, la corretta progettazione cede l'implementazione ottimizzata. Questo non sempre accade, ma è bello quando lo fa!

Answer 4

Se preesiste B ad A, poi durante il popolamento A, è possibile bookkeep in un vettore C.