ultimo - La forma más rápida de encontrar elementos comunes en múltiples listas en C#

obtener el ultimo elemento de una lista c#

Question

Dado lo siguiente:

List<List<Option>> optionLists;

¿Cuál sería una forma rápida de determinar el subconjunto de objetos Opción que aparecen en todas las N listas? La igualdad se determina a través de una propiedad de cadena como option1.Value == option2.Value.

Entonces deberíamos terminar con List<Option> donde cada elemento aparece solo una vez.

Answer 1

¿qué hay de usar un hashSet ? de esa manera puedes hacer lo que quieras en O (n) donde n es el número de elementos en todas las listas combinadas, y creo que esa es la forma más rápida de hacerlo.

solo tiene que iterar sobre cada lista e insertar los valores que encuentre en el hashset. Cuando inserte una clave que ya existe recibirá el valor falso como el valor devuelto del método .add; de lo contrario , devuelve true

Answer 2

Bien, esto encontrará la lista de objetos Option que tienen un valor que aparece en cada lista.

var x = from list in optionLists
        from option in list
        where optionLists.All(l => l.Any(o => o.Value == option.Value))
        orderby option.Value
        select option;

No realiza una selección "distinta", por lo que devolverá múltiples objetos Opción, algunos de ellos con el mismo Valor.

Answer 3

Ordenar, luego hacer algo similar a un tipo de combinación.

Básicamente, harías esto:

1. Recuperar el primer elemento de cada lista
2. Compare los artículos, si es igual, salida
3. Si alguno de los elementos está antes que los otros, ordenadamente, recupere un nuevo elemento de la lista correspondiente para reemplazarlo, de lo contrario, recupere los nuevos elementos para reemplazarlos a todos, de toda la lista
4. Mientras que todavía tenga artículos, regrese a 2.

Answer 4

No tengo las estadísticas de rendimiento, pero si no desea desplegar su propio método, varias bibliotecas de colecciones tienen un objeto ''Establecer'' o ''Establecer (T)'' que ofrecen los procedimientos establecidos habituales. (enumerados en el orden en que los usaría).

1. Colecciones de IESI (literalmente solo Set classes)
2. PowerCollections (no se actualiza en un momento)
3. C5 (nunca utilizado personalmente)

Answer 5

Puede hacer esto contando las ocurrencias de todos los elementos en todas las listas; aquellos elementos cuya cantidad de ocurrencias es igual al número de listas, son comunes a todas las listas:

    static List<T> FindCommon<T>(IEnumerable<List<T>> lists)
    {
        Dictionary<T, int> map = new Dictionary<T, int>();
        int listCount = 0; // number of lists

        foreach (IEnumerable<T> list in lists)
        {
            listCount++;
            foreach (T item in list)
            {
                // Item encountered, increment count
                int currCount;
                if (!map.TryGetValue(item, out currCount))
                    currCount = 0;

                currCount++;
                map[item] = currCount;
            }
        }

        List<T> result= new List<T>();
        foreach (KeyValuePair<T,int> kvp in map)
        {
            // Items whose occurrence count is equal to the number of lists are common to all the lists
            if (kvp.Value == listCount)
                result.Add(kvp.Key);
        }

        return result;
    }

Answer 6

Aquí hay una implementación mucho más eficiente:

static SortedDictionary<T,bool>.KeyCollection FindCommon<T> (List<List<T>> items)
{
  SortedDictionary<T, bool>
    current_common = new SortedDictionary<T, bool> (),
    common = new SortedDictionary<T, bool> ();

  foreach (List<T> list in items)
  {
    if (current_common.Count == 0)
    {
      foreach (T item in list)
      {
        common [item] = true;
      }
    }
    else
    {
      foreach (T item in list)
      {
        if (current_common.ContainsKey(item))
          common[item] = true;
        else
          common[item] = false;
      }
    }

    if (common.Count == 0)
    {
      current_common.Clear ();
      break;
    }

    SortedDictionary<T, bool>
      swap = current_common;

    current_common = common;
    common = swap;
    common.Clear ();
  }

  return current_common.Keys;
}    

