c++ - saber - ordenar numeros de un vector

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

Question

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

El primero usando 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 puedo, y por lo que puedo deducir al leer 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 enciende 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

¿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; simplemente 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 disponibilidad de memoria y CPU ...

Answer 2

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

Sin embargo, debería poder obtener un mejor caso mejor si lo marca mientras 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 tener el O(1) mejor caso, O(N log(N)) peor de los casos, y el promedio de casos depende de la distribución de las entradas.

Answer 3

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 clasifique 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 4

En el (muy) caso especial de clasificación de valores discretos con un valor máximo conocido, no demasiado grande. N.
Debería poder comenzar a organizar el depósito y simplemente verificar que el número de valores en cada depósito sea inferior a 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 5

La biblioteca estándar tiene std::unique , pero eso requeriría que hagas una copia de todo el contenedor (ten en cuenta que en ambos ejemplos también haces una copia del vector completo, ya que innecesariamente pasas 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 usar un std::set , como usted sabe, dependería :-).

Answer 6

Por un lado, podría combinar las ventajas de ambos: deje 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 señala que, en el caso genérico, es posible que desee evitar la copia de T, en cuyo caso puede usar un std::set<const T*, dereference_less> lugar.

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

Answer 7

Puede usar std::unique , pero requiere que el rango se ordene primero:

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 al final del conjunto único, por lo que si ese sigue siendo el final del 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 el uso de un C ++ 0x std::unordered_set lugar de std::set lo haría en el tiempo lineal esperado, pero eso requiere que tus elementos sean aptos para el hash y también tener operator == definido, 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, para que no haga una copia innecesaria del mismo.

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 en Sus elementos vectoriales. Ordénelo según el elemento señalado y luego verifique la exclusividad.

También puede usar std :: set para eso. La plantilla se ve así

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

Creo que puede proporcionar el parámetro de Rasgos apropiado e insertar punteros sin procesar para la velocidad o implementar una clase contenedora simple para punteros con <operador.

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

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

Al verificar el resultado (segundo miembro) a menudo puede detectar el duplicado mucho más rápido que si insertara todos los elementos.

Answer 9

Si puedo agregar mis propios 2 centavos.

En primer lugar, como comentó @Potatoswatter , a menos que sus elementos sean baratos de copiar (POD incorporados / pequeños), querrá usar 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, verifique si hay duplicados

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

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

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

Si podemos meternos con ellos, sugeriría mantener el vector ordenado: Loki::AssocVector debería Loki::AssocVector a comenzar. Si no es así, entonces debemos mantener un índice sobre la estructura para asegurar esta propiedad ... espere un minuto: ¿ Boost.MultiIndex para el rescate?

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

Si < ya está definido, entonces 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 tiempo (lo sé, necesitas un RandomAccessIterator, pero si T es Hashable, entonces es fácil tener a T* Hashable en;) )

Pero al final, el verdadero problema aquí es que nuestros consejos son genéricos necesarios porque nos faltan datos.

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

Answer 10

Su primer ejemplo debe ser O (N log N) ya que el set toma el tiempo N de registro 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é es 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 estilo STL,

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

Y si puedes 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 11

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.