Самый быстрый способ найти общие элементы в нескольких списках в C #

Question

Учитывая следующее:

List<List<Option>> optionLists;

Какой быстрый способ определить подмножество объектов Option, которые появляются во всех N списках? Равенство определяется через некоторое строковое свойство, такое как option1.Value == option2.Value.

Таким образом, мы должны получить List<Option>, где каждый элемент появляется только один раз.

Answer 1

Хорошо, здесь будет найден список объектов Option, значения которых появляются в каждом списке.

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;

Он не делает "отдельный" выбор, поэтому он возвращает несколько объектов Option, некоторые из которых имеют одинаковое значение.

Answer 2

Опираясь на Ответ Мэтта , так как нас интересуют только те опции, которые есть во всех списках, мы можем просто проверить любые опции в первом списке, которые другие разделяют:

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

Если список опций не может содержать дубликаты, вызов Distinct не требуется. Если списки сильно различаются по размеру, было бы лучше перебрать опции в кратчайшем списке, а не в любом списке, который будет First. Сортированные или хешированные коллекции можно использовать для улучшения времени поиска при вызове Contains, хотя это не должно иметь большого значения для умеренного числа элементов.

Answer 3

Вот гораздо более эффективная реализация:

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

Он работает, создавая набор всех элементов, общих для всех списков, обработанных до сих пор, и сравнивая каждый список с этим набором, создавая временный набор элементов, общих для текущего списка и списка общих элементов на данный момент. Фактически O (n.m), где n - количество списков, а m - количество элементов в списках.

Пример использования:

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 4

как насчет использования hashSet ? таким образом вы можете делать то, что вы хотите, в O (n), где n - это количество элементов во всех списках, вместе взятых, и я думаю, что это самый быстрый способ сделать это.

вам просто нужно перебрать каждый список и вставить найденные значения в хэш-набор Когда вы вставляете ключ, который уже существует, вы получите false в качестве возвращаемого значения метода .add, в противном случае true возвращается

Answer 5

После поиска в сети и не придумав что-то, что мне понравилось (или это сработало), я спал на нем и придумал это. Мой SearchResult похож на ваш Option. Он содержит EmployeeId, и это то, что мне нужно, чтобы оно было общим для всех списков. Я возвращаю все записи, которые имеют EmployeeId в каждом списке. Это не модно, но просто и понятно, как мне нравится. Для небольших списков (в моем случае) это должно работать очень хорошо - и каждый может это понять!

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

Answer 6

@ Skizz Метод не верный. Он также возвращает элементы, которые не являются общими для всех списков элементов. Вот исправленный метод:

/// <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 7

/// <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 8

Вы можете сделать это, посчитав вхождения всех элементов во всех списках - те элементы, количество вхождений которых равно числу списков, являются общими для всех списков:

    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 9

У меня нет статистики производительности, но если вы не хотите использовать свой собственный метод, в разных библиотеках коллекций есть объект 'Set' или 'Set (T)', который предлагает обычные процедуры установки. (перечислены в порядке, я бы их использовал).

1. Коллекции IESI (буквально просто набор классов)
2. PowerCollections (не обновляется в течение некоторого времени)
3. C5 (никогда не использовался лично)

Answer 10

Сортируйте, затем сделайте что-то похожее на сортировку слиянием.

В основном вы бы сделали это:

1. Получить первый элемент из каждого списка
2. Сравнить элементы, если они равны, вывести
3. Если какой-либо из элементов находится перед другими, в порядке сортировки извлеките новый элемент из соответствующего списка, чтобы заменить его, в противном случае извлеките новые элементы, чтобы заменить их все из всего списка
4. Пока у вас есть предметы, вернитесь к 2.