Funciona creando un conjunto de todos los elementos comunes a todas las listas procesadas hasta el momento y comparando cada lista con este conjunto, creando un conjunto temporal de los elementos comunes a la lista actual y la lista de elementos comunes hasta el momento. Efectivamente, un O (nm) donde n es el número de listas ym el número de elementos en las listas.

Un ejemplo de usarlo:

static void Main (string [] args)
{
  Random
    random = new Random();

  List<List<int>>
    items = new List<List<int>>();

  for (int i = 0 ; i < 10 ; ++i)
  {
    List<int>
      list = new List<int> ();

    items.Add (list);

    for (int j = 0 ; j < 100 ; ++j)
    {
      list.Add (random.Next (70));
    }
  }

  SortedDictionary<int, bool>.KeyCollection
    common = FindCommon (items);

  foreach (List<int> list in items)
  {
    list.Sort ();
  }

  for (int i = 0 ; i < 100 ; ++i)
  {
    for (int j = 0 ; j < 10 ; ++j)
    {
      System.Diagnostics.Trace.Write (String.Format ("{0,-4:D} ", items [j] [i]));
    }

    System.Diagnostics.Trace.WriteLine ("");
  }

  foreach (int item in common)
  {
    System.Diagnostics.Trace.WriteLine (String.Format ("{0,-4:D} ", item));
  }
}

Answer 7

Sobre la base de la respuesta de Matt , dado que solo estamos interesados ​​en las opciones que todas las listas tienen en común, simplemente podemos verificar las opciones en la primera lista que los demás comparten:

var sharedOptions =
    from option in optionLists.First( ).Distinct( )
    where optionLists.Skip( 1 ).All( l => l.Contains( option ) )
    select option;

Si una lista de opciones no puede contener entradas duplicadas, la llamada Distinct es innecesaria. Si las listas varían mucho en tamaño, sería mejor repetir las opciones en la lista más corta, en lugar de la lista que sea First . Las colecciones ordenadas o hash se pueden usar para mejorar el tiempo de búsqueda de la llamada de Contains , aunque no debería hacer mucha diferencia para un número moderado de elementos.

Answer 8

/// <summary>
    /// The method FindCommonItems, returns a list of all the COMMON ITEMS in the lists contained in the listOfLists.
    /// The method expects lists containing NO DUPLICATE ITEMS.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="allSets"></param>
    /// <returns></returns>
    public static List<T> FindCommonItems<T>(IEnumerable<List<T>> allSets)
    {
        Dictionary<T, int> map = new Dictionary<T, int>();
        int listCount = 0; // Number of lists.
        foreach (IEnumerable<T> currentSet in allSets)
        {
            int itemsCount = currentSet.ToList().Count;
            HashSet<T> uniqueItems = new HashSet<T>();
            bool duplicateItemEncountered = false;
            listCount++;
            foreach (T item in currentSet)
            {
                if (!uniqueItems.Add(item))
                {
                    duplicateItemEncountered = true;
                }                        
                if (map.ContainsKey(item))
                {
                    map[item]++;
                } 
                else
                {
                    map.Add(item, 1);
                }
            }
            if (duplicateItemEncountered)
            {
                uniqueItems.Clear();
                List<T> duplicateItems = new List<T>();
                StringBuilder currentSetItems = new StringBuilder();
                List<T> currentSetAsList = new List<T>(currentSet);
                for (int i = 0; i < itemsCount; i++)
                {
                    T currentItem = currentSetAsList[i];
                    if (!uniqueItems.Add(currentItem))
                    {
                        duplicateItems.Add(currentItem);
                    }
                    currentSetItems.Append(currentItem);
                    if (i < itemsCount - 1)
                    {
                        currentSetItems.Append(", ");
                    }
                }
                StringBuilder duplicateItemsNamesEnumeration = new StringBuilder();
                int j = 0;
                foreach (T item in duplicateItems)
                {
                    duplicateItemsNamesEnumeration.Append(item.ToString());
                    if (j < uniqueItems.Count - 1)
                    {
                        duplicateItemsNamesEnumeration.Append(", ");
                    }
                }
                throw new Exception("The list " + currentSetItems.ToString() + " contains the following duplicate items: " + duplicateItemsNamesEnumeration.ToString());
            }
        }
        List<T> result= new List<T>();
        foreach (KeyValuePair<T, int> itemAndItsCount in map)
        {
            if (itemAndItsCount.Value == listCount) // Items whose occurrence count is equal to the number of lists are common to all the lists.
            {
                result.Add(itemAndItsCount.Key);
            }
        }

        return result;
    }

