Contenitore C++ più veloce: valori unici

Question

Sto scrivendo un'applicazione di posta elettronica che si interfaccia con un database MySQL. Ho due tabelle che stanno acquistando i miei dati, uno dei quali contiene le disiscrizioni, l'altra delle quali è una tabella utente standard. A partire da ora, sto creando un vettore di puntatori agli oggetti di posta elettronica e, inizialmente, memorizzando tutte le e-mail non iscritte. Poi ho un ciclo SQL standard in cui sto verificando se l'e-mail non si trova nel vettore di annullamento dell'iscrizione, quindi aggiungendolo al vettore globale di posta elettronica di invio. La mia domanda è, c'è un modo più efficiente per farlo? Devo cercare il vettore di unsub per ogni singola e-mail nel mio sistema, fino a 50 K diversi. C'è una struttura migliore per la ricerca? E una struttura migliore per mantenere una collezione unica di valori? Forse uno che semplicemente scarterebbe il valore se già lo contiene?

Answer 1

Se l'implementazione della libreria standard C++ lo supporta, prendere in considerazione l'utilizzo di std::unordered_set o std::hash_set.

È inoltre possibile utilizzare std::set, anche se il sovraccarico potrebbe essere più elevato (dipende dal costo di generazione di un hash per l'oggetto rispetto al costo del confronto di due degli oggetti più volte).

Se si utilizza un contenitore in base nodo di come set o unordered_set, si ottiene anche il vantaggio che la rimozione di elementi è relativamente a buon mercato rispetto alla rimozione da un vector.

Answer 2

Memorizza gli indirizzi e-mail in un std::set o utilizza std::set_difference().

Answer 3

1. Attività come questa (impostare le manipolazioni) sono meglio lasciate a ciò che è MEANT per eseguirle - il database!

   E.g. qualcosa sulla falsariga di:

   SELECT email FROM all_emails_table e WHERE NOT EXISTS (
       SELECT 1 FROM unsubscribed u where e.email=u.email 
   ) 
   

2. Se si desidera un algoritmo, è possibile farlo rapidamente recuperando sia l'elenco dei messaggi di posta elettronica e un elenco di unsubscriptions come liste ordinate. Quindi puoi passare attraverso l'elenco di e-mail (che è ordinato), e mentre lo fai scivoli lungo l'elenco di annullamento dell'iscrizione. L'idea è di spostare 1 avanti in qualsiasi elenco abbia l'elemento "più grande" attuale.Questo algo è O (M + N) invece di O (M * N) come il tuo attuale

3. Oppure, puoi fai una mappa hash che mappa dall'indirizzo e-mail non iscritto a 1. Quindi fai le chiamate find() su quella mappa per le corrette implementazioni hash O (1) per ogni ricerca Sfortunatamente, non c'è lo standard Hash Map in C++ - vedi this SO question for existing implementations (paio di idee ci sono di STL hash_map e Boost e/o TR1 std::tr1::unordered_map SGI)

   Uno dei commenti su quel post indica che verrà aggiunto alla norma:. "Con questo in mente, lo standard Biblioteca Relazione tecnica C++ introdotto i contenitori associativi non ordinati, che sono realizzati tramite tabelle hash, e sono stati aggiunti alla bozza di lavoro di Visual C++ ".

Answer 4

Il modo migliore per farlo è all'interno di MySQL, credo. È possibile modificare lo schema della tabella degli utenti con un'altra colonna, una colonna BIT, per "è annullata la sottoscrizione". Meglio ancora: aggiungi una colonna DATETIME per "data cancellata" con un valore predefinito di NULL.

Se si utilizza una colonna BIT, la query diventa qualcosa di simile a:

SELECT * FROM `users` WHERE `unsubscribed` <> 0b1; 

Se si utilizza una colonna DATETIME, la query diventa qualcosa di simile:

SELECT * FROM `users` WHERE `date_unsubscribed` IS NULL;