Duplikate aus ArrayList [besser: List<T>] entfernen

Hallo,

ich möchte aus einer ArrayList Duplikate entfernen, so dass jeder Eintrag nur noch einmal vorkommt. Das dumme ist, dass die Objekte dabei dann als gleich definiert werden, wenn ihre Werte gleich sind, es ist nicht Objektidentität gemeint.

Hat jemand eine Idee, wie man so etwas performant realisieren kann?

Vielen Dank,

Golo

Hallo golohaas.de,

ich bekenne mich als Fan von Hashtables und würde die ArrayList per for-Schleife durch gehen. Für jedes Element fragen, ob es schon in der Hastable (als Key) enthalten ist. Wenn ja, Element aus der ArrayList entfernen, wenn nicht Element in die Hashtable hinzufügen (als Key; was als Value verwendet wird, ist egal; true würde passen).

Natürlich kann man auch in einer foreach-Schleife blind jedes Element (als Key) in die Hashtable packen und nacher statt der Original-ArrayList, die Keys-Eigenschaft der Hashtable verwenden.

herbivore

Hi!

Das ist ne gute Idee, danke 🙂!

Viele Grüße,

Golo

Ich würde die doppelten Elemente nicht durch Entfernen aussortieren. Erstens muss ständig der Index in der for-Schleife angepasst werden und zweitens ist es wenig performant, Elemente aus einer ArrayList zu entfernen. Jedes Mal, wenn ein Element entfernt wird, müssen alle nachfolgenden Elemente um eine Position umkopiert werden.

Besser ist eine neue Liste aufzubauen. Foreach-Schleife: wenn ein Element nicht in der Hashtable ist, kommt es in die neue Liste und in die Hashtable. Wenn es das selbe ArrayList-Objekt sein muss, kann man im Anschluss alle Elemente wieder umkopieren.

Gruss
Pulpapex

Das was purpalex hier erzählt ist alles quatsch!!!!!!!! Gewusst wie heist die devise

Hatte das Problem bei ner Abfrage in ASP..... Aber den Code kannst du auch verwenden is ne rekursiev funktion:

		private ArrayList CleanArray2(int startIndex, ArrayList arr)
		{
			//bool thisCheck = false;
			Guid val = new Guid( arr[startIndex].ToString() );
			for ( int i = arr.Count-1 ; i >= 0; --i)
			{
				if ( i != startIndex)
				{
					if ( val == new Guid( arr[i].ToString() ) )
					{
						arr.RemoveAt(i);
					}
				}
			}
			if ( startIndex < arr.Count - 1 )
			{ 
				startIndex++;
				CleanArray2(startIndex ,arr);
			}
			return arr;
		}

Hallo at2oo1,

schon erstaunlich wieviel Ausrufezeichen du bei einer völlig unhaltbaren Aussage für erforderlich hältst. Wahrer wird sie aber dadurch nicht!

herbivore

Wenn du die Liste sortieren darfst, ginge z.B.:

static void RemoveDuplicates(ref ArrayList list) {
	ArrayList newList = new ArrayList();
	list.Sort(); // sortieren - Duplikate stehen jetzt hintereinander
	object previous = new object();
	foreach ( object obj in list ) {
		if ( !Equals( previous, obj ) ) {
			newList.Add( obj );
			previous = obj;
		}
	}
	list = newList;
}

Eventuell mit comparer usw. erweitern. Die Methode kommt auch mit null-Werten in der ArrayList zurecht.

MfG VizOne

[edit]
Falls du keine neue ArrayList erstellen möchtest, geht auch:

static void RemoveDuplicates(ArrayList list) {
	list.Sort();
	object previous = new object();
	int readIndex = 0;
	int writeIndex = 0;
	while ( readIndex < list.Count ) {
		object obj = list[readIndex++];
		if ( !Equals( previous, obj ) ) {
			list[writeIndex++] = obj;
			previous = obj;
		}
	}
	list.RemoveRange( writeIndex, readIndex - writeIndex );
}

[/edit]

Hallo at2oo1,

zur Unterfütterung meiner und Widerlegung deiner Aussage hier mal ein kleiner Vergleich.

