Container zusammenfügen und doppelte Einträge entfernen

Sengha

Ausgangssituation:

Ich habe mehrere Container (vector<int>) die ich alle nun zu einem Einzigen Container zusammenfügen möchte. Nun befindet sich mit großer Sicherheit ein Wert in mehreren dieser Listen wieder. Ziel ist es neben dem Zusammenfügen aller Listen auch doppelte Einträge zu entfernen.

Veranschaulichung:

liste1 { 2, 4, 6, 8, 9 }
liste2 { 3, 4, 5, 6, 8 }
liste3 { 1, 2, 6, 8, 9 }

ergebnis { 1, 2, 3, 4, 5, 6, 8, 9}

Die Ergebnisliste muß dabei nicht unbedingt sortiert sein. Es geht nur um die Werte.

Ich dachte an die Möglichkeit ein set<int> zu verwenden. Gibt es noch andere Möglichkeiten, die evtl. Performanter sind?

Hinweis: In meiner Software habe ich letztlich hunderte dieser Listen (mit unterschiedlicher Länge), die jeweils einige Hundert Werte beinhalten können.

theta

http://www.cplusplus.com/reference/algorithm/unique_copy/
http://www.cplusplus.com/reference/algorithm/unique/

Edit:
Bin mir nicht sicher, aber ich denke, die beiden Algorithmen helfen nicht weiter.

Edit2:
Also... falls std::list als Container auch in Frage kommt..
Die std::list hat nämlich schon optimierte Memberfunktionen dafür.

std::list<long> v1;
v1.push_back(1);
v1.push_back(3);
v1.push_back(5);

std::list<long> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);

v1.merge(v2);
v1.unique();

DocShoe

Für std::list::unique muss die list sortiert sein, also vorher noch sort() aufrufen.

KA51O

muss der zusammengefügte container (also das ergebnis) den auch ein vector sein ?

ansonsten kannst du einfach einen anderen containertyp nutzen
http://www.cplusplus.com/reference/stl/

da gibt es auf jeden fall einen containertyp in den du beliebige einträge (auch doppelt) einfügen kannst und diese dann nur einmal im container gespeichert sind.

ist einer der assoziativen container (set oder map) weiß jetzt grad nicht welcher ^^

Sengha

Für den Zielcontainer kann alles in Frage kommen. Es muß nur schnell sein. Ich probiere mal std::list aus und analysiere die Performance zur Laufzeit.

@KA51O
das wäre dann std::set

KA51O

^^ genau das meinte ich.

hilft aber nicht oder wie ?

und noch was zum aufheitern beim coden:

My Software never has bugs. It just develops random features.

Sengha

KA51O schrieb:

^^ genau das meinte ich.
hilft aber nicht oder wie ?

das war meine erste idee, aber set und map sind für eher dafür ausgelegt, elemente schnell zu finden und nach meiner erfahrung langsamer in der erstellung.

drakon

Ich würds wahrscheinlich auch so in etwa, wie theta machen.
Mergen, sortieren und dann die Mehrfachen rausschmeissen. Mergen sollte schnell gehen (n). Sortieren hat nlog(n) und das rausschmeissen geht in n.

Sengha schrieb:

Für den Zielcontainer kann alles in Frage kommen. Es muß nur schnell sein. Ich probiere mal std::list aus und analysiere die Performance zur Laufzeit.

Kommt halt drauf an, was du zur Laufzeit für Operationen hast. Eher Zugriff? Dann sollte es etwas, wie std::vector sein. Veränderung? Dann sollte es wohl doch eher was, wie std::list sein. Oder doch suchen? Dann eher die std::map .

Sengha

@drakon

Die werte der Ergebnisliste muß ich sowiso alle anfassen... von daher ist std::list volkommen ok. sie dürfen halt nur nicht doppelt sein, sonst kommt totaler blödsinn raus

ich sag einfach mal: thema gelöst

Nexus

drakon schrieb:

Ich würds wahrscheinlich auch so in etwa, wie theta machen.
Mergen, sortieren und dann die Mehrfachen rausschmeissen. Mergen sollte schnell gehen (n). Sortieren hat nlog(n) und das rausschmeissen geht in n.

Warum nicht beide Sequenzen einzeln sortieren, mehrfache Vorkommen rausschmeissen und dann zusammenführen? Dürfte aus zwei Gründen schneller sein: Erstens braucht das Entfernen in Containern wie std::vector weniger Zeit, wenn weniger Elemente auf das zu löschende folgen. Zweitens ist es effizienter, zwei kleine Sequenzen zu sortieren, als eine grosse. Denn es gilt n*log(n) + n*log(n) < 2n*log(2n) .

Zusammenführen braucht dann jedoch wegen der If-Abfragen minimal mehr Zeit. Der Unterschied ist jedoch im Bezug auf die Elemente konstant, während der Gewinn durch Sortierung der beiden einzelnen Sequenzen 2n*log(2) beträgt.

