ما هي الخوارزميات السريعة للعثور على العناصر المكررة في المجموعة وتجميعها؟
https://stackoverflow.com/questions/1332527
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لنفترض أن لديك مجموعة من العناصر، كيف يمكنك اختيار العناصر المكررة ووضعها في كل مجموعة بأقل قدر من المقارنة؟ويفضل أن يكون ذلك في 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) يكون إدراجه أرخص، ولا يتطلب الفرز.)
قم بإخراج عنصر واحد ومقارنته بالباقي، إذا تم العثور على نسخة مكررة، فسيتم سحبه من القائمة.وبمجرد الوصول إلى نهاية القائمة، يتم العثور على مجموعة واحدة من التكرارات، إن وجدت.
كرر الخطوتين أعلاه حتى تصبح القائمة فارغة.
إنها تحتاج إلى 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
};
};
شكرًا على الإجابة أدناه، ولكن يبدو أنه تم تضليلهم من خلال مثالي الذي يتعلق بالأعداد الصحيحة.في الحقيقة العناصر لا تعرف الكتابة (وليس بالضرورة أعدادًا صحيحة أو سلاسل أو أي PODs أخرى), ، والمسندات المتساوية محددة ذاتيًا، أي يمكن أن تكون المقارنة ثقيلة جدًا.
لذلك ربما ينبغي أن يكون سؤالي:باستخدام بنية البيانات + الخوارزمية التي تتضمن مقارنات أقل.
باستخدام حاوية تم فرزها مسبقًا مثل مجموعة متعددة، فإن الخريطة المتعددة ليست أفضل وفقًا للاختبار الذي أجريته، منذ ذلك الحين
- الفرز أثناء الإدراج يقوم بالفعل بإجراء المقارنات،
- النتيجة المجاورة التالية تقوم بالمقارنة مرة أخرى،
- تفضل هياكل البيانات هذه عمليات أقل من العمليات المتساوية، فهي تؤدي 2 أقل من (a
لا أرى كيف يمكن حفظ المقارنات.
هناك شيء آخر تتجاهله بعض الإجابات أدناه، وهو أنني أحتاج إلى التمييز بين المجموعات المكررة عن بعضها البعض، وليس مجرد الاحتفاظ بها في الحاوية.
خاتمة
بعد كل هذه المناقشة، يبدو أن هناك 3 طرق
- طريقتي الساذجة الأصلية كما هو موضح أعلاه
- ابدأ بحاوية خطية مثل
std::vector، قم بفرزها ثم حدد النطاقات المتساوية - ابدأ بحاوية مرتبطة مثل
std::map<Type, vector<duplicates>>, ، انتقاء التكرارات أثناء إعداد الحاوية المرتبطة كما اقترح تشارلز بيلي.
لقد قمت بترميز عينة لاختبار جميع الطرق كما هو منشور أدناه.
قد يؤثر عدد التكرارات ووقت توزيعها على الاختيار الأفضل.
- الطريقة الأولى هي الأفضل عندما يسقطون بشدة في المقدمة، وتكون الأسوأ عندما تكون في النهاية.لن يؤدي الفرز إلى تغيير التوزيع، بل إلى النهاية.
- الطريقة الثالثة لديها الأداء الأكثر متوسطًا
- الطريقة الثانية ليست الخيار الأفضل أبدًا
شكرا لجميع الذين شاركوا في المناقشة.
مخرج واحد يحتوي على 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 2 2 2 3 4 5 6 10 20] على التوالي
باستخدام std :: vector -> sort () -> foxacent_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 -> foxacent_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);
}
المحلول
يمكنك استخدام خريطة من عنصر تمثيلي إلى قائمة/متجه/مجموعة من العناصر الأخرى.يتطلب هذا مقارنات أقل نسبيًا عند الإدراج في الحاوية ويعني أنه يمكنك التكرار عبر المجموعات الناتجة دون الحاجة إلى إجراء أي مقارنات.
يقوم هذا المثال دائمًا بإدراج العنصر التمثيلي الأول في مخزن deque المعين لأنه يجعل التكرار اللاحق عبر المجموعة بسيطًا منطقيًا، ولكن إذا أثبت هذا التكرار وجود مشكلة، فسيكون من السهل تنفيذ الأمر فقط push_back فقط 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
}
}
}
لقد أجريت بعض التجارب للمقارنة وأعداد الكائنات.في اختبار يتضمن 100000 كائن بترتيب عشوائي مكونًا 50000 مجموعة (أيومتوسط كائنين لكل مجموعة) تكلف الطريقة المذكورة أعلاه العدد التالي من المقارنات والنسخ:
1630674 comparisons, 443290 copies
(لقد حاولت تقليل عدد النسخ، لكنني لم أتمكن من ذلك إلا على حساب المقارنات التي يبدو أنها العملية ذات التكلفة الأعلى في السيناريو الخاص بك.)
إن استخدام خريطة متعددة والاحتفاظ بالعنصر السابق في التكرار النهائي لاكتشاف انتقالات المجموعة يكلف هذا:
1756208 comparisons, 100000 copies
تكلفة استخدام قائمة واحدة وإبراز العنصر الأمامي وإجراء بحث خطي عن أعضاء المجموعة الآخرين:
1885879088 comparisons, 100000 copies
نعم، هذا ما يقرب من 1.9 مليار مقارنات مقارنة بـ 1.6 مليون تقريبًا لأفضل طريقة لدي.للحصول على طريقة القائمة لأداء أي مكان بالقرب من العدد الأمثل من المقارنات، يجب أن يتم فرزها، وهذا سيكلف عددًا مماثلاً من المقارنات مثل بناء حاوية مرتبة بطبيعتها في المقام الأول.
يحرر
لقد أخذت الكود المنشور الخاص بك وقمت بتشغيل الخوارزمية الضمنية (اضطررت إلى وضع بعض الافتراضات حول الكود كما توجد بعض التعريفات المفترضة) على نفس مجموعة بيانات الاختبار التي استخدمتها من قبل وقمت بالحساب:
1885879088 comparisons, 420939 copies
أي.بالضبط نفس عدد المقارنات مثل خوارزمية القائمة الغبية، ولكن مع المزيد من النسخ.أعتقد أن هذا يعني أننا نستخدم خوارزميات مماثلة بشكل أساسي لهذه الحالة.لا أستطيع رؤية أي دليل على وجود ترتيب فرز بديل، ولكن يبدو أنك تريد قائمة بالمجموعات التي تحتوي على أكثر من عنصر واحد مكافئ.يمكن تحقيق ذلك ببساطة في بلدي Iterate وظيفة عن طريق إضافة if (i->size > 1) بند.
ما زلت لا أستطيع رؤية أي دليل على أن بناء حاوية مرتبة مثل خريطة deques هذه ليست استراتيجية جيدة (حتى لو لم تكن مثالية).
نصائح أخرى
نعم، يمكنك أن تفعل أفضل بكثير.
فرزها (O (n) للأعداد الصحيحة البسيطة، O (N * Log N) بشكل عام)، ثم يتم ضمان التكرارات أن تكون مجاورة، مما يجعل العثور عليها سريعة O (N)
استخدم طاولة تجزئة، أيضا O (n). لكل عنصر، (أ) تحقق مما إذا كان ذلك بالفعل في جدول التجزئة؛ إذا كان الأمر كذلك، فهي مكررة؛ إذا لم يكن كذلك، ضعها في طاولة التجزئة.
تعديل
يبدو أن الطريقة التي تستخدمها Do 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 * log (n) أصغر، لأي قيمة عالية من N.
كيف كبيرة ن في قضيتك؟
بقدر تقليل تصادمات التجزئة، فإن أفضل طريقة هي الحصول على وظيفة تجزئة أفضل :-D. على افتراض أنه غير ممكن، إذا كان بإمكانك إجراء متغير (على سبيل المثال، مختلفا للتنفيذ)، فقد تكون قادرا على القيام بتجميل متداخلا.
1. فرز صفيف O (N Log N) في أسوأ الأحوال - Mergesort / Heapsort / Trink Tree Trans ETC
2. مقارنة الجيران وسحب المباريات خارج O (N)
احتفظ بهيكل يعتمد على جدول التجزئة من القيمة إلى الأعلى؛ إذا كان تنفيذ C ++ الخاص بك لا يقدم std::hash_map (ليس حقا جزءا من معيار C ++ حتى الآن! -) استخدم دفعة أو الاستيلاء على نسخة من الويب. يتيح لك المرء على المجموعة (أي، O (n)) القيام بقيمة رسم الخرائط القيمة؛ يمر آخر على طاولة التجزئة (<= o (n)، بوضوح) لتحديد القيم مع عدد> 1 وانبعث منها بشكل مناسب. عموما O (ن)، وهذا ليس هو الحال لاقتراحك.
هل حاولت الفرز؟ على سبيل المثال باستخدام خوارزمية مثل الفرز السريع؟ إذا كان الأداء جيدا بما يكفي بالنسبة لك، فسيكون ذلك نهجا سهلا.
إذا كان من المعروف أنه قائمة بالأعداد الصحيحة، وإذا كان من المعروف أنهم جميعا بين A و B (مثل = 0، B = 9)، فقم بإنشاء مجموعة من عناصر BA، وإنشاء حاويات BA.
في حالة محددة للغاية (قائمة الأعداد الصحيحة العادية)، أقترح عليك فقط عدها، لأنك لا تستطيع التمييز بين أعداد صحيحة مختلفة، على أي حال:
for(int i = 0; i < countOfNumbers; i++)
counter[number[i]]++;
اذا هم نكون تميز، قم بإنشاء مجموعة من القوائم، وأضفها إلى القائمة المعنية.
إذا لم تكن أرقاما، فاستخدم خريطة STD :: الأمراض المنقولة جنسيا أو STD :: MASH_MAP ومفاتيح التعيين لقوائم القيم.
على الأرجح على الأرجح فقط فرز القائمة، ثم للتكرار أثناء البحث عن Dups.
إذا كنت تعرف شيئا عن البيانات، فإن الخوارزميات الأكثر كفاءة ممكنة.
على سبيل المثال، إذا كنت تعرف أن القائمة كانت كبيرة، وتواصل الأعداد الصحيحة فقط من 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;
الآن، يحتوي العديد من [] على مجموعة من القيم التي شوهدت أكثر من مرة.
معظم الأشخاص الذين يذكرون حلول خريطة التجزئة / غير المبررة يفترضون وقت الإدراج والاستعلام، ومع ذلك يمكن أن يكون O (n) أسوأ الحالات. بالإضافة إلى ذلك، يمكنك إبطال تكلفة تجزئة الكائن.
أنا شخصيا أود إدراج كائنات في شجرة ثنائية (O (LOGN) الإدراج لكل منها)، والحفاظ على عداد في كل عقدة. هذا من شأنه أن يحقق وقت البناء O (NLGON) و O (N) اجتياز لتحديد جميع التكرارات.
إذا فهمت السؤال بشكل صحيح، فهذا هو أبسط الحل الذي يمكنني التفكير فيه:
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) يتم إجراء المقارنات لكل مجموعة (لذلك يتم ذلك في الغالب n مرات، كما تحقق O(n lg n).
لاحظ أن هذا يعتمد على الإدخال كونه متجه. فقط الوصول العشوائي للوصول إلى تعقيد لوغاريتمي في الممر الثاني. محامون ثنائي الاتجاه سيكون خطي.
هذا لا يعتمد على التجزئة (على النحو المطلوب)، ويحافظ على جميع العناصر الأصلية (بدلا من إرجاع عنصر واحد فقط لكل مجموعة، إلى جانب عدد عدد مرات حدوث ذلك).
بالطبع، هناك عدد من التحسينات المستمرة الأصغر ممكنا. output.reserve(input.size()) على ناقلات الإخراج سيكون فكرة جيدة، لتجنب إعادة التخصيص. input.end() يؤخذ في كثير من الأحيان أكثر من اللازم أيضا، ويمكن تخزينها بسهولة.
اعتمادا على مقدار الفئات الكبيرة التي يفترض بها، equal_range قد لا يكون الاختيار الأكثر كفاءة. أفترض أنه يقوم بعمل بحث ثنائي للحصول على تعقيد لوغاريتمي، ولكن إذا كانت كل مجموعة فقط من العناصر فقط، فإن الفحص الخطي البسيط سيكون أسرع. على أي حال، يهيمن الفرز الأولي على التكلفة رغم ذلك.
فقط للتسجيل في كان لدي نفس المشكلة أثناء تطبيع متجر ثلاثي يعمل معه. لقد قمت بتنفيذ الطريقة الثالثة، التي تلخيصها من قبل تشارلز بيلي، في LISP المشترك باستخدام ميزة جدول التجزئة من Allegro Common Lisp.
وظيفة "وكيل متساو؟" يستخدم لاختبار عندما يكون الوكلاء في 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)
...
)))))
منذ C ++ 11، يتم توفير جداول التجزئة من قبل STL مع STD :: unrodered_map.وبعد لذلك الحل O (ن) هو وضع قيمك في unordered_map< T, <vector<T> >.
