repetidos - mostrar elementos de una lista c#

Contar elementos existentes en 2 Listas

Question

Tengo dos listas de tipo int, como la List A y la List B Quiero verificar cuántos elementos de la List A hay en la List B Soy capaz de hacer esto, pero lo que puede ser una manera eficiente es que estoy tratando de evitar foreach , ya que la optimización es un objetivo primordial en mi código.

List<int> A = new List<int>;
List<int> B = new List<int>;
// Some logic....item added in both lists. Then

foreach(var item in A)
{
    if (B.Contains(item))
    {
        // Subtract number of duplicates
    }
}

Intenté usar Intersect y Any , pero eso devuelve bool por lo que no puedo aplicarlos por completo.

Answer 1

Bueno, desde un punto de vista teórico, ya que tienes que verificar completamente una de las dos listas y para cada elemento de esa lista verificar si está contenido en la otra, lo único que puedes hacer para mejorar asintóticamente el método es mejorar La búsqueda del elemento en la otra lista. Las posibilidades que veo son las siguientes (supongo que estamos buscando elementos de la lista A en el elemento B ):

• Ordene (haga fácilmente en LINQ usando OrderBy ) los elementos en la lista B - complejidad O(m log m) - y busque los elementos en ella usando el algoritmo de búsqueda binaria . La complejidad general es O(n log m) (tomando n como el número de elementos en A y m como el número de elementos en B ).
• Transformar (usando el método ToDictionary ) B en un diccionario (complejidad O(m) ). De esta manera, la complejidad global se vuelve max(O(n), O(m)) .

En LINQ, otra forma de hacerlo es realizar una unión interna entre las dos listas. Esto puede ser más legible, pero supongo que no es tan eficaz.

Déjame saber si algo no está claro.

Answer 2

Desde una perspectiva de estructuras de datos estrictas, lo mejor que se puede hacer es O (n * m) si su entrada no está clasificada . Vea las notas a continuación sobre por qué O (n + m) no es necesariamente correcto.

Psuedocode repugnante:

