Скажем, у вас есть набор элементов, как вы можете выбрать элементы с дубликатами и поместить их в каждую группу с наименьшим количеством сравнений? желательно на C ++, но алгоритм важнее языка.
Например
учитывая {E1, E2, E3, E4, E4, E2, E6, E4, E3}, я хочу извлечь {E2, E2}, {E3, E3}, {E4, E4, E4}.
какую структуру данных и алгоритм вы выберете? Также укажите стоимость настройки структуры данных, скажем, если она предварительно отсортирована, например std :: multimap
Обновление
Чтобы сделать вещи понятнее, как предложено. есть одно ограничение: элементы должны сравниваться сами по себе , чтобы убедиться, что они являются дубликатами.
Таким образом, хэши не применяются, потому что фактически они смещают сравнение с тяжелых элементов (например, фрагментов данных) на легкие элементы (целые числа) и сокращают некоторое сравнение, но не отказываются от них, и в конце концов, мы вернулись к нашей первоначальной проблеме, когда оказались внутри одного ковша столкновения.
Представьте, что у вас есть куча потенциалов, дублирующих файлы по ГБ каждый, они имеют одинаковое значение хеш-функции, которое знает каждый хэш-алгоритм. Теперь вы найдете настоящие дубликаты.
Нет, это не может быть реальной проблемой (даже 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) , и равные предикаты являются самоопределяемыми, то есть сравнение может быть очень тяжелым .
Так что, возможно, мой вопрос должен быть следующим: использование какой структуры данных + алгоритм требует меньше сравнений.
При использовании предварительно отсортированного контейнера, такого как мультимножество, multimap не лучше в соответствии с моим тестом, так как
- сортировка при вставке уже делает сравнения,
- следующий смежный вывод снова выполняет сравнение,
- эти структуры данных предпочитают меньше операций, чем равные операции, они выполняют 2 меньше, чем (
Я не вижу, как это может сохранить сравнения.
еще одна вещь, которая игнорируется некоторыми ответами ниже, мне нужно отличать дублирующиеся группы друг от друга, а не просто хранить их в контейнере.
Заключение
После всего обсуждения, кажется, есть 3 пути
- мой оригинальный наивный метод, как описано выше
- Начните с линейного контейнера, например
std::vector, отсортируйте его, а затем найдите равные диапазоны
- начните со связанного контейнера, например
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 () ->
adjacent_find ():
сравнения: ['<' = 139, '==' = 23
] </p>
сравнения: ['<' = 38, '==' = 23] </p>
используя std :: list -> sort () -> shrink
список:
сравнений: ['<' = 50, '==' = 43] </p>
сравнений: ['<' = 52, '==' = 43] </p>
используя std :: list -> shrink list:
сравнений: ['<' = 0, '==' = 121] </p>
сравнений: ['<' = 0, '==' = 43] </p>
с использованием std :: vector -> std :: map>:
сравнения: ['<' = 79, '==' = 0] </p>
сравнения: ['<' = 53, '==' = 0] </p>
с использованием std :: vector ->
std :: multiset ->
adjacent_find ():
сравнений: ['<' = 79, '==' = 7] </p>
сравнений: ['<' = 53, '==' = 7] </p>
Код
// 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);
}