Modo efficiente per trovare elementi unici in un vettore rispetto a più vettori

Naviga le tue risposte
6

Sto cercando di trovare il numero di elementi unici in un vettore rispetto a più vettori usando C ++. I vettori sono in ordine e possono essere di taglia 2.000.000.

Supponiamo che io abbia 

v1: 5, 8, 13, 16, 20
v2: 2, 4, 6, 8
v3: 20
v4: 1, 2, 3, 4, 5, 6, 7
v5: 1, 3, 5, 7, 11, 13, 15

Il numero di elementi univoci in v1 è 1 (cioè il numero 16).

Ho provato due approcci.

  1. Aggiunti i vettori v2, v3, v4 e v5 in un vettore di vettore. Per ogni elemento in v1, controllato se l'elemento è presente in uno qualsiasi degli altri vettori.

  2. Combinato tutti i vettori v2, v3, v4 e v5 utilizzando l'ordinamento di unione in un singolo vettore e confrontato con v1 per trovare gli elementi univoci.

Nota: sample_vector = v1 e all_vectors_merged contiene v2, v3, v4, v5 

//Method 1
unsigned int compute_unique_elements_1(vector<unsigned int> sample_vector,vector<vector<unsigned int> > all_vectors_merged)
{
    unsigned int duplicate = 0;
    for (unsigned int i = 0; i < sample_vector.size(); i++)
    {
        for (unsigned int j = 0; j < all_vectors_merged.size(); j++)
        {
            if (std::find(all_vectors_merged.at(j).begin(), all_vectors_merged.at(j).end(), sample_vector.at(i)) != all_vectors_merged.at(j).end())
            {
                duplicate++;
            }
        }
    }
    return sample_vector.size()-duplicate;
}

// Method 2
unsigned int compute_unique_elements_2(vector<unsigned int> sample_vector, vector<unsigned int> all_vectors_merged)
{
    unsigned int unique = 0;
    unsigned int i = 0, j = 0;
    while (i < sample_vector.size() && j < all_vectors_merged.size())
    {
        if (sample_vector.at(i) > all_vectors_merged.at(j))
        {
            j++;
        }
        else if (sample_vector.at(i) < all_vectors_merged.at(j))
        {
            i++;
            unique ++;
        }
        else
        {
            i++;
            j++;
        }
    }
    if (i < sample_vector.size())
    {
        unique += sample_vector.size() - i;
    }
    return unique;
}

Di queste due tecniche, vedo che il Metodo 2 dà risultati più veloci.

1) Metodo 1: esiste un modo più efficiente per trovare gli elementi rispetto all'esecuzione di std :: find su tutti i vettori per tutti gli elementi nella v1.

2) Metodo 2: overhead aggiuntivo nel confronto tra vettori v2, v3, v4, v5 e ordinamento.

Come posso farlo in un modo migliore?

[modifica] I vettori sono ordinati.

    
posta SyncMaster 03.09.2012 - 22:59
fonte

3 risposte

9

Usa tabelle hash. Gli elementi sono la chiave, il numero di occorrenze sono i valori.

    
risposta data 03.09.2012 - 23:18
fonte
0

Sembra che i tuoi dati siano stringhe e hai usato valori numerici per illustrare più facilmente aspetti del problema come ogni vettore che viene ordinato, ma con molti vettori per scorrere l'iterazione.

La programmazione dinamica può offrire grandi opportunità per ottenere grandi risparmi in termini di efficienza. In genere, la programmazione dinamica esegue parte del proprio algoritmo per generare una soluzione parziale che può essere riutilizzata in iterazioni successive per risparmiare tempo. C'è una ottima versione del problema del commesso viaggiatore che fa questo per enormi risparmi di tempo (al trade-off di bisogno di enormi quantità di memoria).

Se conosci alcune cose sui tuoi dati, dì che è limitato ai valori interi compresi tra 0 e 99, un approccio semplice sarebbe quello di creare una tabella di 100 valori booleani, analizzare i vettori una volta per contrassegnare la tabella per mostrare quali elementi sono presenti, quindi confronta il tuo vettore test con il tavolo.

Se si trattasse di un algoritmo di ricerca e l'input fosse una chiave di più stringhe e i dati vettoriali multipli ordinati fossero parole chiave dai documenti, si potrebbe scegliere tra molti metodi per raccogliere le stringhe univoche in una rappresentazione adatta per binary o altra ricerca . Lo spazio di archiviazione necessario per questa struttura dati di supporto dipenderà dal numero di stringhe univoche presenti nel set di dati di input. Potrebbe sorprendere anche per i dati così diversi come il testo inglese come poche stringhe uniche possono essere trovate in due milioni di vettori, anche di poche centinaia di parole ciascuna.

    
risposta data 15.09.2012 - 17:21
fonte
0

Poiché sono ordinati, puoi utilizzare la funzione standard std::set_difference : 

unsigned int compute_uniqute_elements(vector<unsigned int> sample_vector, vector<unsigned int> merged_vectors)
{
    vector<unsigned int> difference;
    vector<unsigned int>::iterator it;
    it = std::set_difference(sample_vector.begin(), sample_vector.end(), it->begin(), it->end(), difference.begin());

    return std::distance(difference.begin(), it);
}
    
risposta data 16.09.2012 - 01:30
fonte

Leggi altre domande sui tag

Quali sono gli svantaggi dell'utilizzo di stored procedure, SSIS e SSRS per implementare applicazioni aziendali? [chiuso] Come potrei fare un suggerimento per una modifica allo standard SQL