int FindCommonIntersects (ListA, ListB){
    int return_var = 0
    for each_a_entry in ListA: // Assumes that ListA is sorted
        if each_a_entry != each_a_entry->next.value() then:
            for each_b_entry in ListB:
                if each_a_entry == each_b_entry then return_var++
    return return_var;

Pasa por O (n) para la lista A y O (m) para la lista B si las listas no están ordenadas

Ergo la solución óptima se ejecuta en O (n * m) donde solo se recorre cada lista una vez. Tenga en cuenta que incluso si hay varios elementos en A que sean iguales, la línea each_a_entry != each_a_entry->next.value() significa que no hacemos una comparación con un elemento de B, lo que nos ahorra tiempo.

Estoy seguro de que puedes hacer esto más rápido con una estructura de hash asumiendo que puedes crear un mapa de tamaño n; sin embargo, asumo que no tenemos memoria infinita y, por lo tanto, no podemos crear un mapa de hash de tamaño extraordinario.

Answer 3

En primer lugar, es importante saber si sus listas pueden contener duplicados y cómo desea contarlos en caso de que existan.

Por ejemplo:

var listA = new List<int> { 1, 1, 1, 2, 3, 4, 4, 5 };
var listB = new List<int> { 1, 1, 2, 2, 3, 4, 5, 6 };
var result = listA.Intersect(listB).Count(); // 5

Si necesita obtener la cantidad de elementos que tienen un elemento igual a él en la otra lista, entonces debe escribir su propio método para hacerlo porque los métodos de biblioteca existentes usan colecciones que no permiten duplicados (como Set). Puedes intentar usar un HashSet para almacenar elementos de la segunda lista (esto aumentará tu velocidad de búsqueda)

public static int GetDuplicatesCount(List<int> listA, List<int> listB)
{
    var tempB = new HashSet<int>(listB);
    return listA.Count(tempB.Contains);
}

Devolverá 8 para las listas anteriores. También puedes intentar perfilar un poco más la versión detallada:

public static int GetDuplicatesCount(List<int> listA, List<int> listB)
{
    var tempB = new HashSet<int>(listB);
    var result = 0;
    foreach (var item in listA)
    {
        if (tempB.Contains(item))
        {
            result++;
        }
    }
    return result;
}

El cronómetro confirma que el bucle explícito funciona más rápido que LINQ. Para resumir: si necesita tener en cuenta los duplicados en su primera lista, entonces debe usar un método como el último que proporcioné. Si no, usa un método provisto por

Answer 4

Implementación estándar B.Intersect(A).Count() tiene una gran ventaja de ser breve y fácil de leer, a menos que tenga un problema de rendimiento medido que deba seguir.

Cuando el rendimiento es un problema, puede introducir HashSet<int> , es un buen compromiso en el uso de recursos y el tiempo de búsqueda. Sin embargo, debido a que te preocupa el rendimiento, deberíamos realizar algunas pruebas (estoy usando esta herramienta gratuita que escribí):

CPU: 1.8 GHz Pentium Core 2 Duo
Número de iteraciones: 100
Número de elementos en cada lista: 1000

A.Where(a => B.Contains(a)).Count() : 8338 ticks
A.Intersect(B).Count() : 288 ticks
B.Count - B.Except(A).Count() : 313 ticks

Ahora introduzcamos HashSet<int> en nuestra prueba (seleccione implementación de cualquier otra respuesta):

HashSet<int> : 163 ticks

Se realiza mucho mejor. ¿Podemos hacerlo mejor? Si el rango de entrada es conocido (y limitado), puede hacerlo mucho mejor que esto utilizando BitArray . En este ejemplo, asumo (por simplicidad) solo números positivos, pero es fácil de adaptar.

public static int UseBitArray(int range, List<int> listA, List<int> listB) {
    var BitArray array = new BitArray(range);
    for (int i = 0; i < listA.Count; ++i)
        array[listA[i]] = true;

    int count = 0;
    for (int i = 0; i < listB.Count; ++i) {
        if (array[listB[i]])
            ++count;
    }

    return count;
}

¿Cómo se realiza?

BitArray : 95 ticks

Solo requiere el 58% del segundo mejor método ( HashSet<int> ). Ni siquiera me comparo con los demás. Tenga en cuenta que usa mucha memoria y para un amplio rango (digamos Int32.MaxValue / 2 ) usa mucha memoria (además, su tamaño está limitado a Int32.MaxValue entonces no puede tener un rango entero de 32 bits con signo completo. Si Sus limitaciones no son un problema para ti, entonces deberías ir con ellas.

También tenga en cuenta que si puede hacer algunas suposiciones sobre sus entradas, puede optimizar aún más su función de búsqueda (por ejemplo, si puede suponer que los conjuntos están ordenados).

Cómo se escalan (la escala del eje Y es logarítmica):

Tenga en cuenta que Except desempeña mejor que Intersect cuando el número de elementos crece. También tenga en cuenta que para tal objeto trivial (un entero) no tendrá ninguna ganancia de rendimiento para hacerlo en paralelo (consulte también Cómo encontrar la diferencia entre dos listas de cadenas ): la comparación es tan trivial que la sobrecarga y la sincronización son mayores que los beneficios ( a menos que sea un algoritmo bien afinado en un número MUY elevado de elementos).

Si realmente está buscando lo último en ganancia de rendimiento, puede incluso implementar su propia clase de BitArray (sin cosas innecesarias y verificación de errores):

sealed class FastBitArray {
    public FastBitArray(int length) {
        m_array = new int[((length - 1) / 32) + 1];
    }

    public bool this[int index] {
        get {
            return (m_array[index / 32] & (1 << (index % 32))) != 0;
        }
        set {
            if (value)
                m_array[index / 32] |= (1 << (index % 32));
            else
                m_array[index / 32] &= ~(1 << (index % 32));
        }
    }

    private int[] m_array;
}

Tenga en cuenta que dentro del establecedor hay una rama, no tenemos que preocuparnos de optimizarla porque el patrón es fácil (siempre true ) para el predictor de rama. No hay ganancia de rendimiento para hacerlo más complicado que esto.

Últimas pruebas:

Número de iteraciones: 100
Número de elementos en cada lista: 1000000

HashSet<int> : 144748 ticks
BitArray : 37292 ticks
FastBitArray : 28966 ticks

Comparémoslos visualmente (la serie azul se prueba con 1,000 artículos, la serie naranja es 1,000,000; el eje Y es logarítmico para una comparación fácil con la serie 1k). Los métodos que sabemos que son lentos son simplemente omitidos:

Los mismos datos que muestran solo series 1M y con eje Y lineal:

Answer 5

Probablemente no sea el mejor rendimiento, pero es mejor que los OP y la solución de linq.

otro enfoque con Except()

int Result = B.Count - B.Except(A).Count();

Answer 6

Puedes obtener esto usando este

A.Count(match => B.Contains(match));

o

var count = A.Count(B.Contains);

Answer 7

Puedes usar Intersect y método de conteo.

List<int> A = new List<int>;
List<int> B = new List<int>;
// Some logic....item added in both lists. Then
A.Intersect(B).Count();

Answer 8

Realmente no podemos usar un HashSet para la primera lista ya que es completamente posible que la lista contenga entradas duplicadas ... Sin embargo, podemos crear un HashSet para la segunda lista (agrega complejidad de espacio + O (m) pero podríamos haber comenzado con un HashSet) ya que los duplicados no tienen sentido ... Entonces podemos iterar sobre la primera lista y verificar si el HashSet contiene el valor ... Esto será complejidad O (n) (para bucle) y O (1) para el cheque HashSet ...

LinqPad usado ....

  var lst = new List<int>{1,2,3,4,4,5,6,7};
  var lst2 = new List<int>{4,4,6};

  int count=0;
  var hs= new HashSet<int>(lst2);  //O(m) ... contains {4,6}
  foreach (var l in lst)  // O(n)
  {
    if (hs.Contains(l))  // O(1)
      count++;
  }
  count.Dump();  //returns 3

Answer 9

Si la información en sus dos listas se recopila a lo largo del tiempo, considere realizar un seguimiento de la superposición a medida que se insertan / eliminan elementos. De esa manera, el costo de determinar la respuesta se amortiza a lo largo de la vida útil de las listas y no se incurre en un evento único.

Answer 10

Si las listas son MUY grandes y desea ser eficiente, lo primero que tendrá que hacer es ordenarlas. Lo segundo que debe hacer es eliminar los duplicados en el destino (lista no contada). Pero, si el problema es lo suficientemente grande, no basta con las simples expresiones linq que se describen en las otras respuestas. Debe insertar los datos en un servidor SQL y ejecutar una consulta para obtener su respuesta. Entonces, la multihebra de un servidor SQL se encargará de la escala que necesitará si el problema es grande.

Answer 11

Tuve el mismo problema pero estaba buscando algo más eficiente.

// Testcase: 500 items exist in both lists
List<int> InputA = Enumerable.Range(0, 1000).ToList();
List<int> InputB = Enumerable.Range(500, 1000).ToList();

// Result
int Result1 = InputA.Where(a => InputB.Contains(a)).Count(); //13000 ticks
int Result2 = InputA.Intersect(InputB).Count(); //5700 ticks
int Result3 = B.Count - B.Except(A).Count(); //5800 ticks

int Result4 = InputA.CountIntersect(InputB); //2400 ticks

Mi solución es igual al método interno de Intersect , solo con contar y sin copiar los elementos. Es por eso que es más de 2 veces más rápido.

Código:

public static int CountIntersect<T>(this IEnumerable<T> collectionA, IEnumerable<T> collectionB)
{
    HashSet<T> tempA = new HashSet<T>(collectionA);
    int Result = 0;
    foreach (var itemB in collectionB)
    {
        if (tempA.Remove(itemB))
            Result++;
    }
    return Result;
}

Answer 12

A.Where(B.Distinct().ToDictionary(_ => _).ContainsKey).Count(); //This should work for other scenario with good performance

Answer 13

A.Where(a=>B.Contains(a)).Count ()

Answer 14

B.Intersect(A).Count(); //should do the job

Answer 15

HashSet<int> Btemp = new HashSet<int>(B);
var x = A.Count(p => B.Contains(p));

// or var x = A.Count(B.Contains); 
// but I have always found it to be a little unreadable to skip a lambda
// but this shorted form could be a little faster, because it skips a delegate

o

HashSet<int> Btemp = new HashSet<int>(B);
Btemp.IntersectWith(A); // note that this method is of the HashSet, it isn''t 
                        // a "generic" Intersect, so it''s optimized against 
                        // the HashSet internals
var y = Btemp.Count;

(teóricamente, tanto la adición como la verificación de la existencia en un HashSet son HashSet O(1) )

ambos son O(n) donde n = A.Count , en lugar de ser O(m * n) con m = B.Count , entonces O(x^2) .

(técnicamente son O(n) + O(m) porque la construcción del HashSet es O(m) , pero sigue siendo un O(x) ) ...

Al final, son lineales en el tiempo en lugar de cuadráticas ... Pero todo esto depende de la longitud de B ... Si B es de 1-3 elementos, es probable que sea más rápido usar el Contain directamente como lo hiciste.

En general, si sabe que A es mucho más grande que B, entonces debe poner A en el HashSet y dejar B en la List (debe hacer lo contrario si B es mucho más grande que A)