una - string[] c# ejemplos

Combinar de manera eficiente matrices de cadenas en.NET, manteniendo distintos valores

Question

Estoy usando .NET 3.5. Tengo dos matrices de cadenas, que pueden compartir uno o más valores:

string[] list1 = new string[] { "apple", "orange", "banana" };
string[] list2 = new string[] { "banana", "pear", "grape" };

Me gustaría una forma de fusionarlos en una matriz sin valores duplicados:

{ "apple", "orange", "banana", "pear", "grape" }

Puedo hacer esto con LINQ:

string[] result = list1.Concat(list2).Distinct().ToArray();

pero me imagino que no es muy eficiente para arreglos grandes.

¿Hay una mejor manera?

Answer 1

¿Por qué te imaginas que sería ineficiente? Por lo que yo sé, tanto Concat como Distinct se evalúan perezosamente, usando un HashSet detrás de escena para que Distinct realice un seguimiento de los elementos que ya han sido devueltos.

No estoy seguro de cómo lograría hacerlo más eficiente que eso de manera general :)

EDITAR: Distinct en realidad usa Set (una clase interna) en lugar de HashSet, pero la esencia sigue siendo correcta. Este es un muy buen ejemplo de cuán ordenado es LINQ. La respuesta más simple es casi tan eficiente como se puede lograr sin más conocimiento de dominio.

El efecto es el equivalente 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;
        }
    }
}

Answer 2

.NET 3.5 introdujo la clase HashSet que podría hacer esto:

IEnumerable<string> mergedDistinctList = new HashSet<string>(list1).Union(list2);

No estoy seguro del rendimiento, pero debería superar el ejemplo de Linq que diste.

EDITAR: Estoy corregido. La implementación diferida de Concat y Distinct tiene una memoria clave Y una ventaja de velocidad. Concat / Distinct es aproximadamente un 10% más rápido y guarda múltiples copias de datos.

Confirmé a través del código:

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

es el resultado 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);

Answer 3

No sabes qué enfoque es más rápido hasta que lo midas. La forma de LINQ es elegante y fácil de entender.

Otra forma es implementar un conjunto como una matriz hash (Diccionario) y agregar todos los elementos de ambas matrices al conjunto. Luego use el método set.Keys.ToArray () para crear la matriz resultante.

Answer 4

Probablemente, la creación de una tabla hash con sus valores como claves (solo agregue aquellos que aún no están presentes) y la conversión de las claves a una matriz podría ser una solución viable.

Answer 5

Descargo de responsabilidad Esta es una optimización prematura. Para sus matrices de ejemplo, use los métodos de extensión 3.5. Hasta que sepa que tiene un problema de rendimiento en esta región, debe usar el código de la biblioteca.

Si puede ordenar las matrices, o están ordenadas cuando llega a ese punto en el código, puede usar los siguientes métodos.

Estos extraerán un ítem de ambos, y producirán el ítem "más bajo", luego buscarán un nuevo ítem de la fuente correspondiente, hasta que ambas fuentes se agoten. En el caso en que el elemento actual obtenido de las dos fuentes sea igual, producirá el de la primera fuente y saltará en ambas fuentes.

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();
        }
    }
}

Tenga en cuenta que si una de las fuentes contiene duplicados, es posible que vea duplicados en la salida. Si desea eliminar estos duplicados en las listas ya ordenadas, use el siguiente método:

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;
        }
    }
}

Tenga en cuenta que ninguno de estos utilizará internamente una estructura de datos para guardar una copia de los datos, por lo que serán baratos si la entrada está ordenada. Si no puede, o no lo garantizará, debe usar los métodos de extensión 3.5 que ya ha encontrado.

Aquí hay un código de ejemplo que llama a los métodos anteriores:

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);

Answer 6

string[] result = list1.Union(list2).ToArray();

from msdn : "Este método excluye los duplicados del conjunto de resultados. Este es un comportamiento diferente al método Concat (TSource), que devuelve todos los elementos en las secuencias de entrada, incluidos los duplicados".