Come mantenere solo i duplicati in modo efficiente?

Question

Dato un vettore STL, uscita solo i duplicati in modo ordinato, per esempio,

INPUT : { 4, 4, 1, 2, 3, 2, 3 } 
OUTPUT: { 2, 3, 4 } 

L'algoritmo è banale, ma l'obiettivo è quello di rendere il più efficiente std :: unico(). La mia implementazione ingenuo modifica il contenitore sul posto:

mia ingenua implementazione:

void not_unique(vector<int>* pv) 
{ 
    if (!pv) 
     return; 

// Sort (in-place) so we can find duplicates in linear time 
sort(pv->begin(), pv->end()); 

vector<int>::iterator it_start = pv->begin(); 
while (it_start != pv->end()) 
{ 
    size_t nKeep = 0; 

    // Find the next different element 
    vector<int>::iterator it_stop = it_start + 1; 
    while (it_stop != pv->end() && *it_start == *it_stop) 
    { 
    nKeep = 1; // This gets set redundantly 
    ++it_stop; 
    } 

    // If the element is a duplicate, keep only the first one (nKeep=1). 
    // Otherwise, the element is not duplicated so erase it (nKeep=0). 
    it_start = pv->erase(it_start + nKeep, it_stop); 
} 
} 

Se si può fare questo più efficiente, elegante, o generale, per favore fatemelo sapere. Ad esempio, un algoritmo di ordinamento personalizzato o copia elementi nel secondo ciclo per eliminare la chiamata cancella().

Answer 1

Più breve e più STL rispetto alle voci precedenti. Assume input ordinati.

#include <algorithm> 
#include <functional> 

template< class I, class P > 
I remove_unique(I first, I last, P pred = P()) { 
    I dest = first; 
    while (
     (first = std::adjacent_find(first, last, pred)) 
      != last) { 
     * dest = * first; 
     ++ first; 
     ++ dest; 
     if ((first = std::adjacent_find(first, last, std::not2(pred))) 
      == last) break; 
     ++ first; 
    } 
    return dest; 
} 

template< class I > 
I remove_unique(I first, I last) { 
    return remove_unique(first, last, 
     std::equal_to< typename std::iterator_traits<I>::value_type >()); 
} 

Answer 2

Il mio suggerimento sarebbe un ordinamento di inserimento modificato, in modo che sia possibile ordinare i duplicati del filtro & allo stesso tempo.

Answer 3

Penso che da un punto di vista O grande, l'hai implementato nel miglior modo possibile. Il costo prevalente è l'ordinamento, che è O (N log N). Una possibilità, tuttavia, sarebbe quella di creare un nuovo vettore con le voci duplicate piuttosto che utilizzare il vettore esistente con l'operazione di eliminazione rimuovendo i non duplicati. Tuttavia, ciò sarebbe migliore solo se il numero distinto di duplicati è piccolo rispetto al numero totale di voci.

Considerare l'esempio estremo. Se la matrice originale consisteva di 1.000 voci con un solo duplicato, l'output sarebbe un vettore con un solo valore. Potrebbe essere un po 'più efficiente creare il nuovo vettore con una voce piuttosto che cancellare le altre 999 voci dal vettore originale. Sospetto, tuttavia, che nei test sul mondo reale, i risparmi di tale cambiamento potrebbero essere difficili da misurare.

Modifica Stavo proprio pensando a questo in termini di domanda "intervista". In altre parole, questa non è una risposta terribilmente utile. Ma sarebbe possibile risolvere questo in O (N) (tempo lineare) anziché O (N Log N). Usa spazio di archiviazione anziché CPU. Crea due matrici "bit" con esse cancellate inizialmente. Passa in rassegna il tuo vettore di valori interi. Cerca ogni valore nel primo array di bit. Se non è impostato, quindi imposta il bit (impostalo su 1). Se è impostato, quindi imposta il bit corrispondente nel secondo array (indicando un duplicato). Dopo che tutte le voci vettoriali sono state elaborate, eseguire la scansione attraverso il secondo array e generare gli interi che sono duplicati (indicati dai bit impostati nel secondo array di bit). La ragione per l'utilizzo degli array di bit è solo per l'efficienza dello spazio. Se si ha a che fare con interi a 4 byte, lo spazio grezzo richiesto è (2 * 2^32/8). Ma questo potrebbe essere trasformato in un algoritmo utilizzabile rendendolo un array sparse. Lo pseudo-codice molto pseudo sarebbe qualcosa di simile a questo:

bitarray1[infinite_size]; 
bitarray2[infinite_size]; 

clear/zero bitarrays 

// NOTE - do not need to sort the input 
foreach value in original vector { 
    if (bitarray1[value]) 
     // duplicate 
     bitarray2[value] = 1 
    bitarray1[value] = 1 
} 

