假设您有一组元素，您如何挑选出重复的元素并将它们放入每个组中以最少的比较？最好用 C++，但算法比语言更重要。例如给定 {E1,E2,E3,E4,E4,E2,E6,E4,E3}，我想提取 {E2,E2}, {E3,E3}, {E4,E4,E4}。你会选择什么数据结构和算法？还请包括设置数据结构的成本，例如，如果它是像 std::multimap 这样的预排序的
更新
按照建议使事情更清楚。有一个限制：元素必须自己比较才能确定它们是重复的。
所以哈希不适用，因为实际上它们将比较从重元素（例如数据块）转移到轻元素（整数），并减少了一些比较，但没有取消它们，最后，我们回到我们最初的问题是什么时候在一个碰撞桶内。
假设您有一堆潜在的 GB 重复文件，它们具有人类所知道的每种哈希算法相同的哈希值。现在您将发现真正的重复项。
不，这不可能是现实生活中的问题（即使 MD5 也足以为现实生活中的文件生成唯一的哈希）。但是只是假装这样我们就可以专注于找到涉及最少比较的数据结构+算法。
我正在做的是
表示成一个 STL std::list 数据结构（其中 1）它的元素删除比向量便宜 2）它的插入更便宜，不需要排序。）
弹出一个元素并将其与其余元素进行比较，如果发现重复，则将其从列表中拉出。一旦到达列表的末尾，就会发现一组重复项，如果有的话。
重复上述 2 个步骤，直到列表为空。
在最好的情况下它需要 N-1，但是 (N-1)！在最坏的情况下。
有什么更好的选择？
我的代码使用上面解释的方法：
// 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
};
};
感谢下面的回答，但是他们似乎被我的例子误导了，它是关于整数的。事实上，元素是类型不可知的（不一定是整数、字符串或任何其他 POD），并且相等的谓词是自定义的，即比较可能非常繁重。
所以也许我的问题应该是：使用哪种数据结构+算法涉及更少的比较。
根据我的测试，使用像 multiset 这样的预排序容器，multimap 并不好，因为
- 插入时的排序已经进行了比较，
- 以下相邻发现再次进行比较，
- 这些数据结构更喜欢小于操作而不是相等操作，它们执行 2 个小于（a
我看不出它如何保存比较。
下面的一些答案忽略了另一件事，我需要将重复的组彼此区分开来，而不仅仅是将它们保存在容器中。
结论
经过所有讨论，似乎有3种方法
- 我原来的天真方法如上所述
- 从线性容器开始
std::vector，对其进行排序，然后找到相等的范围 - 从关联容器开始，
std::map<Type, vector<duplicates>>如 Charles Bailey 所建议的，在关联容器的设置过程中挑选出重复项。
我编写了一个示例来测试下面发布的所有方法。
重复的数量和分布的时间可能会影响最佳选择。
- 方法 1 最好是在前面重重摔倒，最后最差。排序不会改变分布，而是字节序。
- 方法 3 的性能最平均
- 方法2永远不是最好的选择
感谢所有参与讨论的人。
一个输出包含以下代码中的 20 个示例项目。
用 [ 20 10 6 5 4 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1 ] 进行测试
和 [ 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 4 5 6 10 20 ]
使用 std::vector -> 排序（） -> 相邻查找（）：
比较：['<' = 139，'==' = 23]
比较：['<' = 38, '==' = 23]
使用 std::list -> sort() -> 收缩列表：
比较：['<' = 50, '==' = 43]
比较：['<' = 52, '==' = 43]
使用 std::list -> 缩小列表：
比较：['<' = 0, '==' = 121]
比较：['<' = 0, '==' = 43]
使用 std::vector -> std::map>:
比较：[ '<' = 79, '==' = 0 ]
比较：['<' = 53, '==' = 0]
使用 std::vector -> std::multiset ->相邻_find()：
比较：['<' = 79，'==' = 7]
比较：['<' = 53, '==' = 7]
代码
// 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);
}