Ein Programm, das eine ArrayList mit zehntausend Einträgen erstellt, bei dem alle Einträge mit geradem Index gleich und alle anderen Einträge paarweise unterschiedlich sind und das anschließend die ArrayList mit deiner Methode bereinigt (wobei ich die Guids durch Strings ersetzt habe) benötigt auf meinem Rechner knapp eine halbe Minute Sekunden (gähn).

Ein identisches Programm, jedoch mit folgendem Code, der auf den Beiträgen von Pulpapex und mir beruht, benötigt dagegen weniger als eine zwanzigstel(!) Sekunde.

private static ArrayList CleanArray2 (int startIndex, ArrayList arr)
{
   Hashtable ht = new Hashtable ();
   ArrayList arrNew = new ArrayList ();

   foreach (Object obj in arr) {
      String val = obj.ToString ();
      if (!ht.Contains (val)) {
         arrNew.Add (obj);
         ht [val] = true;
      }
   }

   return arrNew;
}

Das liegt aber nicht nur daran, das der Code ansich effizienter ist, sondern vorallem daran, dass der Aufwand mit der Länge der ArrayList nur linear ansteigt, bei dir dagegen quadratisch.

herbivore

PS: Unter diesen Umständen ist Dein "Gewusst wie heist die devise" schon mehr als peinlich. 🙂

Menno. Meine Methoden verlieren dagegen 🙁

MfG VizOne 😁

NEtter code darauf bin ich nicht gekommen....

Woltle net rumpöbeln..... hat mich nur geärgert das auf meine beiträge im asp forum nie geantwortet wird und hier der bär abgeht.....

also war keine kritik......

@ Herbivore ... danke, sieht sehr gut aus 🙂. So ähnlich hatte ich es inzwischen auch, aber Deine Lösung ist besser 🙂!

Hm, ich würde beim Hashtable aber nicht immer true als value zuweisen - das bedeutet unnötiges Boxing.

MfG VizOne

Hallo VizOne,

klar würde es '= null' auch tun. Aber wenn es danach geht, lässt sich noch einiges verbessern. Ich hatte den Code ja nicht auf Performance, sondern auf die direkte Vergleichbarkeit mit dem Code von at2oo1 optimiert.

Für bessere Performance würde ich eher ToString und wohl sogar das ganze arrNew sowie die Contains-Abfrage weglassen und nachher eine Kopie(?) der Keys-Eigenschaft der Hashtable liefern.

Aber über Perfomance-Verbesserungen, die nicht die Komplexitätsklasse (z.B. linear statt quadratisch) betreffen, kann man genauso schön streiten, wie über die richtige Position von geschweiften Klammern. 🙂

herbivore

Oh je, ich muss ja ganz schön pedantisch erscheinen 8o Das war aber etwas, dass mir direkt ins Auge stach. Weder darüber noch über Klammern möchte ich mich streiten 😁

MfG VizOne

Obwohl der Beitrag schon sehr alt liefert die Suche nach "Duplikate entfernen" diesen Treffer. Für alle die durch die Suche hierher kommen will ich eine aktuelle Möglichkeit zeigen.

Mit den Mitteln von .net 3.5 gibt es mit dem HashSet eine sehr effiziente und einfache Alternative.

private static List<string> RemoveDuplicates3(List<string> list)
{
	return new HashSet<string>(list).ToList();
}

Wie man sieht kann im Konstruktor des HashSet ein IEnumerable<T> für die "Befüllung" des HashSet verwendet werden. Es werden nur eindeutige Elemente hinzugefügt und diese dann per ToList<T>() zurückgegeben.
Alternativ kann die Überladung mit dem IComparer verwendet werden um einen anderen Vergleich zu definieren.

mfG Gü

PS: Wie vorher erwähnt keine direkte Antwort zum Thema sondern ein Hinweis für alle die aktuell über die SuFu hierher kommen.

Wenn Du aus dem string noch ein T machst, und aus der List<> noch ein IEnumerable<>, ist es perfekt ... 😃

Hallo Golo,

vollkommen richtig. Bin zu sehr am Beispiel gehangen 🤔

Aber wenn schon dann "richtig" als Extension-Methode:

namespace gfoidl.Extensions
{
	using System.Collections.Generic;

