Fusionnez efficacement les tableaux de chaînes dans .NET en conservant des valeurs distinctes
https://stackoverflow.com/questions/146358
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'utilise .NET 3.5. J'ai deux tableaux de chaînes pouvant partager une ou plusieurs valeurs:
string[] list1 = new string[] { "apple", "orange", "banana" };
string[] list2 = new string[] { "banana", "pear", "grape" };
Je voudrais un moyen de les fusionner dans un tableau sans valeurs dupliquées:
{ "apple", "orange", "banana", "pear", "grape" }
Je peux le faire avec LINQ:
string[] result = list1.Concat(list2).Distinct().ToArray();
mais j'imagine que ce n'est pas très efficace pour les grands tableaux.
Y a-t-il un meilleur moyen?
La solution
string[] result = list1.Union(list2).ToArray();
from msdn : " Cette méthode exclut les doublons de la déclaration ensemble. Ce comportement diffère de celui de la méthode Concat (TSource), qui renvoie tous les éléments des séquences d’entrée, y compris les doublons.
Autres conseils
Pourquoi imaginez-vous que ce serait inefficace? Autant que je sache, Concat et Distinct sont tous deux évalués, en utilisant un HashSet en coulisse pour Distinct afin de garder la trace des éléments déjà renvoyés.
Je ne sais pas comment vous pourriez le rendre plus efficace que cela de manière générale:)
EDIT: Distinct utilise actuellement Set (une classe interne) au lieu de HashSet, mais l’essentiel est toujours correct. C’est un très bon exemple de la beauté de LINQ. La réponse la plus simple est à peu près aussi efficace que possible sans connaissances supplémentaires du domaine.
L'effet est l'équivalent de:
public static IEnumerable<T> DistinctConcat<T>(IEnumerable<T> first, IEnumerable<T> second)
{
HashSet<T> returned = new HashSet<T>();
foreach (T element in first)
{
if (returned.Add(element))
{
yield return element;
}
}
foreach (T element in second)
{
if (returned.Add(element))
{
yield return element;
}
}
}
.NET 3.5 a introduit la classe HashSet qui pourrait faire ceci:
IEnumerable<string> mergedDistinctList = new HashSet<string>(list1).Union(list2);
Pas sûr des performances, mais il devrait battre l'exemple de Linq que vous avez donné.
EDIT: Je me suis trompé. Les implémentations paresseuses de Concat et Distinct ont un avantage clé en termes de mémoire ET de rapidité. Concat / Distinct est environ 10% plus rapide et enregistre plusieurs copies de données.
j'ai confirmé par le code:
Setting up arrays of 3000000 strings overlapping by 300000
Starting Hashset...
HashSet: 00:00:02.8237616
Starting Concat/Distinct...
Concat/Distinct: 00:00:02.5629681
est la sortie de:
int num = 3000000;
int num10Pct = (int)(num / 10);
Console.WriteLine(String.Format("Setting up arrays of {0} strings overlapping by {1}", num, num10Pct));
string[] list1 = Enumerable.Range(1, num).Select((a) => a.ToString()).ToArray();
string[] list2 = Enumerable.Range(num - num10Pct, num + num10Pct).Select((a) => a.ToString()).ToArray();
Console.WriteLine("Starting Hashset...");
Stopwatch sw = new Stopwatch();
sw.Start();
string[] merged = new HashSet<string>(list1).Union(list2).ToArray();
sw.Stop();
Console.WriteLine("HashSet: " + sw.Elapsed);
Console.WriteLine("Starting Concat/Distinct...");
sw.Reset();
sw.Start();
string[] merged2 = list1.Concat(list2).Distinct().ToArray();
sw.Stop();
Console.WriteLine("Concat/Distinct: " + sw.Elapsed);
Avertissement : il s'agit d'une optimisation prématurée. Pour vos exemples de tableaux, utilisez les méthodes d’extension 3.5. Jusqu'à ce que vous sachiez que vous rencontrez un problème de performances dans cette région, vous devez utiliser le code de la bibliothèque.
Si vous pouvez trier les tableaux, ou s'ils sont triés lorsque vous atteignez ce point dans le code, vous pouvez utiliser les méthodes suivantes.
Ceux-ci vont tirer un élément des deux et produire le "plus bas" élément, puis extrayez un nouvel élément de la source correspondante jusqu'à ce que les deux sources soient épuisées. Dans le cas où l'élément en cours extrait des deux sources est égal, il produira celui de la première source et les ignorera dans les deux sources.
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2)
{
return Merge(source1, source2, Comparer<T>.Default);
}
private static IEnumerable<T> Merge<T>(IEnumerable<T> source1,
IEnumerable<T> source2, IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source1))
throw new ArgumentNullException("source1");
if (Object.ReferenceEquals(null, source2))
throw new ArgumentNullException("source2");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T>
enumerator1 = source1.GetEnumerator(),
enumerator2 = source2.GetEnumerator())
{
Boolean more1 = enumerator1.MoveNext();
Boolean more2 = enumerator2.MoveNext();
while (more1 && more2)
{
Int32 comparisonResult = comparer.Compare(
enumerator1.Current,
enumerator2.Current);
if (comparisonResult < 0)
{
// enumerator 1 has the "lowest" item
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
else if (comparisonResult > 0)
{
// enumerator 2 has the "lowest" item
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
else
{
// they're considered equivalent, only yield it once
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
more2 = enumerator2.MoveNext();
}
}
// Yield rest of values from non-exhausted source
while (more1)
{
yield return enumerator1.Current;
more1 = enumerator1.MoveNext();
}
while (more2)
{
yield return enumerator2.Current;
more2 = enumerator2.MoveNext();
}
}
}
Notez que si l'une des sources contient des doublons, vous risquez de voir des doublons dans la sortie. Si vous souhaitez supprimer ces doublons dans les listes déjà triées, utilisez la méthode suivante:
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source)
{
return CheapDistinct<T>(source, Comparer<T>.Default);
}
private static IEnumerable<T> CheapDistinct<T>(IEnumerable<T> source,
IComparer<T> comparer)
{
#region Parameter Validation
if (Object.ReferenceEquals(null, source))
throw new ArgumentNullException("source");
if (Object.ReferenceEquals(null, comparer))
throw new ArgumentNullException("comparer");
#endregion
using (IEnumerator<T> enumerator = source.GetEnumerator())
{
if (enumerator.MoveNext())
{
T item = enumerator.Current;
// scan until different item found, then produce
// the previous distinct item
while (enumerator.MoveNext())
{
if (comparer.Compare(item, enumerator.Current) != 0)
{
yield return item;
item = enumerator.Current;
}
}
// produce last item that is left over from above loop
yield return item;
}
}
}
Notez qu’aucun d’entre eux n’utilisera en interne une structure de données pour conserver une copie des données. Ils seront donc économiques si l’entrée est triée. Si vous ne pouvez pas ou ne voulez pas vous en garantir, vous devez utiliser les méthodes d'extension 3.5 déjà trouvées.
Voici un exemple de code appelant les méthodes ci-dessus:
String[] list_1 = { "apple", "orange", "apple", "banana" };
String[] list_2 = { "banana", "pear", "grape" };
Array.Sort(list_1);
Array.Sort(list_2);
IEnumerable<String> items = Merge(
CheapDistinct(list_1),
CheapDistinct(list_2));
foreach (String item in items)
Console.Out.WriteLine(item);
Créer une table de hachage avec vos valeurs comme clés (en ajoutant uniquement celles qui ne sont pas déjà présentes), puis convertir les clés en tableau pourrait être une solution viable.
Vous ne savez pas quelle approche est la plus rapide avant de la mesurer. La méthode LINQ est élégante et facile à comprendre.
Une autre méthode consiste à implémenter un ensemble sous forme de tableau de hachage (Dictionnaire) et à ajouter tous les éléments des deux tableaux à l'ensemble. Ensuite, utilisez la méthode set.Keys.ToArray () pour créer le tableau résultant.
