Was sind die schnellen Algorithmen, um doppelte Elemente in einer Sammlung zu finden und sie zu gruppieren?
https://stackoverflow.com/questions/1332527
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Angenommen, Sie haben eine Sammlung von Elementen. Vorzugsweise in C ++, aber Algorithmus ist wichtiger als die Sprache. Zum Beispiel {e1, e2, e3, e4, e4, e2, e6, e4, e3} möchte ich {e2, e2}, {e3, e3}, {e4, e4, e4} extrahieren. Welche Datenstruktur und welcher Algorithmus werden Sie wählen? Bitte geben Sie auch die Kosten für die Einrichtung der Datenstruktur an, beispielsweise, wenn es sich um eine vorgewiesene Art wie std :: multimap handelt
Aktualisierung
Die Dinge klarer machen, wie vorgeschlagen. Es gibt eine Einschränkung: Die Elemente müssen selbst verglichen werden Um sicher zu sein, dass sie Duplikate sind.
Hashes gelten also nicht, da sie praktisch den Vergleich mit schweren Elementen (z. Unser ursprüngliches Problem, wann befindet sich in einem Kollisions -Eimer.
Stellen Sie sich vor, Sie haben jeweils eine Reihe von potentialen doppelten Dateien von GBS, sie tragen den gleichen Hash-Wert nach jedem Hash-Algorithmus, den Menschen kennen. Jetzt werden Sie die echten Duplikate erkennen.
Nein, es kann kein reales Problem sein (selbst MD5 reicht aus, um eindeutiger Hash für reale Dateien zu generieren). Aber so tun wir einfach so, dass wir können Konzentrieren Sie sich darauf, den Datenstruktur + Algorithmus zu finden, der den geringsten Vergleich beinhaltet.
Was ich tue, ist zu
in einer STL std :: Listendatenstruktur darstellen (in diesem 1) ist sein Element-Delett billiger als beispielsweise ein Vektor 2) seine Einfügung ist billiger und erfordert keine Sortierung.)
Pop ein Element heraus und vergleichen Sie es mit dem Rest, wenn ein Duplikat gefunden wird, wird es aus der Liste herausgezogen. Sobald das Ende der Liste erreicht ist, wird eine Gruppe von Duplikationen gefunden, falls vorhanden.
Wiederholen Sie die oben genannten 2 Schritte, bis die Liste leer ist.
Es braucht N-1 im besten Fall, aber (n-1)! im schlimmsten Fall.
Was sind die besseren Alternativen?
Mein oben erläuterter Code unter Verwendung der Methode:
// 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
};
};
Vielen Dank für die Antwort unten, aber sie scheinen durch mein Beispiel irregeführt zu werden, dass es um Ganzzahlen geht. In der Tat Die Elemente sind agnostisch vom Typ (nicht unbedingt Ganzzahlen, Saiten oder andere Pods), und die gleichen Prädikate sind selbst definiert, das heißt Der Vergleich kann sehr schwer sein.
Vielleicht sollte meine Frage sein: Verwenden der Datenstruktur + Algorithmus mit weniger Vergleiche.
Wenn Sie einen vorgefertigten Behälter wie Multiset verwenden, ist Multimap nach meinem Test nicht besser
- Das Sortieren beim Einfügen bereits die Vergleiche,
- Der folgende benachbarte Befund vergleiche erneut,
- Diese Datenstruktur bevorzugen weniger als operierende Operationen, sie führen 2 weniger als (a) aus (a
Ich sehe nicht, wie es Vergleiche speichern kann.
Eine weitere Sache, die von einigen Antworten unten ignoriert wird, muss ich die doppelten Gruppen voneinander unterscheiden, nicht nur im Container aufbewahren.
Fazit
Nach all der Diskussion scheinen es 3 Wege zu geben
- Meine ursprüngliche naive Methode, wie oben erläutert
- Beginnen Sie mit einem linearen Behälter wie
std::vectorSortieren Sie es und lokalisieren Sie dann die gleichen Bereiche - Beginnen Sie mit einem zugehörigen Behälter wie
std::map<Type, vector<duplicates>>, Wählen Sie die Duplikate während der Einrichtung des zugehörigen Containers aus, wie von Charles Bailey vorgeschlagen.
Ich habe ein Beispiel codiert, um alle nachstehend veröffentlichten Methoden zu testen.
Die Anzahl der Duplikate und wenn sie verteilt werden, kann die beste Wahl beeinflussen.
- Methode 1 ist am besten, wenn sie stark vorne fallen und am Ende am schlimmsten ist. Sortierung wird die Verteilung nicht ändern, sondern den Endian.
- Methode 3 hat die durchschnittlichste Leistung
- Methode 2 ist nie die beste Wahl
Vielen Dank für alle, die an der Diskussion teilnehmen.
Eine Ausgabe mit 20 Beispielelementen aus dem folgenden Code.
Test mit [20 10 6 5 4 3 2 2 2 2 1 1 1 1 1 1 1 1 1 1
und [1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 4 5 6 10 20
Verwenden Sie std :: vector -> sort () -> adjacent_find ():
Vergleiche: ['<' = 139, '==' = 23
Vergleiche: ['<' = 38, '==' = 23
Verwenden Sie STD :: LISTE -> SORT () -> Schrumpfliste:
Vergleiche: ['<' = 50, '==' = 43
Vergleiche: ['<' = 52, '==' = 43
Verwenden Sie STD :: LISTE -> Schrumpfliste:
Vergleiche: ['<' = 0, '==' = 121
Vergleiche: ['<' = 0, '==' = 43
Verwenden Sie STD :: Vector -> std :: map>:
Vergleiche: ['<' = 79, '==' = 0
Vergleiche: ['<' = 53, '==' = 0
Verwenden von std :: vector -> std :: multiset -> adjacent_find ():
Vergleiche: ['<' = 79, '==' = 7
Vergleiche: ['<' = 53, '==' = 7
Code
// 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);
}
Lösung
Sie können eine Karte von einem repräsentativen Element zu einer Liste/einem Vektor/Deque anderer Elemente verwenden. Dies erfordert relativ weniger Vergleiche beim Einfügen in den Container und bedeutet, dass Sie durch die resultierenden Gruppen iterieren können, ohne Vergleiche durchzuführen.
Dieses Beispiel fügt immer das erste repräsentative Element in die kartierte Deque -Speicherung ein, da die nachfolgende Iteration durch die Gruppe logisch einfach ist push_back nur 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);
}
Das Iterieren durch die Gruppen ist dann (relativ) einfach und billig:
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
}
}
}
Ich habe einige Experimente zur Vergleichs- und Objektzahlen durchgeführt. In einem Test mit 100000 Objekten in zufälliger Reihenfolge bildete die obige Methode die folgende Anzahl von Vergleiche und Kopien:
1630674 comparisons, 443290 copies
(Ich habe versucht, die Anzahl der Kopien zu senken, aber nur auf Kosten von Vergleiche, die den höheren Kostenbetrieb in Ihrem Szenario zu sein scheinen.)
Die Verwendung eines Multimaps und die Beibehaltung des vorherigen Elements in der endgültigen Iteration, um die Gruppenübergänge zu erkennen, kosten dies:
1756208 comparisons, 100000 copies
Verwenden einer einzelnen Liste, das Aufnehmen des Frontelements und das Ausführen einer linearen Suche nach anderen Gruppenmitgliedern:
1885879088 comparisons, 100000 copies
Ja, das sind ~ 1,9B -Vergleiche im Vergleich zu ~ 1,6 m für meine beste Methode. Damit die Listenmethode in die Nähe einer optimalen Anzahl von Vergleiche durchführen kann, müsste sie sortiert werden, und dies wird eine ähnliche Anzahl von Vergleiche kosten, da der Bau eines von Natur aus geordneten Containers überhaupt erst bauen würde.
Bearbeiten
Ich habe Ihren veröffentlichten Code genommen und den implizite Algorithmus (ich musste einige Annahmen über den Code wie einige angenommene Definitionen angenommen) über denselben Testdatensatz ausgeführt, wie ich es zuvor verwendet habe, und ich zählte:
1885879088 comparisons, 420939 copies
dh genau die gleiche Anzahl von Vergleiche wie mein dummer Listenalgorithmus, aber mit weiteren Kopien. Ich denke, das bedeutet, dass wir für diesen Fall im Wesentlichen ähnliche Algorithmen verwenden. Ich kann keine Hinweise auf eine alternative Sortierreihenfolge sehen, aber es sieht so aus, als ob Sie eine Liste der Gruppen haben möchten, die mehr als ein äquivalentes Element enthalten. Dies kann einfach in meinem erreicht werden Iterate Funktion durch Hinzufügen if (i->size > 1) Klausel.
Ich kann immer noch keine Beweise dafür sehen, dass das Erstellen eines sortierten Containers wie diese Karte von Deques keine gute (wenn nicht optimale) Strategie ist.
Andere Tipps
Ja, Sie können es viel besser machen.
Sortieren Sie sie (o (n) für einfache ganze Zahlen, o (n*log n) im Allgemeinen), dann dürfen Duplikate garantiert benachbart sind, was dazu führt, dass sie schnell o (n) finden.
Verwenden Sie eine Hash -Tabelle, auch o (n). Überprüfen Sie für jeden Artikel (a), ob es sich bereits in der Hash -Tabelle befindet. Wenn ja, ist es ein Duplikat; Wenn nicht, legen Sie es in den Hash -Tisch.
bearbeiten
Die Methode, die Sie verwenden, scheint o (n^2) Vergleiche zu machen:
for i = 0; i < length; ++i // will do length times
for j = i+1; j < length; ++j // will do length-i times
compare
Also für Länge 5 machen Sie 4+3+2+1 = 10 Vergleiche; Für 6 machen Sie 15 usw. (n^2)/2 - n/2, um genau zu sein. N*log (n) ist kleiner, für jeden einigermaßen hohen Wert von N.
Wie groß ist n in Ihrem Fall?
In Bezug auf die Reduzierung von Hash-Kollisionen besteht der beste Weg, eine bessere Hash-Funktion zu erhalten: D. Angenommen, dies ist nicht möglich, können Sie möglicherweise einen verschachtelten Hash machen, wenn Sie eine Variante (z. B. anders Modulous) erstellen können.
1. Sortieren Sie das Array O (n log n) im schlimmsten Fall - Mergesort/Haufen/Binärbaumsort usw.
2. Vergleichen Sie Nachbarn und ziehen Sie die Übereinstimmungen O (n) heraus
Halten Sie eine Hash-Tisch-basierte Struktur von Wert bis zu zählen; Wenn Ihre C ++ - Implementierung nicht bietet std::hash_map (Bisher nicht wirklich Teil des C ++-Standards!-) Verwenden Sie Boost oder schnappen Sie sich eine Version aus dem Web. Mit einem Durchgang über die Sammlung (dh O (n)) können Sie eine Wertvorstellung durchführen. Ein weiterer Übergang über die Hash -Tabelle (<= O (n), eindeutig), um Werte mit einer Anzahl> 1 zu identifizieren und sie angemessen auszugeben. Insgesamt O (n), was für Ihren Vorschlag nicht der Fall ist.
Hast du versucht zu sortieren? Zum Beispiel verwenden Sie einen Algorithmus wie schnelle Sortierung? Wenn die Leistung für Sie gut genug ist, wäre das ein einfacher Ansatz.
Wenn bekannt ist, dass es sich um eine Liste von Ganzzahlen handelt, und wenn bekannt ist, dass sie alle zwischen A und B sind (zB a = 0, b = 9), machen Sie eine Reihe von BA -Elementen und erstellen Sie BA -Behälter.
In dem ganz spezifischen Fall (Liste der einfachen Ganzzahlen) schlage ich vor, dass Sie sie nur zählen, da Sie sowieso verschiedene ganze Zahlen nicht unterscheiden können:
for(int i = 0; i < countOfNumbers; i++)
counter[number[i]]++;
Wenn sie sind Unterscheidbar, erstellen Sie eine Reihe von Listen und fügen Sie sie der jeweiligen Liste hinzu.
Wenn es sich nicht um Zahlen handelt, verwenden Sie eine std :: map oder std :: hash_map, die Schlüsseln zu Wertenlisten.
Am einfachsten ist es wahrscheinlich, die Liste zu sortieren und dann nach Dups zu suchen.
Wenn Sie etwas über die Daten wissen, sind effizientere Algorithmen möglich.
Wenn Sie beispielsweise wussten, dass die Liste groß war und nur Zahlen von 1 enthielt. N, wo n ziemlich klein ist, könnten Sie ein Paar boolesche Arrays (oder eine Bitmap) verwenden und so etwas tun:
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;
Jetzt enthält viele [] ein Array, von dem Werte mehr als einmal gesehen wurden.
Die meisten Menschen, die Hash/Unordnungs -Kartenlösungen erwähnen, nehmen O (1) Insertion- und Abfragezeit an, es könnte jedoch o (n) schlimmster Fall sein. Zusätzlich ungültig, die Kosten für das Hashing von Objekten.
Persönlich würde ich Objekte in einen binären Baum (O (logn) für jeden) einfügen und an jedem Knoten den Zähler halten. Dies würde zu O (NLogn) -Konstruktionszeit und O (n) -Anquerlauf liefern, um alle Duplikate zu identifizieren.
Wenn ich die Frage richtig verstanden habe, ist dies die einfachste Lösung, an die ich denken kann:
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);
}
Gesamtlaufzeit: O(n log n). Sie haben einen Sortierpass O(n lg n) und dann einen zweiten Pass wo O(lg n) Vergleiche werden durchgeführt Für jede Gruppe (Das ist also getan maximal n Zeiten, auch nachgeben O(n lg n).
Beachten Sie, dass dies davon abhängt, dass der Eingang ein Vektor ist. Nur Zufallszugriffs -Iteratoren haben im zweiten Pass eine logarithmische Komplexität. Bidirektionale Iteratoren wären linear.
Dies beruht nicht auf Hashing (wie angefordert) und bewahrt alle ursprünglichen Elemente (anstatt nur ein Element für jede Gruppe zurückzugeben, zusammen mit einer Anzahl der Auftreten, wie es oft aufgetreten ist).
Natürlich ist eine Reihe kleinerer konstanter Optimierungen möglich. output.reserve(input.size()) Auf dem Ausgangsvektor wäre eine gute Idee, um eine Umverteilung zu vermeiden. input.end() wird viel häufiger als nötig genommen und kann leicht zwischengespeichert werden.
Je nachdem, wie groß die Gruppen angenommen werden, werden angenommen, equal_range Möglicherweise ist nicht die effizienteste Wahl. Ich gehe davon aus, dass es eine binäre Suche nach logarithmischer Komplexität durchführt, aber wenn jede Gruppe nur ein paar Elemente ist, wäre ein einfacher linearer Scan schneller gewesen. In jedem Fall dominiert die anfängliche Sortierung jedoch die Kosten.
Nur um sich zu registrieren, dass ich das gleiche Problem während einer Normalisierung eines dreifachen Ladens hatte, mit dem ich zusammenarbeite. Ich habe die von Charles Bailey zusammengefasste Methode 3 mit der Hash-Table-Funktion von Allegro Common LISP zusammengefasst.
Die Funktion "Agent-Gleiche?" wird verwendet, um zu testen, wenn zwei Mittel in den Ts gleich sind. Die Funktion "Merge-Nodes" verschmilzt die Knoten an jedem Cluster. In dem folgenden Code wurde das "..." verwendet, um die nicht so wichtigen Teile zu entfernen.
(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)
...
)))))
Da C ++ 11 Hash -Tabellen von der STL mit bereitgestellt werden STD :: Under Ordered_map. Eine o (n) Lösung besteht also darin, Ihre Werte in eine zu setzen unordered_map< T, <vector<T> >.
