quels sont les algorithmes rapides pour trouver les éléments en double dans une collection et de les regrouper?

Dire que vous avez une collection d'éléments, comment pouvez-vous choisir ceux avec les doublons et de les mettre dans chaque groupe avec au moins le montant de la comparaison? de préférence en C++, mais l'algorithme est plus important que la langue.
Par Exemple
compte tenu de {E1,E2,E3,E4,E4,E2,E6,E4,E3}, je souhaite extraire de {E2,E2}, {E3,E3}, {E4,E4,E4}.
quelle structure de données et algorithme de vous choisir? Veuillez également inclure le coût de la création de la structure de données, dites, si c'est un pré-triés un comme std::multimap

Mises à jour

Pour rendre les choses plus claires comme le suggère. il y a une contrainte: les éléments doivent être comparés par eux-mêmes pour être certains qu'ils sont des doublons.

Donc hachages ne s'applique pas, puisque la quasi-ils passer à la comparaison à partir d'éléments lourds(par exemple, des blocs de données) à la lumière des éléments(des entiers), et de réduire certains de comparaison, mais pas les faire disparaître, et à la fin, nous sommes de retour à notre problème, lorsque vous êtes à l'intérieur d'une collision de seau.

Imaginez que vous avez un tas de potentiels de dupliquer les fichiers de l'Abg chaque, ils portent la même valeur de hachage par tous les hash-algorithme de l'homme connaît. Maintenant, vous allez repérer les doublons réels.

Non, il ne peut pas être un problème de la vie réelle(même MD5 est suffisant pour générer de hachage unique pour la vie réelle des fichiers). Mais juste faire semblant, de sorte que nous pouvons accent sur la recherche de la structure de données + algorithme qui implique moins de comparaison.

---

Ce que je fais est de

1. représenter dans un STL std::list structure de données(1) de son élément de suppression est moins cher que, disons, un vecteur 2) son insertion est moins cher, ne nécessitant pas de tri.)

2. pop sur un élément et de le comparer avec le reste, si un double est trouvé, il est sorti de la liste. une fois à la fin de la liste est atteinte, un groupe de duplication est trouvé, le cas échéant.

3. répéter ces 2 étapes jusqu'à ce que la liste est vide.

Il a besoin de N-1 dans le meilleur des cas, mais (N-1)! dans le pire des cas.

quelles sont les meilleures solutions?

---

Mon code à l'aide de la méthode expliquée ci-dessus:

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

---

Merci pour la réponse ci-dessous, cependant, ils semblent être induits en erreur par mon exemple que c'est sur les entiers. En fait les éléments sont de type agnostique(pas nécessairement des entiers, des chaînes ou toute autre Gousses), et de l'égalité des prédicats sont définis soi-même, c'est-à la comparaison peut être très lourd.

Peut-être que ma question devrait être: à l'aide de lequel la structure de données + algorithme implique moins de comparaisons.

À l'aide d'un pré-triés récipient comme multiset, multimap n'est pas mieux en fonction de mon test, depuis

1. le tri, tout en insérant déjà fait les comparaisons,
2. suivantes adjacents conclusion n'comparaison encore,
3. ces données structure préfèrent moins que les opérations de l'égalité des opérations qu'ils effectuent 2 moins-que(un

Je ne vois pas comment il peut sauver des comparaisons.

---

une chose de plus qui est ignoré par les quelques réponses ci-dessous, j'ai besoin de différencier les dupliquer les groupes les uns des autres, de ne pas les garder dans le conteneur.

---

Conclusion

Après tout, la discussion, il semble y avoir 3 façons

1. mon original à la méthode naïve comme expliqué ci-dessus
2. Commencer avec un linéaire récipient comme std::vector , à les trier, puis recherchez l'égalité des plages de
3. commencer avec un conteneur associé comme std::map<Type, vector<duplicates>>, choisir les doublons lors de la configuration de conteneur associé, tel que suggéré par Charles Bailey.

J'ai codé un échantillon à tester toutes les méthodes comme affiché ci-dessous.

le nombre de doublons et lorsqu'ils sont distribués peuvent influencer le meilleur choix.

• La méthode 1 est meilleur quand ils tombent lourdement sur le devant, et est pire quand à la fin. Tri pas de changement de la distribution, mais la endian.
• Méthode 3 a le plus de rendement moyen
• La méthode 2 est jamais le meilleur choix

Merci pour tous ceux qui participent à la discussion.

une sortie avec 20 éléments de l'échantillon à partir du code ci-dessous.

Test avec [ 20 10 6 5 4 3 2 2 2 2 1
1 1 1 1 1 1 1 1 1 ]

et [ 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3
4 5 6 10 20 ] respectivement

en utilisant std::vector -> type() ->
adjacent_find():

comparaisons: ["<' = 139, '==' = 23
]

comparaisons: ["<' = 38, '==' = 23 ]

en utilisant std::list -> type() -> shrink
liste:

comparaisons: ["<' = 50, '==' = 43 ]

comparaisons: ["<' = 52, '==' = 43 ]

en utilisant std::list -> rétrécir liste:

comparaisons: ["<' = 0, '==' = 121 ]

comparaisons: ["<' = 0, '==' = 43 ]

en utilisant std::vector -> std::map>:

comparaisons: ["<' = 79, '==' = 0 ]

comparaisons: ["<' = 53, '==' = 0 ]

en utilisant std::vector ->
std::multiset ->
adjacent_find():

comparaisons: ["<' = 79, '==' = 7 ]

comparaisons: ["<' = 53, '==' = 7 ]

Code

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