// At this point, bitarray2 contains a 1 for all duplicate values. 
// Scan it and create the new vector with the answer 
for i = 0 to maxvalue 
    if (bitarray2[i]) 
     print/save/keep i 

Answer 4

Calling "erase (it_start + mantenere, it_stop);" dall'interno del ciclo while si otterrà la copia degli elementi rimanenti più e più volte.

Suggerirei di scambiare tutti gli elementi univoci nella parte anteriore del vettore, quindi cancellare tutti gli elementi rimanenti contemporaneamente.

int num_repeats(vector<int>::const_iterator curr, vector<int>::const_iterator end) { 
    int same = *curr; 
    int count = 0; 
    while (curr != end && same == *curr) { 
    ++curr; 
    ++count; 
    } 
    return count; 
} 

void dups(vector<int> *v) { 
    sort(v->begin(), v->end()); 
    vector<int>::iterator current = v->begin(); 
    vector<int>::iterator end_of_dups = v->begin(); 
    while (current != v->end()) { 
    int n = num_repeats(current, v->end()); 
    if (n > 1) { 
     swap(*end_of_dups, *current); 
     end_of_dups++; 
    } 
    current += n; 
    } 
    v->erase(end_of_dups, v->end()); 
} 

Answer 5

ho miseramente fallito con il mio primo tentativo, partendo dal presupposto che std::unique muove tutti i duplicati alla fine del campo (non è così). Ops. Ecco un altro tentativo:

Ecco un'implementazione di not_unique.Rimuove qualsiasi elemento visualizzato una sola volta nell'intervallo ordinato e duplicati di qualsiasi elemento visualizzato più volte. L'intervallo risultante è quindi l'elenco univoco di elementi che appaiono più di una volta.

La funzione ha una complessità lineare e fa un singolo passaggio nell'intervallo (std::unique ha una complessità lineare). It deve soddisfare i requisiti di un iteratore di inoltro. Viene restituita la fine dell'intervallo risultante.

template <typename It> 
It not_unique(It first, It last) 
{ 
    if (first == last) { return last; } 

    It new_last = first; 
    for (It current = first, next = ++first; next != last; ++current, ++next) 
    { 
     if (*current == *next) 
     { 
      if (current == new_last) 
      { 
       ++new_last; 
      } 
      else 
      { 
       *new_last++ = *current; 
       while (next != last && *current == *next) 
       { 
        ++current; 
        ++next; 
       } 
       if (next == last) 
        return new_last; 
      } 
     } 
    } 
    return new_last; 
} 

Answer 6

Questo è nello stile della libreria standard. Credito per algoritmo goes to James! (Se fai +1 su di me, è meglio farlo +1, oppure). Tutto quello che ho fatto è stato renderlo stile libreria standard:

#include <algorithm> 
#include <functional> 
#include <iostream> 
#include <iterator> 
#include <vector> 

// other stuff (not for you) 
template <typename T> 
void print(const char* pMsg, const T& pContainer) 
{ 
    std::cout << pMsg << "\n "; 
    std::copy(pContainer.begin(), pContainer.end(), 
     std::ostream_iterator<typename T::value_type>(std::cout, " ")); 
    std::cout << std::endl; 
} 

template <typename T, size_t N> 
T* endof(T (&pArray)[N]) 
{ 
    return &pArray[0] + N; 
} 

// not_unique functions (for you) 
template <typename ForwardIterator, typename BinaryPredicate> 
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast, 
          BinaryPredicate pPred) 
{ 
    // correctly handle case where an empty range was given: 
    if (pFirst == pLast) 
    { 
     return pLast; 
    } 

    ForwardIterator result = pFirst; 
    ForwardIterator previous = pFirst; 

    for (++pFirst; pFirst != pLast; ++pFirst, ++previous) 
    { 
     // if equal to previous 
     if (pPred(*pFirst, *previous)) 
     { 
      if (previous == result) 
      { 
       // if we just bumped bump again 
       ++result; 
      } 
      else if (!pPred(*previous, *result)) 
      { 
       // if it needs to be copied, copy it 
       *result = *previous; 

       // bump 
       ++result; 
      } 
     } 
    } 

    return result; 
} 

template <typename ForwardIterator> 
ForwardIterator not_unique(ForwardIterator pFirst, ForwardIterator pLast) 
{ 
    return not_unique(pFirst, pLast, 
       std::equal_to<typename ForwardIterator::value_type>()); 
} 


//test 
int main() 
{ 
    typedef std::vector<int> vec; 

    int data[] = {1, 4, 7, 7, 2, 2, 2, 3, 9, 9, 5, 4, 2, 8}; 
    vec v(data, endof(data)); 

    // precondition 
    std::sort(v.begin(), v.end()); 
    print("before", v); 

    // duplicatify (it's a word now) 
    vec::iterator iter = not_unique(v.begin(), v.end()); 
    print("after", v); 

    // remove extra 
    v.erase(iter, v.end()); 
    print("erased", v); 
} 