	public static class MyIEnumerableExtension
	{
		public static IEnumerable<T> RemoveDuplicates<T>(this IEnumerable<T> collection)
		{
			return new HashSet<T>(collection);
		}
	}
}

Danke für den Hinweis!

[Edit]Es könnten dann noch die Überladungen für IComparer, etc. hinzugefügt werden.[/Edit].

mfG Gü

huhu,

Abgesehen von der "kurzen schreibweise" - hat jemand nachgeforscht wie performant es ist? (War ja da oben der aufhänger^^)

😃

Xynratron

Hi,

Zwischen diesen beiden Beiträgen liegen mehr als 4 Jahre.

Das weiß eh jeder. Habe ich ja oben erwähnt dass die Antwort nur deshalb da ist weil ... siehe oben.

Ja hab ich getestet und ziemlich performant (eine schlechte Lösung würde ich ja nicht posten). Es gibt sicher noch mehr Möglichkeiten die im Test einbezogen werden könnten.
Getestet wurde mit folgendem Beispiel:

namespace DuplikateEntfernen
{
	using System;
	using System.Collections.Generic;
	using System.Diagnostics;
	using System.Linq;

	class Program
	{
		static void Main(string[] args)
		{
			const int N = 25000;
			List<string> list = CreateTestList(N);

			Stopwatch sw = new Stopwatch();
			sw.Reset();
			sw.Start();
			var r1 = RemoveDuplicates1(list);
			sw.Stop();
			Console.WriteLine(sw.ElapsedMilliseconds);

			sw.Reset();
			sw.Start();
			var r2 = RemoveDuplicates2(list);
			sw.Stop();
			Console.WriteLine(sw.ElapsedMilliseconds);

			sw.Reset();
			sw.Start();
			var r3 = RemoveDuplicates3(list);
			sw.Stop();
			Console.WriteLine(sw.ElapsedMilliseconds);

			Console.ReadKey();
		}
		//---------------------------------------------------------------------
		private static List<string> RemoveDuplicates1(List<string> list)
		{
			List<string> result = new List<string>(list.Capacity);

			for (int i = 0; i < list.Count; i++)
				if (!result.Contains(list[i]))
					result.Add(list[i]);

			return result;
		}
		//---------------------------------------------------------------------
		private static List<string> RemoveDuplicates2(List<string> list)
		{
			return list.GroupBy(i => i).Select(g => g.Key).ToList();
		}
		//---------------------------------------------------------------------
		private static List<string> RemoveDuplicates3(List<string> list)
		{
			return new HashSet<string>(list).ToList();
		}
		//---------------------------------------------------------------------
		private static List<string> CreateTestList(int n)
		{
			string ident = Guid.NewGuid().ToString();
			List<string> list = new List<string>(n);

			for (int i = 0; i < n; i++)
				if (i % 2 == 0)
					list.Add(ident);
				else
					list.Add(Guid.NewGuid().ToString());

			return list;
		}
	}
}

Ausgabe:

3294
19
7

mfG Gü

Hallo gfoidl,

return new HashSet<string>(list).ToList();  

ist sicher nett kurz und ohne Frage effizient. Allerdings wird dabei in der Regel die Reihenfolge der Elemente durcheinander gewürfelt. Das tut mein Vorschlag oben nicht, obwohl er in der gleichen Aufwandsklasse liegt, wie dein Vorschlag, also quasi genauso schnell ist. So könnte mein Vorschlag mit .NET 3.5 aussehen:

private static List <T> RemoveDuplicates <T> (IEnumerable <T> ienum)
{
   Hashset <T> hs   = new Hashset <T> ();
   List <T>    list = new List <T> ();

   foreach (T t in ienum) {
      if (hs.Add (t)) {
         list.Add (t);
      }
   }

   return list;
}

herbivore

Hallo herbivore,

wenn es darum geht dass die Elementreihenfolge erhalten bleibt, ist deine Variante die geeignete und ca. 7...8x schneller als das Sortieren des HashSet.

Sollen nur die Duplikate ohne Rücksicht auf die Elementreihenfolge entfernt werden ist die "kurze HashSet-Variante" die schnellste.

