Determinar si un vector no ordenado <T> tiene todos los elementos únicos

Question

Hacer un perfil de mi código CPU-bound me ha sugerido pasar mucho tiempo comprobando si un contenedor contiene elementos completamente únicos. Suponiendo que tengo algo de gran contenedor de elementos sin ordenar (con < y = definido), tengo dos ideas sobre cómo se puede hacer esto:

El primero utilizando un conjunto:

template <class T> 
bool is_unique(vector<T> X) { 
    set<T> Y(X.begin(), X.end()); 
    return X.size() == Y.size(); 
} 

El segundo bucle sobre los elementos:

template <class T> 
bool is_unique2(vector<T> X) { 
    typename vector<T>::iterator i,j; 
    for(i=X.begin();i!=X.end();++i) { 
    for(j=i+1;j!=X.end();++j) { 
     if(*i == *j) return 0; 
    } 
    } 
    return 1; 
} 

los he probado lo mejor que pueda, y de lo que se desprende de la lectura de la documentación sobre STL, la respuesta es (como de costumbre), depende. Creo que en el primer caso, si todos los elementos son únicos, es muy rápido, pero si hay una gran degeneración, la operación parece tomar O (N^2) tiempo. Para el enfoque de iterador anidado, lo opuesto parece ser cierto, se ilumina rápidamente si X[0]==X[1] pero toma (comprensiblemente) O (N^2) tiempo si todos los elementos son únicos.

¿Hay una mejor manera de hacerlo, quizás un algoritmo STL creado para este propósito? Si no es así, ¿hay alguna sugerencia que permita un poco más de eficiencia?

Answer 1

Su primer ejemplo debe ser O (N log N) como set toma el registro N hora para cada inserción. No creo que una O más rápida sea posible.

El segundo ejemplo es obviamente O (N^2). El coeficiente y el uso de memoria son bajos, por lo que puede ser más rápido (o incluso más rápido) en algunos casos.

Depende de qué sea T, pero para un rendimiento genérico, recomendaría ordenar un vector de punteros a los objetos.

template< class T > 
bool dereference_less(T const *l, T const *r) 
{ return *l < *r; } 

template <class T> 
bool is_unique(vector<T> const &x) { 
    vector< T const * > vp; 
    vp.reserve(x.size()); 
    for (size_t i = 0; i < x.size(); ++ i) vp.push_back(&x[i]); 
    sort(vp.begin(), vp.end(), ptr_fun(&dereference_less<T>)); // O(N log N) 
    return adjacent_find(vp.begin(), vp.end(), 
      not2(ptr_fun(&dereference_less<T>))) // "opposite functor" 
     == vp.end(); // if no adjacent pair (vp_n,vp_n+1) has *vp_n < *vp_n+1 
} 

o en el estilo de STL,

template <class I> 
bool is_unique(I first, I last) { 
    typedef typename iterator_traits<I>::value_type T; 
    … 

---

Y si se puede reordenar el vector original, por supuesto,

template <class T> 
bool is_unique(vector<T> &x) { 
    sort(x.begin(), x.end()); // O(N log N) 
    return adjacent_find(x.begin(), x.end()) == x.end(); 
} 

Answer 2

La biblioteca estándar tiene std::unique, pero eso requeriría que haga una copia de todo el contenedor (tenga en cuenta que en ambos ejemplos también hace una copia del vector completo, ya que innecesariamente pasa el vector por valor)

template <typename T> 
bool is_unique(std::vector<T> vec) 
{ 
    std::sort(vec.begin(), vec.end()); 
    return std::unique(vec.begin(), vec.end()) == vec.end(); 
} 

si esto sería más rápido que el uso de un std::set habría, como es sabido, dependerá :-).

Answer 3

¿No es factible usar un contenedor que brinde esta "garantía" desde el primer momento? ¿Sería útil marcar un duplicado en el momento de la inserción en lugar de hacerlo en el futuro? Cuando he querido hacer algo como esto, esa es la dirección que he seguido; solo usando el conjunto como el contenedor "primario", y tal vez construyendo un vector paralelo si necesitaba mantener el orden original, pero por supuesto eso hace algunas suposiciones sobre la memoria y la disponibilidad de la CPU ...

Answer 4

Por una cosa que podrías combinar las ventajas de ambos: dejar de construir el conjunto, si ya ha descubierto un duplicado:

template <class T> 
bool is_unique(const std::vector<T>& vec) 
{ 
    std::set<T> test; 
    for (typename std::vector<T>::const_iterator it = vec.begin(); it != vec.end(); ++it) { 
     if (!test.insert(*it).second) { 
      return false; 
     } 
    } 
    return true; 
} 

por cierto, Potatoswatter hace un buen punto de que, en el caso genérico es posible que desee evitar copiar T, en cuyo caso se podría usar un std::set<const T*, dereference_less> en su lugar.

---

Por supuesto, podría hacerlo mucho mejor si no fuera genérico. Por ejemplo, si tuviera un vector de números enteros de rango conocido, podría simplemente marcar en una matriz (o incluso conjunto de bits) si existe un elemento.

Answer 5

Puede utilizar std::unique, pero requiere el rango que ser resuelto en primer lugar:

template <class T> 
bool is_unique(vector<T> X) { 
    std::sort(X.begin(), X.end()); 
    return std::unique(X.begin(), X.end()) == X.end(); 
} 

std::unique modifica la secuencia y devuelve un iterador hasta el final de la serie única, así que si eso es todavía el final de la vector entonces debe ser único.

Esto se ejecuta en nlog (n); lo mismo que su ejemplo establecido.No creo que teóricamente puedas garantizar que lo hagas más rápido, aunque usar un C++ 0x std::unordered_set en lugar de std::set lo haría en el tiempo lineal esperado, pero eso requiere que tus elementos sean aptos para el hash y tengan operator == definidos, lo que podría no será tan fácil