Nexus schrieb:

Zusammenführen braucht dann jedoch wegen der If-Abfragen minimal mehr Zeit.

Bist du dir da mit dem "minimal" sicher? Bei m vectoren mit n Einträgen stelle ich mir das Mergen als O(m*n) vor, oder gibt's da was besseres?

knivil

Warum nicht beide Sequenzen einzeln sortieren, mehrfache Vorkommen rausschmeissen und dann zusammenführen?

Weil du nachtraeglich nochmal doppelte entfernen musst.

Nexus

Badestrand_ schrieb:

Bist du dir da mit dem "minimal" sicher? Bei m vectoren mit n Einträgen stelle ich mir das Mergen als O(m*n) vor, oder gibt's da was besseres?

Ich meinte minimal mehr.
Und zwar gegenüber einem Merge von m unsortierten Containern mit n Elementen, die einfach aneinander gehängt werden. Das benötigt ebenfalls O(m*n) Rechenschritte.

Besser wäre, wenn man sich die Umkopiererei sparen könnte und die einzelnen Stücke lediglich referenziert. Das könnte als eine Art Range gestaltet werden, sodass man von aussen her das Gefühl hat, es handle sich um eine zusammenhängende Sequenz, tatsächlich sind die einzelnen Teile aber verstreut. Dafür bezahlt man aber mit langsameren Zugriff.

knivil schrieb:

Weil du nachtraeglich nochmal doppelte entfernen musst.

Das kann man ja gleich beim Zusammenführen erledigen.

knivil

Das kann man ja gleich beim Zusammenführen erledigen.

Das kann man auch schon beim Sortieren erledigen, aber dann muss man Sortieren (oder Zusammenfuehren) selbst implementieren.

drakon

Das Problem ist halt, dass du so, oder so nach dem mergen nochmal sortieren und raus schmeissen musst und ich denke dann fährst du besser, wenn du das im gesamten nur 1x machst, als 3x.
Du hast also eher:

n*log(n) + n*log(n) + kn*log(kn) vs. 2n*log(2n) , k <= 2n

Nexus

drakon schrieb:

Das Problem ist halt, dass du so, oder so nach dem mergen nochmal sortieren und raus schmeissen musst

Eben nicht. Zwei sortierte Container mit m respektive n Elementen kann man in O(m+n) zusammenführen, sodass der neue Container sowohl sortiert ist als auch keine mehrfachen Elemente enthält.

Dass es witzlos ist, drei Mal rauszuschmeissen und zu sortieren, glaube ich dir gern.

drakon

Nexus schrieb:

drakon schrieb:

Das Problem ist halt, dass du so, oder so nach dem mergen nochmal sortieren und raus schmeissen musst

Eben nicht. Zwei sortierte Container mit m respektive n Elementen kann man in O(m+n) zusammenführen, sodass der neue Container sowohl sortiert ist als auch keine mehrfachen Elemente enthält.

Achso. Da stand ja noch mehr.

Naja. So viel Gedanken habe ich mir da gestern nicht gemacht, aber ich denke auch, dass wenn man selbst alles von Hand macht, dass man die Operationen schon auch schneller hin bringt, als die Kaskade von Standardalgorithmen.

Nexus

Man muss ja nicht alles von Hand erledigen. Ein Algorithmus, der zwei sortierte Sequenzen effizient zusammenführt und Duplikate löscht, sollte reichen. Ich dachte an sowas:

template <typename InputIterator, typename OutputIterator>
void advance_smaller(InputIterator& left, InputIterator& right, InputIterator& previous, OutputIterator& result)
{
	if (*left < *right)
		previous = left++;
	else
		previous = right++;

	*result++ = *previous;
}

template <typename InputIterator, typename OutputIterator>
OutputIterator merge_unique(InputIterator first1, InputIterator last1, InputIterator first2, InputIterator last2,
	OutputIterator result)
{	
	InputIterator previous;
	advance_smaller(first1, first2, previous, result);

	for (;;)
	{
		if (first1 == last1)
			return std::copy(first2, last2, result);
		else if (first2 == last2)
			return std::copy(first1, last1, result);

		if (*first1 == *previous)
			++first1;
		else if (*first2 == *previous)
			++first2;
		else
			advance_smaller(first1, first2, previous, result);
	}
}

Eventuell noch eine Wrapper-Funktion:

template <class Container>
void merge_unique_containers(const Container& source1, const Container& source2, Container& dest)
{
	merge_unique(source1.begin(), source1.end(), source2.begin(), source2.end(), std::back_inserter(dest));
}

Der STL-Algorithmus std::set_union() sieht eigentlich vielversprechend aus, allerdings trifft er die Annahme, dass beide Quell-Ranges keine Duplikate enthalten.