c++ - repite - ¿Cuáles son los algoritmos rápidos para encontrar elementos duplicados en una colección y agruparlos?
mostrar numeros repetidos c++ (11)
¿Has probado la clasificación? Por ejemplo, usando un algoritmo como ordenar rápidamente? Si el rendimiento es lo suficientemente bueno para usted, entonces sería un enfoque fácil.
Digamos que tiene una colección de elementos, ¿cómo puede elegir aquellos con duplicados y ponerlos en cada grupo con la menor cantidad de comparación? preferiblemente en C ++, pero el algoritmo es más importante que el lenguaje. Para el ejemplo dado {E1, E2, E3, E4, E4, E2, E6, E4, E3}, deseo extraer {E2, E2}, {E3, E3}, {E4, E4, E4}. ¿Qué estructura de datos y algoritmo elegirás? Incluya también el costo de configuración de la estructura de datos, por ejemplo, si está predefinida como std :: multimap
Actualizaciones
Para aclarar las cosas como se sugiere. hay una restricción: los elementos deben compararse por sí mismos para estar seguros de que son duplicados.
Entonces, los hashes no se aplican, porque virtualmente cambian la comparación de elementos pesados (por ejemplo, fragmentos de datos) a elementos ligeros (enteros), y reducen algunas comparaciones, pero no las eliminan, y al final, volvemos a nuestro problema original, cuando estamos dentro de un cubo de colisión.
Imagina que tienes un montón de potenciales duplicando archivos de GB cada uno, tienen el mismo valor hash por cada algoritmo de hash que los seres humanos conocen. Ahora vas a ver los duplicados reales.
No, no puede ser un problema de la vida real (incluso MD5 es suficiente para generar hash único para archivos de la vida real). Pero solo finge que podemos enfocarnos en encontrar la estructura de datos + algoritmo que implique la menor cantidad de comparación .
Lo que estoy haciendo es
representar en una estructura de datos STL std :: list (en ese 1) su eliminación de elementos es más económica que, por ejemplo, un vector 2) su inserción es más barata, no requiere clasificación.)
sacar un elemento y compararlo con el resto, si se encuentra un duplicado, se saca de la lista. una vez que se llega al final de la lista, se encuentra un grupo de duplicación, si corresponde.
repita los 2 pasos anteriores hasta que la lista esté vacía.
¡Necesita N-1 en el mejor de los casos, pero (N-1)! en el peor de los casos
¿Cuáles son las mejores alternativas?
Mi código usando el método explicado arriba:
// algorithm to consume the std::list container,
// supports: list<path_type>,list< pair<std::string, paths_type::const_iterater>>
template<class T>
struct consume_list
{
groups_type operator()(list<T>& l)
{
// remove spurious identicals and group the rest
// algorithm:
// 1. compare the first element with the remaining elements,
// pick out all duplicated files including the first element itself.
// 2. start over again with the shrinked list
// until the list contains one or zero elements.
groups_type sub_groups;
group_type one_group;
one_group.reserve(1024);
while(l.size() > 1)
{
T front(l.front());
l.pop_front();
item_predicate<T> ep(front);
list<T>::iterator it = l.begin();
list<T>::iterator it_end = l.end();
while(it != it_end)
{
if(ep.equals(*it))
{
one_group.push_back(ep.extract_path(*(it))); // single it out
it = l.erase(it);
}
else
{
it++;
}
}
// save results
if(!one_group.empty())
{
// save
one_group.push_back(ep.extract_path(front));
sub_groups.push_back(one_group);
// clear, memory allocation not freed
one_group.clear();
}
}
return sub_groups;
}
};
// type for item-item comparison within a stl container, e.g. std::list
template <class T>
struct item_predicate{};
// specialization for type path_type
template <>
struct item_predicate<path_type>
{
public:
item_predicate(const path_type& base)/*init list*/
{}
public:
bool equals(const path_type& comparee)
{
bool result;
/* time-consuming operations here*/
return result;
}
const path_type& extract_path(const path_type& p)
{
return p;
}
private:
// class members
};
};
Gracias por la respuesta a continuación, sin embargo, parecen ser engañados por mi ejemplo de que se trata de enteros. De hecho, los elementos son de tipo agnóstico (no necesariamente enteros, cadenas o cualquier otro POD) , y los predicados iguales son autodefinidos, es decir, la comparación puede ser muy pesada .
Entonces, tal vez mi pregunta debería ser: usar qué estructura de datos + algoritmo implica menos comparaciones.
Utilizando un contenedor previamente clasificado como multiset, multimap no es mejor según mi prueba, ya que
- la clasificación al insertar ya hace las comparaciones,
- el siguiente hallazgo adyacente vuelve a hacer la comparación,
- Esta estructura de datos prefiere operaciones menores que las operaciones iguales, realizan 2 menos que (una
No veo cómo puede guardar comparaciones.
Una cosa más que es ignorada por algunas respuestas a continuación, necesito diferenciar los grupos duplicados entre sí, no solo mantenerlos en el contenedor.
Conclusión
Después de toda la discusión, parece haber 3 formas
- mi método ingenuo original como se explicó anteriormente
- Comience con un contenedor lineal como
std::vector, ordénelo y luego ubique los rangos iguales - comience con un contenedor asociado como
std::map<Type, vector<duplicates>>, seleccione los duplicados durante la configuración del contenedor asociado según lo sugerido por Charles Bailey.
He codificado una muestra para probar todos los métodos tal como se publica a continuación.
la cantidad de duplicados y cuándo se distribuyen pueden influir en la mejor elección.
- El Método 1 es mejor cuando caen pesadamente en el frente, y es peor cuando está al final. Sort no cambiará la distribución, pero endian.
- El método 3 tiene el rendimiento más promedio
- El método 2 nunca es la mejor opción
Gracias a todos los que participaron en la discusión.
una salida con 20 elementos de muestra del código a continuación.
Pruebe con [20 10 6 5 4 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1]
y [1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 4 5 6 10 20] respectivamente
usando std :: vector -> sort () -> adjacent_find ():
comparaciones: [''<'' = 139, ''=='' = 23]
comparaciones: [''<'' = 38, ''=='' = 23]
usando std :: list -> sort () -> shrink list:
comparaciones: [''<'' = 50, ''=='' = 43]
comparaciones: [''<'' = 52, ''=='' = 43]
usando std :: list -> shrink list:
comparaciones: [''<'' = 0, ''=='' = 121]
comparaciones: [''<'' = 0, ''=='' = 43]
usando std :: vector -> std :: map>:
comparaciones: [''<'' = 79, ''=='' = 0]
comparaciones: [''<'' = 53, ''=='' = 0]
usando std :: vector -> std :: multiset -> adjacent_find ():
comparaciones: [''<'' = 79, ''=='' = 7]
comparaciones: [''<'' = 53, ''=='' = 7]
Código
// compile with VC++10: cl.exe /EHsc
#include <vector>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <boost/foreach.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/format.hpp>
using namespace std;
struct Type
{
Type(int i) : m_i(i){}
bool operator<(const Type& t) const
{
++number_less_than_comparison;
return m_i < t.m_i;
}
bool operator==(const Type& t) const
{
++number_equal_comparison;
return m_i == t.m_i;
}
public:
static void log(const string& operation)
{
cout
<< "comparison during " <<operation << ": [ "
<< "''<'' = " << number_less_than_comparison
<< ", "
<< "''=='' = " << number_equal_comparison
<< " ]/n";
reset();
}
int to_int() const
{
return m_i;
}
private:
static void reset()
{
number_less_than_comparison = 0;
number_equal_comparison = 0;
}
public:
static size_t number_less_than_comparison;
static size_t number_equal_comparison;
private:
int m_i;
};
size_t Type::number_less_than_comparison = 0;
size_t Type::number_equal_comparison = 0;
ostream& operator<<(ostream& os, const Type& t)
{
os << t.to_int();
return os;
}
template< class Container >
struct Test
{
void recursive_run(size_t n)
{
bool reserve_order = false;
for(size_t i = 48; i < n; ++i)
{
run(i);
}
}
void run(size_t i)
{
cout <<
boost::format("/n/nTest %1% sample elements/nusing method%2%:/n")
% i
% Description();
generate_sample(i);
sort();
locate();
generate_reverse_sample(i);
sort();
locate();
}
private:
void print_me(const string& when)
{
std::stringstream ss;
ss << when <<" = [ ";
BOOST_FOREACH(const Container::value_type& v, m_container)
{
ss << v << " ";
}
ss << "]/n";
cout << ss.str();
}
void generate_sample(size_t n)
{
m_container.clear();
for(size_t i = 1; i <= n; ++i)
{
m_container.push_back(Type(n/i));
}
print_me("init value");
Type::log("setup");
}
void generate_reverse_sample(size_t n)
{
m_container.clear();
for(size_t i = 0; i < n; ++i)
{
m_container.push_back(Type(n/(n-i)));
}
print_me("init value(reverse order)");
Type::log("setup");
}
void sort()
{
sort_it();
Type::log("sort");
print_me("after sort");
}
void locate()
{
locate_duplicates();
Type::log("locate duplicate");
}
protected:
virtual string Description() = 0;
virtual void sort_it() = 0;
virtual void locate_duplicates() = 0;
protected:
Container m_container;
};
struct Vector : Test<vector<Type> >
{
string Description()
{
return "std::vector<Type> -> sort() -> adjacent_find()";
}
private:
void sort_it()
{
std::sort(m_container.begin(), m_container.end());
}
void locate_duplicates()
{
using std::adjacent_find;
typedef vector<Type>::iterator ITR;
typedef vector<Type>::value_type VALUE;
typedef boost::tuple<VALUE, ITR, ITR> TUPLE;
typedef vector<TUPLE> V_TUPLE;
V_TUPLE results;
ITR itr_begin(m_container.begin());
ITR itr_end(m_container.end());
ITR itr(m_container.begin());
ITR itr_range_begin(m_container.begin());
while(itr_begin != itr_end)
{
// find the start of one equal reange
itr = adjacent_find(
itr_begin,
itr_end,
[] (VALUE& v1, VALUE& v2)
{
return v1 == v2;
}
);
if(itr_end == itr) break; // end of container
// find the end of one equal reange
VALUE start = *itr;
while(itr != itr_end)
{
if(!(*itr == start)) break;
itr++;
}
results.push_back(TUPLE(start, itr_range_begin, itr));
// prepare for next iteration
itr_begin = itr;
}
}
};
struct List : Test<list<Type> >
{
List(bool sorted) : m_sorted(sorted){}
string Description()
{
return m_sorted ? "std::list -> sort() -> shrink list" : "std::list -> shrink list";
}
private:
void sort_it()
{
if(m_sorted) m_container.sort();////std::sort(m_container.begin(), m_container.end());
}
void locate_duplicates()
{
typedef list<Type>::value_type VALUE;
typedef list<Type>::iterator ITR;
typedef vector<VALUE> GROUP;
typedef vector<GROUP> GROUPS;
GROUPS sub_groups;
GROUP one_group;
while(m_container.size() > 1)
{
VALUE front(m_container.front());
m_container.pop_front();
ITR it = m_container.begin();
ITR it_end = m_container.end();
while(it != it_end)
{
if(front == (*it))
{
one_group.push_back(*it); // single it out
it = m_container.erase(it); // shrink list by one
}
else
{
it++;
}
}
// save results
if(!one_group.empty())
{
// save
one_group.push_back(front);
sub_groups.push_back(one_group);
// clear, memory allocation not freed
one_group.clear();
}
}
}
private:
bool m_sorted;
};
struct Map : Test<vector<Type>>
{
string Description()
{
return "std::vector -> std::map<Type, vector<Type>>" ;
}
private:
void sort_it() {}
void locate_duplicates()
{
typedef map<Type, vector<Type> > MAP;
typedef MAP::iterator ITR;
MAP local_map;
BOOST_FOREACH(const vector<Type>::value_type& v, m_container)
{
pair<ITR, bool> mit;
mit = local_map.insert(make_pair(v, vector<Type>(1, v)));
if(!mit.second) (mit.first->second).push_back(v);
}
ITR itr(local_map.begin());
while(itr != local_map.end())
{
if(itr->second.empty()) local_map.erase(itr);
itr++;
}
}
};
struct Multiset : Test<vector<Type>>
{
string Description()
{
return "std::vector -> std::multiset<Type> -> adjacent_find()" ;
}
private:
void sort_it() {}
void locate_duplicates()
{
using std::adjacent_find;
typedef set<Type> SET;
typedef SET::iterator ITR;
typedef SET::value_type VALUE;
typedef boost::tuple<VALUE, ITR, ITR> TUPLE;
typedef vector<TUPLE> V_TUPLE;
V_TUPLE results;
SET local_set;
BOOST_FOREACH(const vector<Type>::value_type& v, m_container)
{
local_set.insert(v);
}
ITR itr_begin(local_set.begin());
ITR itr_end(local_set.end());
ITR itr(local_set.begin());
ITR itr_range_begin(local_set.begin());
while(itr_begin != itr_end)
{
// find the start of one equal reange
itr = adjacent_find(
itr_begin,
itr_end,
[] (VALUE& v1, VALUE& v2)
{
return v1 == v2;
}
);
if(itr_end == itr) break; // end of container
// find the end of one equal reange
VALUE start = *itr;
while(itr != itr_end)
{
if(!(*itr == start)) break;
itr++;
}
results.push_back(TUPLE(start, itr_range_begin, itr));
// prepare for next iteration
itr_begin = itr;
}
}
};
int main()
{
size_t N = 20;
Vector().run(20);
List(true).run(20);
List(false).run(20);
Map().run(20);
Multiset().run(20);
}
La mayoría de las personas que mencionan soluciones de mapa hash / desordenadas están asumiendo O (1) inserción y tiempo de consulta, sin embargo, podría ser O (N) el peor caso. Además, anulas el costo del hash de objetos.
Personalmente insertaba objetos en un árbol binario (inserción O (logn) para cada uno), y mantengo el contador en cada nodo. Esto produciría O (nlogn) tiempo de construcción y O (n) recorrido para identificar todos los duplicados.
Lo más simple es, probablemente, ordenar la lista y luego iterar sobre ella buscando dúplex.
Si sabe algo sobre los datos, es posible utilizar algoritmos más eficientes.
Por ejemplo, si sabía que la lista era grande y solo contenía enteros de 1..n donde n es bastante pequeña, podría usar un par de matrices booleanas (o un mapa de bits) y hacer algo como esto:
bool[] once = new bool[MAXIMUM_VALUE];
bool[] many = new bool[MAXIMUM_VALUE];
for (int i = 0; i < list.Length; i++)
if (once[ value[i] ])
many[ value[i] ] = true;
else
once[ value[i] ] = true;
Ahora, muchos [] contienen una matriz cuyos valores se vieron más de una vez.
Mantenga una estructura basada en tablas hash del valor al recuento; si su implementación en C ++ no ofrece std::hash_map (¡que en realidad no forma parte del estándar de C ++ hasta ahora!), use Boost o obtenga una versión de la web. Un pase sobre la colección (es decir, O (N)) le permite hacer un mapeo value-> count; un pase más sobre la tabla hash (<= O (N), claramente) para identificar valores con un recuento> 1 y emitirlos de manera apropiada. En general O (N), que no es el caso para su sugerencia.
Sí, puedes hacerlo mucho mejor.
Ordénelos (O (n) para enteros simples, O (n * log n) en general), luego se garantiza que los duplicados serán adyacentes, lo que hace que encontrarlos sea rápido O (n)
Use una tabla hash, también O (n). Para cada elemento, (a) compruebe si ya está en la tabla hash; si es así, es un duplicado; si no, póngalo en la tabla hash.
editar
El método que está utilizando parece hacer comparaciones O (N ^ 2):
for i = 0; i < length; ++i // will do length times
for j = i+1; j < length; ++j // will do length-i times
compare
Entonces para la longitud 5 haces 4 + 3 + 2 + 1 = 10 compara; para 6 haces 15, etc. (N ^ 2) / 2 - N / 2 para ser exactos. N * log (N) es más pequeño, para cualquier valor razonablemente alto de N.
¿Qué tan grande es N en tu caso?
http://img188.imageshack.us/img188/7315/foou.png
En cuanto a la reducción de colisiones hash, la mejor manera es obtener una mejor función hash :-D. Suponiendo que no es posible, si puede hacer una variante (por ejemplo, diferente modulous), es posible que pueda hacer un hash anidado.
Si se sabe que es una lista de enteros, y si se sabe que todos están entre A y B (por ejemplo, A = 0, B = 9), haga una matriz de elementos BA y cree contenedores BA.
En el caso muy específico (lista de enteros simples), propongo que simplemente los cuentes, ya que no puedes distinguir diferentes enteros, de todos modos:
for(int i = 0; i < countOfNumbers; i++)
counter[number[i]]++;
Si son distinguibles, cree una matriz de listas y agréguelas a la lista correspondiente.
Si no son números, use std :: map o std :: hash_map, asignando claves a las listas de valores.
1. Clasifique la matriz O (n log n) en el peor - mergesort / heapsort / binary tree sort, etc.
2. Comparar a los vecinos y sacar las cerillas O (n)
Puede usar un mapa de un elemento representativo a una lista / vector / deque de otros elementos. Esto requiere comparaciones relativamente menores en la inserción en el contenedor y significa que puede iterar a través de los grupos resultantes sin tener que realizar ninguna comparación.
Este ejemplo siempre inserta el primer elemento representativo en el almacenamiento deque asignado, ya que hace que la iteración posterior a través del grupo sea lógicamente simple, pero si esta duplicación demuestra un problema, sería fácil realizar solo push_back solo if (!ins_pair.second) .
typedef std::map<Type, std::deque<Type> > Storage;
void Insert(Storage& s, const Type& t)
{
std::pair<Storage::iterator, bool> ins_pair( s.insert(std::make_pair(t, std::deque<Type>())) );
ins_pair.first->second.push_back(t);
}
Iterar a través de los grupos es entonces (relativamente) simple y barato:
void Iterate(const Storage& s)
{
for (Storage::const_iterator i = s.begin(); i != s.end(); ++i)
{
for (std::deque<Type>::const_iterator j = i->second.begin(); j != i->second.end(); ++j)
{
// do something with *j
}
}
}
Realicé algunos experimentos para comparación y recuento de objetos. En una prueba con 100000 objetos en orden aleatorio que forman 50000 grupos (es decir, un promedio de 2 objetos por grupo), el método anterior cuesta el siguiente número de comparaciones y copias:
1630674 comparisons, 443290 copies
(Intenté reducir el número de copias, pero solo logré hacerlo a expensas de las comparaciones que parecen ser las operaciones de mayor costo en su escenario).
Usar un multimapa y retener el elemento anterior en la iteración final para detectar las transiciones grupales le cuesta esto:
1756208 comparisons, 100000 copies
Usar una sola lista y hacer estallar el elemento frontal y realizar una búsqueda lineal para otros miembros del grupo cuesta:
1885879088 comparisons, 100000 copies
Sí, eso es ~ 1.9b comparaciones en comparación con ~ 1.6m para mi mejor método. Para hacer que el método de lista funcione en cualquier lugar cerca de un número óptimo de comparaciones, tendría que ser ordenado y esto costará una cantidad similar de comparaciones, ya que la construcción de un contenedor inherentemente ordenado lo haría en primer lugar.
Editar
Tomé su código publicado y ejecuté el algoritmo implícito (tuve que hacer algunas suposiciones sobre el código así como algunas definiciones asumidas) sobre el mismo conjunto de datos de prueba que utilicé antes y conté:
1885879088 comparisons, 420939 copies
es decir, exactamente el mismo número de comparaciones que mi algoritmo de lista tonta, pero con más copias. Creo que eso significa que usamos algoritmos esencialmente similares para este caso. No veo ninguna evidencia de un orden de clasificación alternativo, pero parece que desea una lista de los grupos que contienen más de un elemento equivalente. Esto se puede lograr simplemente en mi función Iterate agregando if (i->size > 1) cláusula if (i->size > 1) .
Todavía no puedo ver ninguna evidencia de que construir un contenedor clasificado como este mapa de deques no sea una estrategia buena (incluso si no es óptima).
Si entendí la pregunta correctamente, esta es la solución más simple que puedo pensar:
std::vector<T> input;
typedef std::vector<T>::iterator iter;
std::vector<std::pair<iter, iter> > output;
sort(input.begin(), input.end()); // O(n lg n) comparisons
for (iter cur = input.begin(); cur != input.end();){
std::pair<iter, iter> range = equal_range(cur, input.end(), *cur); // find all elements equal to the current one O(lg n) comparisons
cur = range.second;
output.push_back(range);
}
Tiempo total de ejecución: O(n log n) . Tiene un pase de clasificación O(n lg n) y luego un segundo pase donde se realizan las comparaciones O(lg n) para cada grupo (por lo que esto se hace a lo sumo n veces, también se obtiene O(n lg n) .
Tenga en cuenta que esto depende de que la entrada sea un vector. Solo los iteradores de acceso aleatorio tienen complejidad logarítmica en el segundo pase. Los iteradores bidireccionales serían lineales.
Esto no se basa en hash (como se solicita) y conserva todos los elementos originales (en lugar de solo devolver un elemento para cada grupo, junto con un recuento de la frecuencia con que se produjo).
Por supuesto, es posible una cantidad de optimizaciones constantes más pequeñas. output.reserve(input.size()) en el vector de salida sería una buena idea para evitar la reasignación. input.end() se toma con mucha más frecuencia de la necesaria y se puede almacenar fácilmente en caché.
Dependiendo de qué tan grandes se supone que son los grupos, equal_range puede no ser la opción más eficiente. Supongo que hace una búsqueda binaria para obtener la complejidad logarítmica, pero si cada grupo es solo un par de elementos, un escaneo lineal simple hubiera sido más rápido. En cualquier caso, la clasificación inicial domina el costo sin embargo.
Solo para registrar que tuve el mismo problema durante la normalización de una tienda triple con la que estoy trabajando. Implementé el método 3, resumido por Charles Bailey, en Common Lisp usando la función de tabla hash de Allegro Common Lisp.
La función "agente-igual?" se usa para probar cuando dos agentes en el TS son iguales. La función "merge-nodes" fusiona los nodos en cada clúster. En el siguiente código, el "..." se usó para eliminar las partes no tan importantes.
(defun agent-equal? (a b)
(let ((aprops (car (get-triples-list :s a :p !foaf:name)))
(bprops (car (get-triples-list :s b :p !foaf:name))))
(upi= (object aprops) (object bprops))))
(defun process-rdf (out-path filename)
(let* (...
(table (make-hash-table :test ''agent-equal?)))
(progn
...
(let ((agents (mapcar #''subject
(get-triples-list :o !foaf:Agent :limit nil))))
(progn
(dolist (a agents)
(if (gethash a table)
(push a (gethash a table))
(setf (gethash a table) (list a))))
(maphash #''merge-nodes table)
...
)))))
Desde C ++ 11, las tablas hash son provistas por el STL con std :: unordered_map . Entonces, una solución O (N) es poner sus valores en un unordered_map< T, <vector<T> > .