要素のコレクションがあるとします。重複している要素をどのように選択し、それらを最小の比較で各グループに入れることができますか? できれば C++ ですが、アルゴリズムは言語よりも重要です。たとえば、{E1,E2,E3,E4,E4,E2,E6,E4,E3} を指定した場合、{E2,E2}、{E3,E3}、{E4,E4,E4} を抽出します。どのデータ構造とアルゴリズムを選択しますか? std::multimap のような事前にソートされたデータ構造の場合、データ構造のセットアップのコストも含めてください。
アップデート
提案されたように物事をより明確にするため。1 つの制約があります。要素が重複していることを確認するには、要素を単独で比較する必要があります。
したがって、ハッシュは適用されません。事実上、比較を重い要素（データのチャンクなど）から軽い要素（整数）にシフトし、比較を減らしますが、それらをなくすわけではなく、最終的には元に戻ります1つの衝突バケット内にある場合の元の問題。
それぞれ GB の潜在的な重複ファイルがたくさんあるふりをすると、それらは人間が知っているすべてのハッシュアルゴリズムによって同じハッシュ値を持ちます。これで、実際の重複を見つけることができます。
いいえ、それは実際の問題ではありません (MD5 でさえ、実際のファイルの一意のハッシュを生成するのに十分です)。しかし、データ構造 + 比較の最小量を含むアルゴリズムを見つけることに集中できるように、ふりをしてください。
私がやっていることは
STL std::list データ構造に表現します (1) その要素の削除は、たとえばベクトルよりも安価です 2) その挿入は、ソートを必要とせずに安価です。)
1 つの要素を取り出して残りの要素と比較し、重複が見つかった場合はリストから除外します。リストの最後に到達すると、1 つのグループの重複が検出されます。
リストが空になるまで、上記の 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
比較を保存する方法がわかりません。
以下のいくつかの回答で無視されているもう1つのことは、重複したグループをコンテナに保持するだけでなく、互いに区別する必要があることです。
結論
いろいろ話し合った結果、3つの方法があるようです
- 上記で説明した私の元の素朴な方法
- のような線形コンテナーから開始し
std::vector、並べ替えてから、等しい範囲を見つけます - のような関連するコンテナから始めて、
std::map<Type, vector<duplicates>>Charles Bailey の提案に従って、関連するコンテナのセットアップ中に重複を選択します。
以下に投稿されているように、すべてのメソッドをテストするサンプルをコーディングしました。
複製の数とそれらがいつ配布されるかは、最良の選択に影響を与える可能性があります。
- 方法 1 は、先頭で激しく落下する場合に最適であり、最後に落下する場合は最悪です。並べ替えは分布を変更しませんが、エンディアンを変更します。
- 方法 3 のパフォーマンスが最も平均的です
- 方法 2 は決して最良の選択ではありません
議論に参加してくれたすべての人に感謝します。
以下のコードからの 20 個のサンプル項目を含む 1 つの出力。
[ 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 2 2 2 2 3 4 5 6 10 20 ] それぞれ
std::vector を使用 -> sort() -> neighbor_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 -> neighbor_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);
}
