¿Cómo mantener solo duplicados de manera eficiente?

Question

Dado un vector de STL, salida sólo los duplicados en el orden establecido, por ejemplo,

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

El algoritmo es trivial, pero el objetivo es que sea lo más eficiente como std :: única(). Mi aplicación ingenua modifica el contenedor en el lugar:

mi implementación ingenua:

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

Si usted puede hacer esto más eficiente, elegante, o general, por favor hágamelo saber. Por ejemplo, un algoritmo de clasificación personalizado, o elementos de copia en el 2do ciclo para eliminar la llamada de borrado().

Answer 1

Más corto y más STL-ish que las entradas anteriores. Asume la entrada ordenada.

#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

Mi sugerencia sería una ordenación de inserción modificada, para que pueda ordenar & duplicados de filtro al mismo tiempo.

Answer 3

Creo que desde un gran punto de vista de O, lo has implementado todo lo bien que se puede. El costo principal es el tipo, que es O (N log N). Una posibilidad, sin embargo, sería construir un nuevo vector con las entradas duplicadas en lugar de usar el vector existente con la operación de eliminación eliminando los no duplicados. Sin embargo, esto solo sería mejor si la cantidad de duplicados es pequeña en relación con el número total de entradas.

Considere el ejemplo extremo. Si la matriz original constaba de 1,000 entradas con solo un duplicado, entonces la salida sería un vector con solo un valor. Puede ser un poco más eficiente crear el nuevo vector con una entrada en lugar de eliminar las otras 999 entradas del vector original. Sospecho, sin embargo, que en las pruebas del mundo real, el ahorro de ese cambio podría ser difícil de medir.

Editar Estaba pensando en esto en términos de "entrevista". En otras palabras, esta no es una respuesta terriblemente útil. Pero sería posible resolver esto en O (N) (tiempo lineal) en oposición a O (N Log N). Use espacio de almacenamiento en lugar de CPU. Crea dos arreglos "bit" con ellos borrados inicialmente. Pasa por tu vector de valores enteros. Busque cada valor en la primera matriz de bits. Si no está configurado, configure el bit (establézcalo en 1). Si está configurado, configure el bit correspondiente en el segundo conjunto (que indica un duplicado). Después de procesar todas las entradas de vector, escanee a través de la segunda matriz y genere los enteros que son duplicados (indicados por los bits establecidos en la segunda matriz de bits). La razón para usar matrices de bits es solo para la eficiencia del espacio. Si se trata de enteros de 4 bytes, el espacio en bruto requerido es (2 * 2^32/8). Pero esto realmente podría convertirse en un algoritmo utilizable al convertirlo en una matriz dispersa. El pseudo-código muy seudo sería algo como esto:

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 "borrado (+ it_start mantener, it_stop);" desde dentro del ciclo while va a resultar en copiar los elementos restantes una y otra vez.

Sugiero intercambiar todos los elementos únicos en la parte delantera del vector, y luego borrar todos los elementos restantes a la vez.

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

fracasé miserablemente con mi primer intento, en el supuesto de que se mueve std::unique todos los duplicados en el extremo superior del rango (no lo hace). Oops. Aquí hay otro intento:

Aquí hay una implementación de not_unique.Elimina todos los elementos que aparecen solo una vez en el rango ordenado y duplicados de los elementos que aparecen más de una vez. El rango resultante es, por lo tanto, la lista única de elementos que aparecen más de una vez.

La función tiene complejidad lineal y hace una sola pasada sobre el rango (std::unique tiene complejidad lineal). It debe cumplir los requisitos de un iterador directo. Se devuelve el final del rango resultante.

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

Esto está en el estilo de la biblioteca estándar. ¡Crédito por el algoritmo goes to James! (Si me + 1, es mejor que 1 él, o de lo contrario ). Todo lo que hice fue hacer que el estilo de la biblioteca estándar:

#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

incluso se puede utilizar desajuste, para ganar puntos extra!
Por cierto: buen ejercicio.

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

Otra:

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

Esto corrige los errores en James McNellis's versión original. También proporciono versiones en el lugar y fuera de lugar.

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

¿Qué se entiende por "as efficient as std :: unique"? Eficiente en términos de tiempo de ejecución, tiempo de desarrollo, uso de memoria, ¿o qué?

Como otros señalaron, std :: única requiere una entrada ordenada, que no se ha proporcionado, así que no es una prueba justa para empezar.

Personalmente sólo tendría un std :: mapa hacer todo mi trabajo para mí. Tiene muchas propiedades que podemos usar para una máxima elegancia/brevedad. Mantiene sus elementos ya ordenados, y el operador [] insertará un valor cero si la clave aún no existe. Aprovechando esas propiedades, podemos hacer esto en dos o tres líneas de código, y aun así lograr una razonable complejidad de tiempo de ejecución.

Básicamente, mi algoritmo es la siguiente: Para cada elemento en el vector, se incrementan en una entrada de mapa de la tecleó por el valor de dicho elemento. Después, simplemente camine por el mapa, generando cualquier clave cuyo valor sea mayor que 1. No podría ser más simple.

#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 

Por lo tanto, nos visitan cada elemento del vector de una vez, y luego cada elemento en mi mapa una vez, donde el número de elementos en mi mapa es en el peor, no más grande que su vector. Los inconvenientes de mi solución son mucho más espacio de almacenamiento que las soluciones que implican reorganizar tu vector en el lugar. Las ventajas, sin embargo, son claras. Es increíblemente breve y simple, obviamente es correcto sin la necesidad de realizar muchas pruebas o revisar el código, y tiene propiedades de rendimiento razonables.

Haciendo mi función de una plantilla, y haciéndolo funcionar en STL-estilo va en lugar de sólo los vectores de enteros, se deja como ejercicio.