Curioso domanda: Che cosa fa l'algoritmo STL set_intersect implementa?

Question

ho trascorso una notevole quantità di tempo di codifica a Baeza-Yates' algoritmo di intersezione di set veloce per una delle mie applicazioni. Mentre ho fatto marginalmente fare fuori la set_intersect STL, il fatto che ho richiesto il set risultante da ordinare rimosso in qualsiasi momento avevo guadagnato da attuare il mio algoritmo dopo aver risolto l'uscita. Dato che il set_intersect STL esegue questa bene, qualcuno può punto me per l'algoritmo che in realtà implementa? Oppure è implementare la stessa Baeza-Yates algoritmo, ma solo in un modo molto più efficiente?

Baeza-Yates: http: // citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

Answer 1

Almeno nelle implementazioni che ho guardato, l'implementazione è piuttosto semplicistico - qualcosa su questo ordine generale:

template <class inIt, class outIt>
outIt set_intersection(inIt start1, inIt end1, inIt start2, inIt end2, outIt out) {
    while (start1 != end1 && start2 != end2) {
       if (*start1 < *start2)
           ++start1;
       else if (*start2 < *start1)
           ++start2;
       else {                 // equal elements.
           *out++ = *start1;
           ++start1;
           ++start2;
       }
    }
    return out;
}

Naturalmente, sto solo scrivendo questo fuori dalla parte superiore della mia testa - probabilmente non sarà nemmeno compilare, e di certo non è pedante corretto (ad esempio, dovrebbe probabilmente utilizzare una funzione di confronto invece di utilizzare direttamente operator<, e dovrebbe avere un altro parametro template per consentire start1 / END1 essere un tipo diverso da start2 / FINE2).

Dal punto di vista algoritmico, però, direi più reale implementazioni sono praticamente come sopra.

Answer 2

STL non richiede alcun particolare algoritmo, imposta solo vincoli sulla complessità algoritmica di talune operazioni. Dal momento che è tutto modello basato, si può facilmente visualizzare il sorgente al particolare implementazione per vedere come funziona.

Answer 3

Interessante. Così, il numero di confronti nel vostro algoritmo di scale linearmente con il numero di elementi in entrambi i set. L'algoritmo di Baeza-Yates va qualcosa di simile (si noti che si assume sia in ingresso set sono ordinati):

1) Trovare la mediana di serie A (A è il set più piccolo qui) 2) Ricerca per la mediana di A a B.     Se trovato, aggiungere al risultato     altrimenti, il rango inserimento del mediano B è nota. 3) Split impostare Un attorno al suo mediana in due parti, e insieme B sulla sua posizione di inserimento in due parti, e ripetere la procedura ricorsivamente su entrambe le parti. Questo passaggio funziona perché tutti gli elementi in meno rispetto alla mediana in A si intersecano solo con quegli elementi prima del rango inserimento di mediana di A in B.

Dal momento che è possibile utilizzare una ricerca binaria per individuare mediana di A in B, in modo chiaro, il numero di confronti in questo algoritmo è più basso di quello che lei ha citato. Infatti, nel caso "migliore", il numero di confronti è O (log (m) * log (n)), dove m e n sono le dimensioni dei set, e nel peggiore dei casi, il numero di confronti è O (m + n). Come diavolo ho fatto rovinare l'attuazione questo male? : (