Answer 7

È anche possibile utilizzare la mancata corrispondenza, per punti extra!
A proposito: bel esercizio.

template<class TIter> 
/** Moves duplicates to front, returning end of duplicates range. 
* Use a sorted range as input. */ 
TIter Duplicates(TIter begin, TIter end) { 
    TIter dup = begin; 
    for (TIter it = begin; it != end; ++it) { 
     TIter next = it; 
     ++next; 
     TIter const miss = std::mismatch(next, end, it).second; 
     if (miss != it) { 
      *dup++ = *miss; 
      it = miss; 
     } 
    } 
    return dup; 
} 

Answer 8

Un altro:

template <typename T> 
void keep_duplicates(vector<T>& v) 
{ 
    set<T> 
     u(v.begin(), v.end()), // unique 
     d; // duplicates 
    for (size_t i = 0; i < v.size(); i++) 
     if (u.find(v[i]) != u.end()) 
      u.erase(v[i]); 
     else 
      d.insert(v[i]); 

    v = vector<T>(d.begin(), d.end()); 
} 

Answer 9

questo risolve il bug nella James McNellis's versione originale. Fornisco anche versioni sul posto e fuori dal luogo.

// In-place version. Uses less memory and works for more container 
// types but is slower. 
template <typename It> 
It not_unique_inplace(It first, It last) 
{ 
    if (first == last) 
     return last; 

    It new_last = first; 
    for (It current = first, next = first + 1; next != last; ++current, ++next) 
    { 
     if (*current == *next && 
      (new_last == first || *current != *(new_last-1))) 
      *new_last++ = *current; 
    } 
    return new_last; 
} 

// Out-of-place version. Fastest. 
template <typename It, typename Container> 
void not_unique(It first, It last, Container pout) 
{ 
    if (first == last || !pout) 
     return; 

    for (It current = first, next = first + 1; next != last; ++current, ++next) 
    { 
     if (*current == *next && 
      (pout->empty() || *current != pout->back())) 
      pout->push_back(*current); 
    } 
} 

Answer 10

Cosa si intende per "efficiente come std :: unique"? Efficiente in termini di tempo di esecuzione, tempo di sviluppo, utilizzo della memoria o cosa?

Come altri hanno sottolineato, std :: unique richiede un input ordinato, che non è stato fornito, quindi non è un test giusto per cominciare.

Personalmente avrei solo una std :: map fare tutto il mio lavoro per me. Ha molte proprietà che possiamo usare per la massima eleganza/brevità. Mantiene già ordinati i suoi elementi e l'operatore [] inserirà un valore zero se la chiave non esiste già. Sfruttando tali proprietà, possiamo ottenere questo risultato in due o tre righe di codice, ottenendo comunque una ragionevole complessità di runtime.

In sostanza, il mio algoritmo è questo: per ciascun elemento nel vettore, incrementa di un'unità la voce della mappa basata sul valore di quell'elemento. Successivamente, basta camminare sulla mappa, emettendo una chiave il cui valore è maggiore di 1. Non potrebbe essere più semplice.

#include <iostream> 
#include <vector> 
#include <map> 

void 
output_sorted_duplicates(std::vector<int>* v) 
{ 
    std::map<int, int> m; 

    // count how many of each element there are, putting results into map 
    // map keys are elements in the vector, 
    // map values are the frequency of that element 
    for (std::vector<int>::iterator vb = v->begin(); vb != v->end(); ++vb) 
     ++m[*vb]; 

    // output keys whose values are 2 or more 
    // the keys are already sorted by the map 
    for (std::map<int, int>::iterator mb = m.begin(); mb != m.end(); ++mb) 
     if ((*mb).second >= 2) 
     std::cout << (*mb).first << " "; 
    std::cout << std::endl; 
} 

int main(void) 
{ 
    int initializer[] = { 4, 4, 1, 2, 3, 2, 3 }; 
    std::vector<int> data(&initializer[0], &initializer[0] + 7); 
    output_sorted_duplicates(&data); 
} 

janks@phoenix:/tmp$ g++ test.cc && ./a.out 
2 3 4 

Così, visitiamo ogni elemento del vettore una volta, e poi ogni elemento nella mia mappa una volta, in cui il numero di elementi nella mia mappa è nel peggiore dei casi non più grande di vettore. Gli svantaggi della mia soluzione sono molto più spazio di archiviazione rispetto alle soluzioni che prevedono la riorganizzazione del proprio vettore sul posto. I vantaggi, tuttavia, sono chiari. È incredibilmente breve e semplice, è ovviamente corretto senza bisogno di molti test o revisione del codice, e ha proprietà di prestazioni ragionevoli.

Rendere la mia funzione un modello e farlo funzionare su gamme stile STL anziché solo vettori di int, è lasciato come esercizio.