У меня есть список списков, для которых я хочу найти пересечение, например:
var list1 = new List<int>() { 1, 2, 3 };
var list2 = new List<int>() { 2, 3, 4 };
var list3 = new List<int>() { 3, 4, 5 };
var listOfLists = new List<List<int>>() { list1, list2, list3 };
// expected intersection is List<int>() { 3 };
Есть ли способ сделать это с помощью IEnumerable.Intersect ()?
РЕДАКТИРОВАТЬ: Я должен был быть более ясным по этому поводу: у меня действительно есть список списков, я не знаю, сколько их будет, три приведенных выше списка были просто примером, то, что у меня есть, на самом деле IEnumerable<IEnumerable<SomeClass>>
РЕШЕНИЕ
Спасибо за отличные ответы. Оказалось, что существует четыре варианта решения этой проблемы: List + aggregate (@Marcel Gosselin), List + foreach (@JaredPar, @Gabe Moothart), HashSet + aggregate (@jesperll) и HashSet + foreach (@Tony the Pony). Я провел несколько тестов производительности этих решений (различное количество списков , количество элементов в каждом списке и максимальный размер случайного числа .
Оказывается, в большинстве ситуаций HashSet работает лучше, чем List (за исключением больших списков и небольшого размера случайных чисел, я полагаю, из-за природы HashSet). Я не смог найти реальной разницы между методом foreach и агрегатом. метод (метод foreach работает немного лучше.)
Для меня метод агрегирования действительно привлекателен (и я буду использовать его как принятый ответ), но я бы не сказал, что это наиболее удобочитаемое решение. Еще раз всем спасибо!
Вы действительно можете использовать
Intersect
дважды. Однако я считаю, что это будет более эффективно:HashSet<int> hashSet = new HashSet<int>(list1); hashSet.IntersectWith(list2); hashSet.IntersectWith(list3); List<int> intersection = hashSet.ToList();
Конечно, это не проблема с маленькими наборами, но если у вас много больших наборов, это может быть значительным.
В основном
Enumerable.Intersect
необходимо создавать набор для каждого вызова - если вы знаете, что собираетесь выполнять больше операций с наборами, вы также можете оставить этот набор.Как всегда, внимательно следите за производительностью и удобочитаемостью - цепочка методов с двойным вызовом
Intersect
очень привлекательна.РЕДАКТИРОВАТЬ: Для обновленного вопроса:
public List<T> IntersectAll<T>(IEnumerable<IEnumerable<T>> lists) { HashSet<T> hashSet = null; foreach (var list in lists) { if (hashSet == null) { hashSet = new HashSet<T>(list); } else { hashSet.IntersectWith(list); } } return hashSet == null ? new List<T>() : hashSet.ToList(); }
Или, если вы знаете, что он не будет пустым и что Skip будет относительно дешевым:
public List<T> IntersectAll<T>(IEnumerable<IEnumerable<T>> lists) { HashSet<T> hashSet = new HashSet<T>(lists.First()); foreach (var list in lists.Skip(1)) { hashSet.IntersectWith(list); } return hashSet.ToList(); }
источник
IntersectAll()
метода (который немногочислен): есть ли простой способ добавить селектор в качестве параметра для сравнения значений (например:)Func<TResult, TKey> selector
и по-прежнему использоватьInsertectWith()
?List<T>
а не aList<TKey>
, верно? Лучшим подходом, вероятно, было бы создание файла,EqualityComparer<T>
который был реализован путем проектирования наTKey
.Попробуйте, это работает, но я бы очень хотел избавиться от .ToList () в совокупности.
var list1 = new List<int>() { 1, 2, 3 }; var list2 = new List<int>() { 2, 3, 4 }; var list3 = new List<int>() { 3, 4, 5 }; var listOfLists = new List<List<int>>() { list1, list2, list3 }; var intersection = listOfLists.Aggregate((previousList, nextList) => previousList.Intersect(nextList).ToList());
Обновить:
Следуя комментарию @pomber, можно избавиться от
ToList()
внутреннегоAggregate
вызова и переместить его наружу, чтобы выполнить его только один раз. Я не тестировал на производительность, будет ли предыдущий код быстрее нового. Необходимо указать параметр универсального типаAggregate
метода в последней строке, как показано ниже:var intersection = listOfLists.Aggregate<IEnumerable<int>>( (previousList, nextList) => previousList.Intersect(nextList) ).ToList();
источник
Вы могли бы сделать следующее
var result = list1.Intersect(list2).Intersect(list3).ToList();
источник
Это моя версия решения с методом расширения, который я назвал IntersectMany.
public static IEnumerable<TResult> IntersectMany<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector) { using (var enumerator = source.GetEnumerator()) { if(!enumerator.MoveNext()) return new TResult[0]; var ret = selector(enumerator.Current); while (enumerator.MoveNext()) { ret = ret.Intersect(selector(enumerator.Current)); } return ret; } }
Таким образом, использование будет примерно таким:
var intersection = (new[] { list1, list2, list3 }).IntersectMany(l => l).ToList();
источник
Это мое однострочное решение для списка списков (ListOfLists) без функции пересечения:
var intersect = ListOfLists.SelectMany(x=>x).Distinct().Where(w=> ListOfLists.TrueForAll(t=>t.Contains(w))).ToList()
Это должно работать для .net 4 (или новее)
источник
После поиска в сети и не придумав ничего, что мне понравилось (или что работало), я проспал это и придумал это. Мой использует class (
SearchResult
), в котором есть, и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(); }
Вот пример, использующий просто список целых чисел, а не класс (это была моя первоначальная реализация).
static List<int> FindCommon(List<List<int>> items) { Dictionary<int, int> oldList = new Dictionary<int, int>(); Dictionary<int, int> newList = new Dictionary<int, int>(); oldList = items[0].ToDictionary(x => x, x => x); foreach (List<int> list in items.Skip(1)) { foreach (int i in list) { if (oldList.Keys.Contains(i)) { newList.Add(i, i); } } oldList = new Dictionary<int, int>(newList); newList.Clear(); } return oldList.Values.ToList(); }
источник
Это простое решение, если все ваши списки маленькие. Если у вас большие списки, он не так эффективен, как хэш-набор:
public static IEnumerable<T> IntersectMany<T>(this IEnumerable<IEnumerable<T>> input) { if (!input.Any()) return new List<T>(); return input.Aggregate(Enumerable.Intersect); }
источник