Скажем, у вас есть коллекция элементов, как вы можете выбрать те, у которых есть дубликаты, и поместить их в каждую группу с наименьшим количеством сравнений? желательно на C++, но алгоритм важнее языка. Например, учитывая {E1,E2,E3,E4,E4,E2,E6,E4,E3}, я хочу извлечь {E2,E2}, {E3,E3}, {E4,E4,E4}. какую структуру данных и алгоритм вы выберете? Пожалуйста, также укажите стоимость настройки структуры данных, скажем, если она предварительно отсортирована, например, std::multimap

Обновления

Чтобы было понятнее, как было предложено. есть одно ограничение: элементы должны сравниваться сами по себе, чтобы убедиться, что они дубликаты.

Таким образом, хэши не применяются, потому что фактически они смещают сравнение с тяжелых элементов (например, фрагментов данных) на легкие элементы (целые числа) и уменьшают некоторые сравнения, но не устраняют их, и, в конце концов, мы возвращаемся к наша исходная проблема, когда мы находимся внутри одного ведра столкновений.

Представьте, что у вас есть куча потенциально дублирующихся файлов по гигабайтам каждый, они имеют одно и то же значение хеш-функции для каждого алгоритма хэширования, известного людям. Теперь вы собираетесь обнаружить настоящие дубликаты.

Нет, это не может быть реальной проблемой (даже 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. these data structure prefer less-than operations to equal operations, they perform 2 less-than(a

Я не вижу, как это может сохранить сравнения.

еще одна вещь, которая игнорируется некоторыми ответами ниже, мне нужно отличать повторяющиеся группы друг от друга, а не просто хранить их в контейнере.

Вывод

После всего обсуждения кажется, что есть 3 пути

1. my original naive method as explained above
2. Начните с линейного контейнера, такого как std::vector , отсортируйте его, а затем найдите равные диапазоны.
3. начните с связанного контейнера, такого как std::map<Type, vector<duplicates>>, выберите дубликаты во время настройки связанного контейнера, как это было предложено Чарльзом Бейли.

Я закодировал образец для проверки всех методов, как указано ниже.

количество дубликатов и время их распространения могут повлиять на лучший выбор.

• Метод 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 -> sort() -> смежный_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 -> смежный_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);
}