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