Zum Vergleich: In beiden Möglichkeiten wird die Elementreihenfolge behalten. Wie bereits erwähnt ist zweite Variante ca. 7...8x langsamer.

private static List<string> RemoveDuplicatesKeepOrder(List<string> list)
{
	HashSet<string> hs = new HashSet<string>();
	List<string> r = new List<string>();

	foreach (string s in list)
	{
		if (hs.Add(s))
			r.Add(s);
	}

	return r;
}
//---------------------------------------------------------------------
private static List<string> RemoveDuplicates(List<string> list)
{
	return new HashSet<string>(list).OrderBy(s => s).ToList();
}

mfG Gü

PS: Ich glaube das Thema ist vorerst genügend behandelt worden. 😉

Eine zusätzliche Überladung zur Angabe des Comparers (IEqualityComparer<T>) wäre auch nicht schlecht

Hallo gfoidl,

PS: Ich glaube das Thema ist vorerst genügend behandelt worden. 😉

im Kern sicher. Allerdings sind mir noch zwei Kleinigkeiten aufgefallen. 🙂

Zum Vergleich: In beiden Möglichkeiten wird die Elementreihenfolge behalten.

Naja, nicht wirklich. 🙂 Bei meinem Vorschlag wird die Reihenfolge der Elemente behalten, bei deinem neuen Vorschlag mit OrderBy werden die Elemente nachträglich in eine bestimmte Reihenfolge gebracht. Das ist nicht das gleiche, wenn die Elemente nicht vorher schon in dieser Reihenfolge waren. Stell dir eine Liste von Messwerten vor, aus denen die Duplikate entfernt werden sollen, die aber in der zeitlichen Reihenfolge der Messung bleiben sollen. Das würde mit OrderBy (in der Regel) nicht funktionieren.

Mal abgesehen davon, dass man bei der Verwendung von OrderBy nur Auszählungen mit Elementen verarbeiten könnte, die von sich aus vergleichbar sind (also IComparable<T> implementieren). Mit dem Vorschlag von kleines_eichhoernchen vermeidet man zumindest das Problem aus diesem Absatz. An der Aussage aus dem vorigen Absatz ändert sich aber auch dadurch nichts.

List<string> RemoveDuplicatesKeepOrder(List<string> list)  

Bei der Wiedergabe meines Vorschlags, hast du die Parametrisierung geändert. Dabei hatte ich diese aus gutem Grund so gewählt, dass der Parametertyp allgemein (IEnumerable <T>) und der Rückgabetyp spezifisch (List<T>) ist. Diese Typenwahl würde ich für alle Vorschläge empfehlen. Das Warum müssen und sollten wir aber in der Tat nicht hier diskutieren, weil es dazu schon einen passend(er)en Thread gibt: IList<T> oder List<T> als Parameter- bzw. Rückgabetyp?

herbivore

Zusammenfassend:

namespace gfoidl.Extensions
{
	using System.Collections.Generic;
	using System.Linq;
	//-------------------------------------------------------------------------
	/// <summary>
	/// Erweiterungsmethoden für IEnumerable(T)
	/// </summary>
	public static class MyIEnumerableExtensions
	{
		public static List<T> RemoveDuplicates<T>(this IEnumerable<T> collection)
		{
			return new HashSet<T>(collection).ToList();
		}
		//---------------------------------------------------------------------
		public static List<T> RemoveDuplicates<T>(
			this IEnumerable<T> collection,
			IEqualityComparer<T> comparer)
		{
			return new HashSet<T>(collection, comparer).ToList();
		}
		//---------------------------------------------------------------------
		public static List<T> RemoveDuplicatesKeepOrder<T>(
			this IEnumerable<T> collection)
		{
			HashSet<T> hashSet = new HashSet<T>();
			List<T> result = new List<T>(collection.Count());

			foreach (T item in collection)
				if (hashSet.Add(item))
					result.Add(item);

			return result;
		}
		//---------------------------------------------------------------------
		public static List<T> RemoveDuplicatesKeepOrder<T>(
			this IEnumerable<T> collection,
			IEqualityComparer<T> comparer)
		{
			HashSet<T> hashSet = new HashSet<T>(comparer);
			List<T> result = new List<T>(collection.Count());

			foreach (T item in collection)
				if (hashSet.Add(item))
					result.Add(item);

			return result;
		}
	}
}

