Wie man nur Duplikate effizient hält?

Question

einen STL-Vektor, Ausgabe nur die Duplikate in sortierter Reihenfolge gegeben, zum Beispiel

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

Der Algorithmus ist trivial, aber das Ziel ist es so effizient wie std zu machen :: einzigartig(). Meine naive Implementierung modifiziert den Behälter an Ort und Stelle:

Meine naive Implementierung:

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); 
} 
} 

Wenn Sie diese effizienter zu gestalten, elegant machen können oder allgemeine, lassen Sie es mich wissen. Zum Beispiel ein benutzerdefinierter Sortieralgorithmus oder Kopieren von Elementen in der zweiten Schleife, um den Aufruf von radi() zu eliminieren.

Answer 1

Kürzere und mehr STL-ish als vorherige Einträge. Setzt sortierte Eingabe voraus.

#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

Mein Vorschlag wäre eine modifizierte Einfügung Sortierung, so dass Sie & Filter Dupes zur gleichen Zeit filtern können.

Answer 3

Ich denke, dass von einem großen O Standpunkt aus, Sie haben es so gut wie es geht umgesetzt. Die übergeordneten Kosten sind die Art, die O (N log N) ist. Eine Möglichkeit wäre jedoch, einen neuen Vektor mit den doppelten Einträgen aufzubauen, anstatt den vorhandenen Vektor zu verwenden, wobei die Löschoperation die Nicht-Duplikate entfernt. Dies wäre jedoch nur dann besser, wenn die eindeutige Anzahl der Duplikate relativ zur Gesamtzahl der Einträge klein ist.

Betrachten Sie das extreme Beispiel. Wenn das ursprüngliche Array aus 1.000 Einträgen mit nur einem Duplikat bestand, wäre die Ausgabe ein Vektor mit nur einem Wert. Es könnte ein wenig effizienter sein, den neuen Vektor mit einem Eintrag zu erstellen, anstatt die anderen 999 Einträge aus dem ursprünglichen Vektor zu löschen. Ich vermute jedoch, dass die Ersparnisse dieser Änderung bei realen Tests schwer zu messen sein könnten.

Bearbeiten Ich dachte gerade darüber in Bezug auf "Interview" Frage. Mit anderen Worten, das ist keine besonders nützliche Antwort. Aber es wäre möglich, dies in O (N) (lineare Zeit) im Gegensatz zu O (N Log N) zu lösen. Verwenden Sie Speicherplatz statt CPU. Erstellen Sie zwei "Bit" -Arrays mit ihnen zunächst gelöscht. Schleife durch den Vektor der Integer-Werte. Schlage jeden Wert im ersten Bit-Array nach. Wenn es nicht eingestellt ist, dann setze das Bit (setze es auf 1). Wenn es gesetzt ist, dann setze das entsprechende Bit in dem zweiten Array (was ein Duplikat anzeigt). Nachdem alle Vektoreinträge verarbeitet wurden, scannen Sie durch das zweite Array und geben die Ganzzahlen aus, die Duplikate sind (angezeigt durch die Bits, die in dem zweiten Bitfeld gesetzt sind). Der Grund für die Verwendung von Bit-Arrays ist nur für die Platzeffizienz. Wenn 4-Byte-Ganzzahlen behandelt werden, ist der benötigte Rohraum (2 * 2^32/8). Aber dies könnte tatsächlich in einen brauchbaren Algorithmus verwandelt werden, indem man es zu einem spärlichen Array macht. Der sehr Pseudo Pseudo-Code so etwas wie dies würde:

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 + halten, it_stop);" aus der while-Schleife heraus wird dazu führen, dass die restlichen Elemente immer wieder kopiert werden.

Ich würde vorschlagen, alle einzigartigen Elemente an der Vorderseite des Vektors zu tauschen, und dann die restlichen Elemente auf einmal zu löschen.

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

ich kläglich mit meinem ersten Versuch scheiterte, unter der Annahme, dass std::unique bewegt all Duplikate zum Ende des Bereichs (es nicht). Hoppla. Hier ist ein weiterer Versuch:

Hier ist eine Implementierung von not_unique.Es entfernt alle Elemente, die nur einmal im sortierten Bereich und Duplikate von Elementen angezeigt werden, die mehr als einmal angezeigt werden. Der resultierende Bereich ist daher die eindeutige Liste der Elemente, die mehr als einmal angezeigt werden.

Die Funktion hat eine lineare Komplexität und führt einen einzigen Durchlauf über den Bereich aus (std::unique hat eine lineare Komplexität). It muss die Anforderungen eines Vorwärts-Iterators erfüllen. Das Ende des resultierenden Bereichs wird zurückgegeben.

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

Dies ist im Stil der Standardbibliothek. Kredit für Algorithmus goes to James! (Wenn Sie mir +1 geben, besser Sie +1, oder sonst). Ich tat alles, war es Standard-Bibliothek Stil machen:

#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

können Sie sogar Mismatch verwenden, für Extra-Punkte!
Btw: schöne Übung.

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

Ein anderes:

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

Dies behebt die Fehler in James McNellis's Originalversion. Ich biete auch In-Place- und Out-of-Place-Versionen an.

// 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

Was bedeutet "so effizient wie std :: unique"? Effizient in Bezug auf Laufzeit, Entwicklungszeit, Speichernutzung oder was?

Wie andere darauf hingewiesen haben, erfordert std :: unique sortierte Eingaben, die Sie nicht angegeben haben, also ist es kein fairer Test für den Anfang.

Persönlich würde ich nur eine Std :: Map haben alle meine Arbeit für mich tun. Es hat viele Eigenschaften, die wir für maximale Eleganz/Kürze verwenden können. Es behält seine Elemente bereits sortiert, und Operator [] fügt einen Nullwert ein, wenn der Schlüssel noch nicht existiert. Indem wir diese Eigenschaften nutzen, können wir dies in zwei oder drei Codezeilen durchführen und dennoch eine angemessene Laufzeitkomplexität erreichen.

Grundsätzlich ist mein Algorithmus dies: Für jedes Element im Vektor, inkrementieren Sie um eins den Map-Eintrag durch den Wert dieses Elements. Gehen Sie anschließend einfach auf der Karte und geben Sie einen beliebigen Schlüssel aus, dessen Wert größer als 1 ist. Das könnte nicht einfacher sein.

#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 

So besuchen wir jedes Element in Ihrem Vektor einmal, und dann jedes Element in meiner Karte einmal, wo die Anzahl der Elemente in meiner Karte im schlimmsten Fall ist nicht größer als der Vektor. Die Nachteile meiner Lösung sind viel mehr Speicherplatz als die Lösungen, bei denen der Vektor direkt neu angeordnet wird. Die Vorteile sind jedoch klar. Es ist unglaublich kurz und einfach, es ist offensichtlich richtig, ohne viel Test oder Code-Review, und es hat vernünftige Leistungseigenschaften.

Meine Funktion zu einer Vorlage zu machen und sie auf STL-artigen Bereichen anstatt nur Vektoren von Ints zu betreiben, wird als Übung belassen.