Laden...

Duplikate aus IEnumerable<T> entfernen bzw. unterschiedliche Elemente holen

Erstellt von gfoidl vor 14 Jahren Letzter Beitrag vor 14 Jahren 10.352 Views
gfoidl Themenstarter:in
6.911 Beiträge seit 2009
vor 14 Jahren
Duplikate aus IEnumerable<T> entfernen bzw. unterschiedliche Elemente holen

Beschreibung:

Erweiterungsmethoden für IEnumerable<T> die eindeutige Elemente zurückgeben.


namespace gfoidl.Extensions
{
	using System.Collections.Generic;
	using System.Linq;
	//-------------------------------------------------------------------------
	/// <summary>
	/// Erweiterungsmethoden für <see cref="IEnumerable&lt;T>"/>
	/// </summary>
	public static class MyIEnumerableExtensions
	{
		//---------------------------------------------------------------------
		/// <summary>
		/// Gibt eine <see cref="List&lt;T>"/> mit eindeutigen Werten
		/// zurück.
		/// </summary>
		/// <typeparam name="T">
		/// Der Typ der aufzulistenden Objekte.
		/// </typeparam>
		/// <param name="collection">
		/// Die Auflistung.
		/// </param>
		/// <returns>
		/// Auflistung ohne Duplikate.
		/// </returns>
		public static List<T> GetDistinct<T>(
			this IEnumerable<T> collection)
		{
			return collection.GetDistinct(false);
		}
		//---------------------------------------------------------------------
		/// <summary>
		/// Gibt eine <see cref="List&lt;T>"/> mit eindeutigen Werten
		/// zurück.
		/// </summary>
		/// <typeparam name="T">
		/// Der Typ der aufzulistenden Objekte.
		/// </typeparam>
		/// <param name="collection">
		/// Die Auflistung.
		/// </param>
		/// <param name="keepOrder">
		/// Gitb an ob die Reihenfolge der Elemente beibehalten werden soll.
		/// </param>
		/// <returns>
		/// Auflistung ohne Duplikate.
		/// </returns>
		public static List<T> GetDistinct<T>(
			this IEnumerable<T> collection,
			bool keepOrder)
		{
			if (keepOrder)
			{
				HashSet<T> hashSet = new HashSet<T>();

				// Eine Kapazität wird nicht angegeben da es sich gezeigt
				// dass die Wahl dieser Größe sehr schwierig ist. Wird die
				// Länge per Count ermittelt so wird über die ganze Enumeration
				// iteriert und das ist die gleiche Aufwandsklasse wie das
				// umkopieren der Elemente wenn keine Kapazität angegeben wird
				// (beide sind O(n)).
				List<T> result = new List<T>();

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

				return result;
			}
			else
				return new HashSet<T>(collection).ToList();
		}
		//---------------------------------------------------------------------
		/// <summary>
		/// Gibt ein <see cref="IEnumerable&lt;T>"/> mit eindeutigen Werten
		/// zurück.
		/// </summary>
		/// <typeparam name="T">
		/// Der Typ der aufzulistenden Objekte.
		/// </typeparam>
		/// <param name="collection">
		/// Die Auflistung.
		/// </param>
		/// <returns>
		/// Auflistung ohne Duplikate.
		/// </returns>
		public static IEnumerable<T> GetDistinctEnumerable<T>(
			this IEnumerable<T> collection)
		{
			HashSet<T> hashSet = new HashSet<T>();
			foreach (T item in collection)
				if (hashSet.Add(item))
					yield return item;
		}
		//---------------------------------------------------------------------
		/// <summary>
		/// Gibt eine <see cref="List&lt;T>"/> mit eindeutigen Werten
		/// zurück.
		/// </summary>
		/// <typeparam name="T">
		/// Der Typ der aufzulistenden Objekte.
		/// </typeparam>
		/// <param name="collection">
		/// Die Auflistung.
		/// </param>
		/// <param name="keepOrder">
		/// Gitb an ob die Reihenfolge der Elemente beibehalten werden soll.
		/// </param>
		/// <param name="comparer">
		/// Die <see cref="IEqualityComparer&lt;T>"/>-Implementierung, die 
		/// zum Vergleichen von Schlüsseln verwendet werden soll, oder null, 
		/// wenn der Standard-<see cref="EqualityComparer&lt;T>"/> für diesen 
		/// Schlüsseltyp verwendet werden soll.
		/// </param>
		/// <returns>
		/// Auflistung ohne Duplikate.
		/// </returns>
		public static List<T> GetDistinct<T>(
			this IEnumerable<T> collection,
			bool keepOrder,
			IEqualityComparer<T> comparer)
		{
			if (keepOrder)
			{
				HashSet<T> hashSet = new HashSet<T>(comparer);
				List<T> result = new List<T>();

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

				return result;
			}
			else
				return new HashSet<T>(collection, comparer).ToList();
		}
	}
}

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

