35 votos

La determinación de si una desordenada vector<T> tiene todos los elementos únicos

Perfiles de mi cpu tiene el código me sugirió que pasar mucho tiempo para comprobar si un recipiente contiene completamente los elementos únicos. Suponiendo que tengo algo de gran contenedor de sin clasificar elementos (con < y = definido), tengo dos ideas sobre cómo se podría hacer esto:

El primer uso de 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;
}

He probado lo mejor que puedo, y de lo que he entendido de la lectura de la documentación acerca de la 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 de la operación parece tomar O(N^2) tiempo. Para el anidado de iterador enfoque de lo contrario parece ser cierto, es rápida de iluminación si X[0]==X[1] pero toma (comprensiblemente) O(N^2) tiempo si todos los elementos son únicos.

Hay una mejor manera de hacer esto, tal vez un STL algoritmo construido para este fin? Si no, ¿hay alguna de las sugerencias que buscan un poco más de eficiencia?

27voto

Potatoswatter Puntos 70305

Su primer ejemplo debe ser O(N log N) set toma de registro N de tiempo para cada inserción. No creo que un más rápido O es posible.

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

Depende de lo T , pero para los genéricos de rendimiento, me gustaría recomendar la ordenación de 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 STL estilo,

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

9voto

wilhelmtell Puntos 25504

Se debe ordenar el vector si desea determinar rápidamente si sólo tiene elementos únicos. De lo contrario, lo mejor que puedes hacer es O(n^2) tiempo de ejecución es O(n log n) tiempo de ejecución con O(n) en el espacio. Creo que es mejor escribir una función que supone la entrada está ordenada.

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

a continuación, el cliente ordenar el vector, o hacer una ordenados copia del vector. Esto abrirá una puerta para programación dinámica. Es decir, si el cliente ordena el vector en el pasado, entonces ellos tienen la opción de mantener y se refieren a que ordenan vector, de modo que se pueda repetir esta operación O(n) tiempo de ejecución.

6voto

James McNellis Puntos 193607

La biblioteca estándar de ha std::unique, pero que se requieren para hacer una copia de todo el contenedor (tenga en cuenta que en los dos ejemplos que hacer una copia de todo el vector, ya que innecesariamente pasar el vector por el 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 usando un std::set , como usted sabe, dependen :-).

6voto

dash-tom-bang Puntos 9384

Es factible usar un contenedor que ofrece esta "garantía" desde el principio? Sería útil para marcar un duplicado en el momento de la inserción, en lugar de en algún momento en el futuro? Cuando he querido hacer algo como esto, que es la dirección en la que he ido; sólo mediante el conjunto como el "principal" de contenedor, y tal vez la construcción de un vector paralelo si me necesitan para mantener el orden original, pero por supuesto que hace algunas suposiciones acerca de la memoria y de la CPU disponibilidad...

6voto

UncleBens Puntos 24580

Para una cosa que usted podría combinar las ventajas de ambos: dejar de construir el conjunto, si usted 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 que en el caso genérico puede evitar la copia de T, en cuyo caso se podría usar la std::set<const T*, dereference_less> lugar.


Por supuesto podría potencialmente hacer mucho mejor si no fuera genérico. E. g si había un vector de enteros de rango, sólo pudo marcar en una matriz (o incluso bitset) si un elemento existe.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X