t.g*_*.g. 22 c++ algorithm duplicate-data elements
假设您有一系列元素,如何选择具有重复元素的元素并将它们放入每组中并进行最少量的比较？最好是在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便宜,它的插入更便宜,不需要排序.)
弹出一个元素并将其与其余元素进行比较,如果找到重复元素,则将其从列表中拉出.一旦到达列表的末尾,就会找到一组重复,如果有的话.
重复上述两个步骤,直到列表为空.
在最好的情况下它需要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并不是更好,因为
我不知道如何保存比较.
下面的一些答案忽略了另一件事,我需要区分重复的组,而不是将它们保存在容器中.
在所有讨论之后,似乎有3种方式
std::vector,对其进行排序,然后找到相等的范围std::map<Type, vector<duplicates>>Charles Bailey所建议的那样,在相关容器的设置过程中挑选出重复的容器.我编写了一个样本来测试下面发布的所有方法.
重复数量以及分发时间可能会影响最佳选择.
一个输出,包含以下代码中的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 - > sort() - > adjacent_find():
比较:['<'= 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 - > adjacent_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);
}
der*_*ert 13
是的,你可以做得更好.
对它们进行排序(对于简单整数为O(n),一般为O(n*log n)),然后重复保证相邻,使得快速找到它们O(n)
使用哈希表,也是O(n).对于每个项目,(a)检查它是否已经在哈希表中; 如果是的话,它是重复的; 如果没有,请将其放入哈希表中.
您正在使用的方法似乎进行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
所以对于长度5你做4 + 3 + 2 + 1 = 10比较; 对于6你做15,等等(N ^ 2)/ 2 - N/2是准确的.对于任何合理的高N值,N*log(N)都较小.
在你的情况下,N有多大？
http://img188.imageshack.us/img188/7315/foou.png
至于减少散列冲突,最好的方法是获得更好的散列函数:-D.假设这是不可能的,如果你可以做一个变体(例如,不同的modulous),你可以做一个嵌套的哈希.
保持基于哈希表的结构从值到计数; 如果你的C++实现没有提供std::hash_map(到目前为止还没有真正的C++标准的一部分! - )使用Boost或从网上获取一个版本.对集合进行一次传递(即O(N))可以进行值 - >计数映射; 再一次通过哈希表(<= O(N),清楚地)来识别count> 1的值并适当地发出它们.总体O(N),这不是你的建议的情况.
您可以使用从代表性元素到其他元素的列表/向量/双端队列的映射。这在插入容器时需要相对较少的比较，并且意味着您可以迭代结果组而无需执行任何比较。
此示例始终将第一个代表性元素插入到映射的双端队列存储中，因为它使通过组的后续迭代在逻辑上变得简单，但如果这种重复证明存在问题，那么很容易只执行唯一push_back的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);
}
这样，遍历组就（相对）简单且便宜：
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
}
}
}
我进行了一些比较和对象计数的实验。在 100000 个对象按随机顺序形成 50000 个组（即每组平均 2 个对象）的测试中，上述方法花费以下数量的比较和副本：
1630674 comparisons, 443290 copies
（我尝试减少副本数量，但实际上只是以牺牲比较为代价，这在您的场景中似乎是成本较高的操作。）
使用多重映射，并在最终迭代中保留前一个元素来检测组转换，成本如下：
1756208 comparisons, 100000 copies
使用单个列表并弹出前面的元素并对其他组成员执行线性搜索的成本：
1885879088 comparisons, 100000 copies
是的，与我的最佳方法的 ~1.6m 相比，这大约是 1.9b 的比较。为了让列表方法执行接近最佳数量的比较，必须对它进行排序，这将花费与构建固有有序容器相似的比较次数。
编辑
我采用了您发布的代码，并在我之前使用的相同测试数据集上运行了隐含算法（我必须对代码做出一些假设，因为有一些假设的定义），并且我计算了：
1885879088 comparisons, 420939 copies
即与我的哑列表算法完全相同的比较次数，但具有更多副本。我认为这意味着我们在这种情况下使用本质上相似的算法。我看不到任何替代排序顺序的证据，但看起来您想要一个包含多个等效元素的组列表。Iterate这可以通过在我的函数中添加 inif (i->size > 1)子句来简单地实现。
我仍然看不到任何证据表明构建一个排序容器（例如这个双端队列映射）不是一个好的（即使不是最佳的）策略。