相关疑难解决方法(0)

假设您有一系列元素,如何选择具有重复元素的元素并将它们放入每组中并进行最少量的比较？最好是在C++中,但算法比语言更重要.对于给出{E1,E2,E3,E4,E4,E2,E6,E4,E3}的示例,我希望提取出{E2,E2},{E3,E3},{E4,E4,E4}.您将选择哪种数据结构和算法？还请包括设置数据结构的成本,例如,它是否是像std :: multimap这样的预先排序的数据结构

更新

根据建议使事情更清楚.有一个约束:元素必须自己进行比较,以确定它们是重复的.

所以哈希不适用,因为实际上他们将比较从重元素(例如数据块)转移到轻元素(整数),并减少一些比较,但不要废除它们,最后,我们又回到了我们原来的问题,什么时候在一个碰撞桶内.

假装你有一堆潜在的GB重复文件,它们与人类所知的每个哈希算法具有相同的哈希值.现在你要发现真正的重复.

不,它不能成为现实生活中的问题(即使MD5足以为现实生活中的文件生成唯一的哈希值).但只是假装我们可以专注于寻找涉及最少量比较的数据结构+算法.

我正在做的是

1. 代表一个STL std :: list数据结构(在那个1中)它的元素删除比例如矢量2便宜,它的插入更便宜,不需要排序.)

2. 弹出一个元素并将其与其余元素进行比较,如果找到重复元素,则将其从列表中拉出.一旦到达列表的末尾,就会找到一组重复,如果有的话.

3. 重复上述两个步骤,直到列表为空.

在最好的情况下它需要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 …