Скажите, что у вас есть набор элементов, как вы можете выбрать дубликаты и поместить их в каждую группу с минимальным количеством сравнения? желательно на С++, но алгоритм более важен, чем язык. Например (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), а равные предикаты самоопределяются, то есть сравнение может быть очень тяжелым,
Итак, может быть, мой вопрос должен быть: использование какой структуры данных + алгоритм требует меньшего количества сравнений.
Использование предварительно отсортированного контейнера, такого как multiset, multimap не лучше в соответствии с моим тестом, так как
- сортировка при вставке уже выполняет сравнения,
- следующий смежный вывод снова делает сравнение,
- эти структуры данных предпочитают меньше операций, чем равные операции, они выполняют 2 меньше (a
Я не вижу, как он может сохранять сравнения.
еще одна вещь, которая игнорируется некоторыми ответами ниже, мне нужно различать повторяющиеся группы друг от друга, а не просто хранить их в контейнере.
Заключение
После всего обсуждения, кажется, есть 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 ]
: ['<' = 38, '==' = 23]
используя std:: list → sort() → shrink список:
: ['<' = 50, '==' = 43]
: ['<' = 52, '==' = 43]
используя std:: list → shrink 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);
}
