23

假设您有一组元素,您如何挑选出重复的元素并将它们放入每个组中以最少的比较?最好用 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. 重复上述 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 并不好,因为

  1. 插入时的排序已经进行了比较,
  2. 以下相邻发现再次进行比较,
  3. 这些数据结构更喜欢小于操作而不是相等操作,它们执行 2 个小于(a

我看不出它如何保存比较。


下面的一些答案忽略了另一件事,我需要将重复的组彼此区分开来,而不仅仅是将它们保存在容器中。


结论

经过所有讨论,似乎有3种方法

  1. 我原来的天真方法如上所述
  2. 从线性容器开始std::vector,对其进行排序,然后找到相等的范围
  3. 从关联容器开始,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);
}
4

11 回答 11

13

是的,你可以做得更好。

  1. 对它们进行排序(对于简单整数 O(n),通常为 O(n*log n)),然后保证重复项是相邻的,从而快速找到它们 O(n)

  2. 使用哈希表,也是 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 有多大?

就减少哈希冲突而言,最好的方法是获得更好的哈希函数:-D。假设这是不可能的,如果你可以做一个变体(例如,不同的模数),你也许可以做一个嵌套散列。

于 2009-08-26T05:38:24.603 回答
7

1. 对数组进行最坏的排序 O(n log n) - 归并排序/堆排序/二叉树排序等

2. 比较邻居并将匹配项拉出 O(n)

于 2009-08-26T05:38:14.370 回答
5

保持从值到计数的基于哈希表的结构;如果你的 C++ 实现不提供std::hash_map(到目前为止还不是 C++ 标准的一部分!-)使用 Boost 或从网上获取一个版本。一次遍历集合(即 O(N))让您可以进行值-> 计数映射;再次遍历哈希表(<= O(N),显然)以识别计数 > 1 的值并适当地发出它们。总体 O(N),这不是你的建议的情况。

于 2009-08-26T05:38:56.367 回答
3

您可以使用从代表元素到其他元素的列表/向量/双端队列的映射。这需要在插入容器时进行相对较少的比较,这意味着您可以遍历结果组而无需执行任何比较。

push_back这个例子总是将第一个代表元素插入到映射的双端队列存储中,因为它使得通过组的后续迭代在逻辑上很简单,但是如果这种重复证明有问题,那么只执行only就很容易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
        }
    }
}

我进行了一些比较和对象计数的实验。在以随机顺序形成 50000 个组(即平均每组 2 个对象)的 100000 个对象的测试中,上述方法花费了以下数量的比较和副本:

1630674 comparisons, 443290 copies

(我尝试减少副本的数量,但只是以牺牲比较为代价才真正做到了,这在您的场景中似乎是成本较高的操作。)

使用多重映射,并在最终迭代中保留前一个元素以检测组转换,成本如下:

1756208 comparisons, 100000 copies

使用单个列表并弹出最前面的元素并对其他组成员执行线性搜索成本:

1885879088 comparisons, 100000 copies

是的,这是~1.9b 的比较,而我最好的方法是~1.6m。为了让 list 方法在接近最佳比较次数的任何地方执行,它必须进行排序,这将花费与构建固有有序容器类似的比较次数。

编辑

我拿了你发布的代码并在我之前使用的相同测试数据集上运行了隐含算法(我必须对代码做出一些假设,因为那里有一些假设的定义),我计算了:

1885879088 comparisons, 420939 copies

即与我的哑列表算法完全相同的比较次数,但有更多副本。我认为这意味着我们在这种情况下使用基本相似的算法。我看不到任何替代排序顺序的证据,但看起来您想要一个包含多个等效元素的组列表。这可以Iterate通过添加 inif (i->size > 1)子句在我的函数中简单地实现。

我仍然看不到任何证据表明构建排序容器(例如此 deques 映射)不是一个好的(即使不是最佳的)策略。

于 2009-08-26T08:39:33.677 回答
1

你试过排序吗?例如使用快速排序之类的算法?如果性能对您来说足够好,那么这将是一个简单的方法。

于 2009-08-26T05:38:34.557 回答
1

最简单的可能是对列表进行排序,然后遍历它以查找重复项。

如果您对数据有所了解,则可以使用更有效的算法。

例如,如果您知道列表很大,并且只包含 1..n 中的整数,其中 n 相当小,您可以使用一对布尔数组(或位图),并执行以下操作:

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;

现在, many[] 包含一个数组,其中的值被多次看到。

于 2009-08-26T05:39:41.183 回答
1

如果已知它是一个整数列表,并且如果已知它们都在 A 和 B 之间(例如 A=0,B=9),则制作一个 BA 元素数组,并创建 BA 容器。

在非常特殊的情况下(普通整数列表),我建议您只计算它们,因为无论如何您无法区分不同的整数:

for(int i = 0; i < countOfNumbers; i++)
    counter[number[i]]++;

如果它们可区分的,则创建一个列表数组,并将它们添加到相应的列表中。

如果它们不是数字,则使用 std::map 或 std::hash_map,将键映射到值列表。

于 2009-08-26T05:40:31.697 回答
1

从 C++11 开始,散列表由 STL 提供,带有std::unordered_map。因此,O(N) 解决方案是将您的值放入unordered_map< T, <vector<T> >.

于 2016-05-26T21:34:53.050 回答
0

大多数提到哈希/无序映射解决方案的人都假设插入和查询时间为 O(1),但最坏的情况可能是 O(N)。此外,您可以避免对象散列的成本。

就我个人而言,我会将对象插入二叉树(每个都插入 O(logn)),并在每个节点处保留计数器。这将产生 O(nlogn) 构造时间和 O(n) 遍历来识别所有重复项。

于 2009-08-26T06:17:42.747 回答
0

如果我正确理解了这个问题,那么这是我能想到的最简单的解决方案:

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

总运行时间:O(n log n). 您有一个排序通道O(n lg n),然后是第二个通道,其中对每个组O(lg n)执行比较(因此大多数时候都会这样做,也会产生. nO(n lg n)

请注意,这取决于输入是向量。只有随机访问迭代器在第二遍中具有对数复杂度。双向迭代器将是线性的。

这不依赖于散列(根据要求),它保留了所有原始元素(而不是只为每个组返回一个元素,以及它发生的频率)。

当然,一些较小的常数优化也是可能的。output.reserve(input.size())在输出向量上将是一个好主意,以避免重新分配。input.end()被占用的次数也比必要的多得多,并且可以很容易地被缓存。

根据假设的组有多大,equal_range可能不是最有效的选择。我假设它会进行二进制搜索以获得对数复杂度,但如果每个组只有几个元素,那么简单的线性扫描会更快。在任何情况下,初始排序都占主导地位。

于 2009-08-27T10:06:47.217 回答
0

只是为了注册在我正在使用的三重商店的规范化过程中我遇到了同样的问题。我使用 Allegro Common Lisp 的哈希表功能在 Common Lisp 中实现了由 Charles Bailey 总结的方法 3。

函数“代理相等?” 用于测试 TS 中的两个代理何时相同。功能“合并节点”合并每个集群上的节点。在下面的代码中,“...”用于删除不那么重要的部分。

(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)
           ...
           )))))
于 2011-06-13T00:48:10.847 回答