Es liegt natürlich der Vergleich zu Enumerable.Distinct (LINQ) nahe. Das angehängte Bild zeigt dass die hier vorgestellten Methoden performanter sind.

mfG Gü

Edit 23.06.2009: Geändert auf Hinweis von kleines_eichhoernchen und JAck30lena
Edit 17.08.2010: Link korrigiert

Schlagwörter: Duplikate, List<T>, IEnumerable<T>, Duplikate entfernen, HashSet<T>, List, HashSet

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

3.971 Beiträge seit 2006
vor 14 Jahren

Hallo gfoidl,
du hast in den letzten beiden Überladungen jeweils den Parameter keepOrder, verwendest diesen aber nirgendswo.

Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...

gfoidl Themenstarter:in
6.911 Beiträge seit 2009
vor 14 Jahren

Hallo kleines_eichhoernchen,

danke für den Hinweis. Habs geändert.

Ich glaub ich bin überarbeitet und brauch Urlaub - solche Fehler passieren mir normalerweise nicht 😉.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

1.820 Beiträge seit 2005
vor 14 Jahren

Hallo!

Bleibt nur noch zu erwähnen, dass HashSet<T> erst im 3.5er-Framework existiert.

Nobody is perfect. I'm sad, i'm not nobody 🙁

Gelöschter Account
vor 14 Jahren

du machst kein remove. du extrahierst.

daher ist "RemoveDuplicates" nciht treffend. ich würde dir "GetUniquesFrom" (oder auch ohne das 'From') empfehlen.

gfoidl Themenstarter:in
6.911 Beiträge seit 2009
vor 14 Jahren

du machst kein remove. du extrahierst.

daher ist "RemoveDuplicates" nciht treffend. i

Berechtigter Einwand. Die Benennung soll auch exakt sein. 👍

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

Gelöschter Account
vor 14 Jahren

und die kommetare passen auch nciht ganz 😃

Entfernt Duplikate aus einem <see cref="IEnumerable&lt;T>"/>.

es sollte heißen: "Erzeugt eine neue Liste ohne Duplikate und gibt diese zurück.

2.891 Beiträge seit 2004
vor 14 Jahren

Schön wäre auch noch, wenn noch der Unterschied zur IEnumerable(T).Distinct-Methode (System.Collections.Generic) erklärt wird.

Gruß,
dN!3L

gfoidl Themenstarter:in
6.911 Beiträge seit 2009
vor 14 Jahren

Hallo,

der Unterschied zu Distinct ist dass die hier vorgestellte Möglichkeite schneller arbeitet. Warum weiß ich nicht. Ich hab mir zwar den Code von Distinct mit dem Reflector angeschaut aber das ist mühsam. Distinct gibt ein IEnumerable<T> zurück - genau wie eine Methode oben - und deshalb wird dort ein yield verwendet. Yield ist jedoch ein C#-Befehl und wird beim Kompilieren in "Compiler generatred Code" ersetzt. Die Mühe diesen Code zu analysieren hab ich mir erspart.

Im obigen Diagramm ist jedoch ein Vergleich der benötigten Ticks für die Ausführung gegeben. Daraus ist ersichtlich dass Distinct nicht so gut abschneidet.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"