Efficacement fusionner les tableaux de chaîne dans .NET, en gardant les valeurs distinctes

Pourquoi pensez-vous qu'il serait inefficace? Pour autant que je suis conscient, à la fois Concat et Distincts, sont évalués paresseusement, à l'aide d'un HashSet derrière les scènes Distinctes pour garder une trace des éléments qui ont déjà été retournés.

Je ne suis pas sûr comment vous pouvez gérer pour le rendre plus efficaces que d'une manière générale 🙂

EDIT: Distinctes utilise Set (une classe interne) au lieu de HashSet, mais l'essentiel est toujours correcte. C'est vraiment un très bon exemple de la façon soignée LINQ est. La réponse la plus simple est à peu près aussi efficace que vous pouvez atteindre sans plus de connaissances 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;
        }
    }
}

Avertissement C'est l'optimisation prématurée. Pour votre exemple des tableaux, utiliser le 3.5 méthodes d'extension. Jusqu'à ce que vous savez que vous avez un problème de performance dans cette région, vous devez utiliser le code de bibliothèque.

Si vous pouvez trier les tableaux, ou ils sont triés quand vous arrivez à ce point dans le code, vous pouvez utiliser les méthodes suivantes.

Ces va tirer un seul élément à la fois, et de produire le "plus" de l'élément, puis chercher un nouvel élément à partir de la source correspondante, jusqu'à ce que les deux sources sont épuisés. Dans le cas où l'élément actuel récupérée à partir de ces deux sources sont égaux, il va produire l'une à partir de la première source, et de les ignorer 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();
}
}
}

Noter que si l'une des sources contient des doublons, vous pouvez voir les doublons dans la sortie. Si vous souhaitez supprimer ces doublons dans les listes 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;
}
}
}

Noter qu'aucun de ces en interne l'utilisation d'une structure de données à conserver une copie des données, de sorte qu'ils seront bon marché si l'entrée est triée. Si vous ne pouvez pas ou ne voulez pas vous garantir que, vous devez utiliser l'3.5 méthodes d'extension que vous avez déjà trouvé.

Voici un exemple de code qui appelle 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);

Vous ne savez pas où l'approche est plus rapide, jusqu'à ce que vous mesurez. Le LINQ façon est élégant et facile à comprendre.

Une autre façon est de mettre en œuvre un ensemble comme un tableau de hachage (Dictionnaire) et ajoutez tous les éléments des deux tableaux à l'ensemble. Puis utiliser.Les touches.Méthode ToArray() pour créer le tableau résultant.