c# - son - coincidencia de elementos de dos listas(o matrices)

obtener elemento de una lista c#

Question

Tengo un problema con mi trabajo que con suerte se reduce a lo siguiente: Tengo dos List<int> s, y quiero ver si alguno de los int s en ListA son iguales a cualquier int en ListB . (Pueden ser arreglos si eso hace la vida más fácil, pero creo que List<> tiene algo de magia incorporada que podría ayudar.) Y estoy seguro de que este es un problema LINQ, pero estoy trabajando en 2.0 aquí.

Mi solución hasta ahora ha sido foreach través de ListA, y luego foreach través de ListB,

foreach (int a in ListA)
{
    foreach (int b in ListB)
    {
        if (a == b)
        {
            return true;
        }
    }
}

que en realidad era bastante resbaladizo cuando tenían tres elementos cada uno, pero ahora tienen 200 de largo y con frecuencia no coinciden, así que tenemos el peor de los casos de comparaciones de N ^ 2. Incluso 40,000 comparaciones pasan bastante rápido, pero creo que me puede faltar algo, ya que N ^ 2 parece bastante ingenuo para este problema en particular.

¡Gracias!

Answer 1

¿Qué hay de usar el método BinarySearch en lugar de iterar sobre todos los elementos en el bucle interno?

Answer 2

Cargue la totalidad de ListA en una instancia de HashSet y luego pruebe el elemento foreach en ListB frente a HastSet: estoy bastante seguro de que esto sería O (N).

//untested code ahead
HashSet<int> hashSet = new HashSet<int>(ListA);
foreach (int i in ListB)
{
    if (hashSet.Contains(i))
        return true;
}

Esto es lo mismo en una línea:

return new HashSet<int>(ListA).Overlaps(ListB);

HashSet no existe en .NET 3.5, por lo que en .NET 2.0 puede usar Dictionary<int,object> (en lugar de usar HashSet<int> ) y siempre almacenar null como el objeto / valor en el Dictionary desde que está solo interesado en las llaves.

Answer 3

Chris da una solución de O (N) mediante hash. Ahora, dependiendo del factor constante (debido a hashing), podría valer la pena considerar una solución O (N log (N)) por clasificación. Hay algunas variantes diferentes que puede considerar dependiendo de su caso de uso.

1. Sort ListB (O (N log (N)), y utiliza un algoritmo de búsqueda para analizar cada elemento en ListA (que de nuevo es O (N) * O (log (N))).

2. Ordene tanto ListA como ListB (O (N log (N)), y use un algoritmo O (N) para comparar estas listas en busca de duplicados.

Si ambas listas se van a utilizar más de una vez, se prefiere el segundo método.

Answer 4

En lugar de iterar a través de cada lista, eche un vistazo al método List.Contains :

foreach (int a in ListA)
{
  if (ListB.Contains(a))
    return true;
}

Answer 5

Con LINQ , esto es trivial, ya que puedes llamar al método de extensión Intersect en la clase Enumerable para darte la intersección establecida de las dos matrices:

var intersection = ListA.Intersect(ListB);

Sin embargo, esta es la intersección del conjunto , lo que significa que si ListA y ListB no tienen valores únicos, no obtendrá ninguna copia. En otras palabras, si tiene lo siguiente:

var ListA = new [] { 0, 0, 1, 2, 3 };
var ListB = new [] { 0, 0, 0, 2 };

Entonces ListA.Intersect(ListB) produce:

{ 0, 2 }

Si estás esperando:

{ 0, 0, 2 }

Luego, tendrá que llevar un conteo de los artículos usted mismo y ceder / disminuir a medida que escanea las dos listas.

En primer lugar, querría recopilar un Dictionary<TKey, int> con las listas de los elementos individuales:

var countsOfA = ListA.GroupBy(i => i).ToDictionary(g => g.Key, g => g.Count());

Desde allí, puede escanear ListB y colocarlo en una lista cuando encuentre un elemento en countsOfA :

// The items that match.
IList<int> matched = new List<int>();

// Scan 
foreach (int b in ListB)
{
    // The count.
    int count;

    // If the item is found in a.
    if (countsOfA.TryGetValue(b, out count))
    {
        // This is positive.
        Debug.Assert(count > 0);

        // Add the item to the list.
        matched.Add(b);

        // Decrement the count.  If
        // 0, remove.
        if (--count == 0) countsOfA.Remove(b);
    }
}

Puede resumir esto en un método de extensión que aplaza la ejecución de la siguiente manera:

public static IEnumerable<T> MultisetIntersect(this IEnumerable<T> first,
    IEnumerable<T> second)
{
    // Call the overload with the default comparer.
    return first.MultisetIntersect(second, EqualityComparer<T>.Default);
}

public static IEnumerable<T> MultisetIntersect(this IEnumerable<T> first,
    IEnumerable<T> second, IEqualityComparer<T> comparer)
{
    // Validate parameters.  Do this separately so check
    // is performed immediately, and not when execution
    // takes place.
    if (first == null) throw new ArgumentNullException("first");
    if (second == null) throw new ArgumentNullException("second");
    if (comparer == null) throw new ArgumentNullException("comparer");

    // Defer execution on the internal
    // instance.
    return first.MultisetIntersectImplementation(second, comparer);
}

private static IEnumerable<T> MultisetIntersectImplementation(
    this IEnumerable<T> first, IEnumerable<T> second, 
    IEqualityComparer<T> comparer)
{
    // Validate parameters.
    Debug.Assert(first != null);
    Debug.Assert(second != null);
    Debug.Assert(comparer != null);

    // Get the dictionary of the first.
    IDictionary<T, long> counts = first.GroupBy(t => t, comparer).
        ToDictionary(g => g.Key, g.LongCount(), comparer);

    // Scan 
    foreach (T t in second)
    {
        // The count.
        long count;

        // If the item is found in a.
        if (counts.TryGetValue(t, out count))
        {
            // This is positive.
            Debug.Assert(count > 0);

            // Yield the item.
            yield return t;

            // Decrement the count.  If
            // 0, remove.
            if (--count == 0) counts.Remove(t);
        }
    }
}

Tenga en cuenta que ambos enfoques son (y me disculpo si estoy eliminando la notación de Big-O aquí) O(N + M) donde N es el número de elementos en el primer conjunto, y M es el número de elementos en el segundo formación. Debe escanear cada lista solo una vez, y se supone que obtener los códigos hash y realizar búsquedas en los códigos hash es una operación O(1) (constante).