Naja, nicht wirklich. 🙂

Stimmt. Ich darf/kann nicht davon ausgehen dass die IEnumerable<T> sortiert ist.

Bezüglich Parametriesierung ist dein Hinweis auch korrekt. Ich weiß die Unterschiede nur wundere ich mich selber warum ich dabei manchmal so schlampig vorgehe. Ich gebe List<T> zurück wenn das Ergebnis eine List<T> ist und IEnumerable<T> gebe ich zurück wenn ich über das Ergebnis iteriere (zB mit yield) - eigentlich logisch, vermutlich Ansätze von Morbus Alzheimer 😁

Mal abgesehen davon, dass man bei der Verwendung von OrderBy nur Auszählungen mit Elementen verarbeiten könnte, die von sich aus vergleichbar sind (also IComparable<T> implementieren).

Dem kann ich nicht ganz zustimmen. OrderBy ist eine Erweiterungsmethode für IEnumerable<T> und wenn kein Vergleich angegeben wird so wird der Standardvergleich verwendet - selbiges gilt für das HashSet<T>.

mfG Gü

Hallo gfoidl,

OrderBy ist eine Erweiterungsmethode für IEnumerable<T> und wenn kein Vergleich angegeben wird so wird der Standardvergleich verwendet

Ja, das ist wahr. Aber was ist denn der Standardvergleich? Das ist die Rückgabe der Comparer<T>.Default-Eigenschaft, zu der die Doku sagt:

Wenn der Typ T die generische System.IComparable<T>-Schnittstelle nicht implementiert, gibt diese Eigenschaft einen Comparer<T> zurück, der die System.IComparable-Schnittstelle verwendet.

Daher meine Aussage, dass der Typ IComparable<T> implementieren muss, denn wenn das nicht der Fall wäre, wird (von der Behandlung für Nullable-Typen mal abgesehen) der meistens völlig unbrauchbare (ObjectComparer<T> bzw.) Comparer.Default-Comparers verwendet.

new List<T>(collection.Count());  

Ich hatte auch überlegt, eine initiale Größe für die Ergebnisliste anzugeben. Allerdings: wie man es macht, macht man es verkehrt. Wenn weniger oder gar keine doppelten Einträge vorhanden sind, wäre es passend, die Größe der Input-Collection zu verwenden und es wäre ungünstiger mit der Standardgröße zu beginnen. Wenn viele oder fast alle Einträge entfernt werden, ist es genau andersherum. Da außerdem bei IEnumerable<T> die Count.Methode die Enumeration tatsächlich einmal komplett durchlaufen durchlaufen muss, um die Größe zu ermitteln, ist es wohl doch besser mit der Standardgröße zu beginnen.

Zusammenfassend:

Dein Code wäre doch - evtl. nach Berücksichtigung meiner Anmerkungen - was für .NET-Komponenten und C#-Snippets, oder?

herbivore

Hallo herbivore,

Ich hatte auch überlegt, eine initiale Größe für die Ergebnisliste anzugeben.

Hab mir das auch noch mals überlegt und getestet. Da beide Varianten (mit und ohne Anfangskapizität) eine O(n)-Operation sind und wirklich keine Annahme über die Anzahl von Duplikaten getroffen werden kann schneidet die Variante ohne Anfangskapazität besser ab.
Hab auch probiert die IEnumerable<T> in ein T[] überzuführen damit eine for-Schleife verwendet werden kann. Bringt aber nichts da über IEnumerable<T> sowieso iteriert werden muss.

Dein Code wäre doch - evtl. nach Berücksichtigung meiner Anmerkungen - was für .NET-Komponenten und C#-Snippets, oder?

Habs unter Duplikate aus IEnumerable<T> entfernen eingestellt.

Danke für die wertvollen Hinweise und Ratschläge (damit sie mir wieder ins Gedächtnis gerufen werden um in Zukunft öfter daran zu denken).

mfG Gü

Hallo,

bisher haben wir die Enumerable.Distinct-Methode noch gar nicht erwähnt. Die ist seit LINQ (also .net 3.5) auch neu.

mfG Gü