Además, si no está modificando el vector en sus ejemplos, mejoraría el rendimiento pasándolo por referencia constante, por lo que no hace una copia innecesaria de él.

Answer 6

Bueno, el primero sólo debe tener N log(N) , por lo que es claramente el peor escenario posible para esta aplicación.

Sin embargo, usted debería ser capaz de obtener un mejor de los casos mejor si se comprueba a medida que agrega cosas al conjunto:

template <class T> 
bool is_unique3(vector<T> X) { 
    set<T> Y; 
    typename vector<T>::const_iterator i; 
    for(i=X.begin(); i!=X.end(); ++i) { 
    if (Y.find(*i) != Y.end()) { 
     return false; 
    } 
    Y.insert(*i); 
    } 
    return true; 
} 

Esto debería haber O(1) mejor de los casos, O(N log(N)) peor de los casos, y el promedio de los casos depende de la distribución de las entradas.

Answer 7

Debe ordenar el vector si desea determinar rápidamente si solo tiene elementos únicos. De lo contrario, lo mejor que puede hacer es el tiempo de ejecución O (n^2) o el tiempo de ejecución O (n log n) con O (n) espacio. Creo que es mejor escribir una función que asuma que la entrada está ordenada.

template<class Fwd> 
bool is_unique(In first, In last) 
{ 
    return adjacent_find(first, last) == last; 
} 

luego haga que el cliente ordene el vector, o haga una copia ordenada del vector. Esto abrirá una puerta para la programación dinámica. Es decir, si el cliente clasificó el vector en el pasado, entonces tienen la opción de guardar y referirse a ese vector ordenado para que puedan repetir esta operación durante el tiempo de ejecución O (n).

Answer 8

Si el tipo T que almacena en Su vector es grande y copiarlo es costoso, considere la posibilidad de crear un vector de punteros o iteradores para Sus elementos de vector. Ordénelo según el elemento señalado y luego verifique la exclusividad.

También puede usar std :: set para eso. La plantilla se parece a esto

template <class Key,class Traits=less<Key>,class Allocator=allocator<Key> > class set 

Creo que se puede proporcionar rasgos apropiados parámetro e insertar punteros primas para la velocidad o implementar una clase de contenedor simple para los punteros con < operador.

No utilice el constructor para insertarlo en el conjunto. Use el método de inserción.El método (una de las sobrecargas) tiene una firma

pair <iterator, bool> insert(const value_type& _Val); 

Al marcar el resultado (segundo miembro) A menudo se puede detectar el duplicado mucho más rápido, que si ha insertado todos los elementos.

Answer 9

Usando los contenedores estándar actuales de C++, tiene una buena solución en su primer ejemplo. Pero si puede usar un contenedor hash, es posible que pueda hacerlo mejor, ya que el conjunto hash será n O (1) en lugar de n O (log n) para un conjunto estándar. Por supuesto, todo dependerá del tamaño de ny de la implementación particular de su biblioteca.

Answer 10

En el caso (muy) especial de clasificación de valores discretos con un valor máximo conocido, no demasiado grande N.
Debería poder comenzar una clasificación de depósito y simplemente verificar que el número de valores en cada cubo debajo 2.

bool is_unique(const vector<int>& X, int N) 
{ 
    vector<int> buckets(N,0); 
    typename vector<int>::const_iterator i; 
    for(i = X.begin(); i != X.end(); ++i) 
    if(++buckets[*i] > 1) 
     return false; 
    return true; 
} 

La complejidad de esto sería O (n).

Answer 11

Si puedo agregar mis 2 centavos.

En primer lugar, como @Potatoswatter comentó, a menos que sus elementos sean baratos de copiar (POD incorporados/pequeños) querrá utilizar punteros a los elementos originales en lugar de copiarlos.

En segundo lugar, hay 2 estrategias disponibles.

1. Simplemente asegúrese de que no haya ningún duplicado insertado en primer lugar. Esto significa, por supuesto, controlar la inserción, que generalmente se logra creando una clase dedicada (con el vector como atributo).
2. Siempre que se necesite la propiedad, la verificación de duplicados

Debo admitir que me inclinaría hacia la primera. Encapsulación, clara separación de responsabilidades y todo eso.

De todos modos, hay varias maneras dependiendo de los requisitos. La primera pregunta es:

• ¿tenemos que dejar los elementos en el vector en un orden particular o podemos "meternos" con ellos?

Si podemos jugar con ellos, sugeriría mantener el vector ordenados: Loki::AssocVector debe empezar. Si no es así, entonces necesitamos mantener un índice sobre la estructura para asegurar esta propiedad ... espere un minuto: Boost.MultiIndex al rescate?

En tercer lugar: como usted mismo comentó, una búsqueda lineal simple duplicada produce una O (N) complejidad en promedio que no es buena.

Si < ya está definido, la clasificación es obvia, con su complejidad O (N log N). También podría valer la pena hacer T Hashable, porque un std::tr1::hash_set podría producir un mejor momento (lo sé, se necesita un RandomAccessIterator, pero si T es Hashable entonces es fácil tener T* Hashable a;))

Pero Al final, el verdadero problema aquí es que nuestros consejos son genéricos necesarios porque carecemos de datos.

• ¿Qué significa T? ¿Pretende que el algoritmo sea genérico?
• ¿Cuál es el número de elementos? 10, 100, 10.000, 1.000.000? Debido a que la complejidad asintótica es bastante discutible cuando se trata de unos pocos cientos ...
• Y, por supuesto, ¿se puede garantizar la uniformidad en el momento de la inserción? ¿Puedes modificar el vector en sí?