Answer 9

@Skizz El método no es correcto. Devuelve también elementos que no son comunes a todas las listas en los artículos. Aquí está el método corregido:

/// <summary>.
    /// The method FindAllCommonItemsInAllTheLists, returns a HashSet that contains all the common items in the lists contained in the listOfLists,
    /// regardless of the order of the items in the various lists.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="listOfLists"></param>
    /// <returns></returns>
    public static HashSet<T> FindAllCommonItemsInAllTheLists<T>(List<List<T>> listOfLists)
    {
        if (listOfLists == null || listOfLists.Count == 0)
        {
            return null;
        }
        HashSet<T> currentCommon = new HashSet<T>();
        HashSet<T> common = new HashSet<T>();

        foreach (List<T> currentList in listOfLists)
        {
            if (currentCommon.Count == 0)
            {
                foreach (T item in currentList)
                {
                    common.Add(item);
                }
            }
            else
            {
                foreach (T item in currentList)
                {
                    if (currentCommon.Contains(item))
                    {
                        common.Add(item);
                    }
                }
            }
            if (common.Count == 0)
            {
                currentCommon.Clear();
                break;
            }
            currentCommon.Clear(); // Empty currentCommon for a new iteration.
            foreach (T item in common) /* Copy all the items contained in common to currentCommon. 
                                        *            currentCommon = common; 
                                        * does not work because thus currentCommon and common would point at the same object and 
                                        * the next statement: 
                                        *            common.Clear();
                                        * will also clear currentCommon.
                                        */
            {
                if (!currentCommon.Contains(item))
                {
                    currentCommon.Add(item);
                }
            }
            common.Clear();
        }

        return currentCommon;
    }

Answer 10

Después de buscar en la red y no encontrar realmente algo que me gustara (o que funcionara), dormí y pensé en esto. My SearchResult es similar a tu Option . Tiene un EmployeeId y eso es lo que necesito que sea común en todas las listas. Devuelvo todos los registros que tienen un EmployeeId . De EmployeeId en cada lista. No es lujoso, pero es simple y fácil de entender, justo lo que me gusta. Para listas pequeñas (mi caso) debería funcionar bien, ¡y cualquiera puede entenderlo!

private List<SearchResult> GetFinalSearchResults(IEnumerable<IEnumerable<SearchResult>> lists)
{
    Dictionary<int, SearchResult> oldList = new Dictionary<int, SearchResult>();
    Dictionary<int, SearchResult> newList = new Dictionary<int, SearchResult>();

    oldList = lists.First().ToDictionary(x => x.EmployeeId, x => x);

    foreach (List<SearchResult> list in lists.Skip(1))
    {
        foreach (SearchResult emp in list)
        {
            if (oldList.Keys.Contains(emp.EmployeeId))
            {
                newList.Add(emp.EmployeeId, emp);
            }
        }

        oldList = new Dictionary<int, SearchResult>(newList);
        newList.Clear();
    }

    return oldList.Values.ToList();
}