Как найти элемент списка в другом списке?

Я хочу знать, можно ли найти хотя бы один элемент в первом списке во втором списке.Как найти элемент списка в другом списке?

Я вижу два способа сделать это. Скажем, наши списки:

List<string> list1 = new[] { "A", "C", "F", "H", "I" }; 
List<string> list2 = new[] { "B", "D", "F", "G", "I" };

Первый подход использует цикл:

bool isFound = false; 
foreach (item1 in list1) 
{ 
    if (list2.Contains(item1)) 
    { 
     isFound = true; 
     break; 
    } 
}

Второй использует Linq непосредственно:

bool isFound = list1.Intersect(list2).Any();

Первый долго писать и не очень просто/легко читается. Второй - короткий и понятный, но выступления будут низкими, особенно в больших списках.

Что может быть изящным способом сделать это?

источник

2011-02-20 Arseni Mourzenko

Я думаю, что второй один будет быстрее для больших списков. Поскольку первый - это «O (list1.Count * list2.Count)», а второй - «O (list1.Count + list2.Count)». Второе занимает больше памяти. – CodesInChaos

Если вы действительно хотите использовать LINQ для поиска * точно *, как ваш первый образец, используйте 'bool isFound = list1.Any (list2.Contains);' – Ani

Но, конечно, этот вариант, так же как и исходный код, имеет квадратичную производительность. – CodesInChaos

Вторая имеет лучшую производительность в больших списках, чем первая. Intersect помещает элементы одного списка в хэш-таблицу перед проверкой элементов другого списка для членства.

источник

2011-02-20 22:56:22 mquander

Я подумал, что во втором случае будет вычисляться пересечение двух списков, и только тогда будет выполняться 'Any'. Я ошибаюсь? –

Пересечение рассчитывается лениво.Я думаю, что он сначала создает хешсет из списка2, а затем перебирает list1 и добавляет к хешсету по мере его продвижения. – CodesInChaos

@MainMa - да, вы ошибаетесь. Он будет хэшировать * первым *, а затем использовать блок итератора для катушки над вторым. В каждой точке вы возвращаете только одно совпадение. Блоки Iterator не запускаются до завершения, прежде чем возвращать содержимое. Нет необходимости вычислять полный набор совпадений в коллекции. Единственный раз, когда 'Any()' будет выполняться до завершения, будет, если он вернет 'false', иначе он будет замыкать последовательность в первом совпадении. –

Кажется странным критиковать работу LINQ, когда оригинал явно (наихудший случай) O (n * m); подходом LINQ будет Я ожидаю, что использует список HashSet<T>, а затем использовать блок потокового итератора - поэтому производительность должна быть O (n + m) - то есть лучше.

источник

2011-02-20 22:57:38

Я думаю, что второй будет быстрее для больших списков. Поскольку первый из них - O (list1.Count * list2.Count), а второй - O (list1.Count + list2.Count). Второе занимает больше памяти.

И накладные расходы на linq обычно являются постоянным коэффициентом умножения по сравнению с кодом ручной работы. Я предполагаю, что второй медленнее, чем императивный код, по крайней мере, в два раза, возможно, даже не это. Он использует память O(list1.Count+list2.Count), которую можно сократить до O(Min(list1,list2)), если вы тщательно напишите свой код для использования с низкой памятью, сохраняя линейную производительность.

Этот код должен быть относительно быстро на больших списках:

bool isFound = false; 
HashSet<string> set2=new HashSet<string>(list2); 
foreach (item1 in list1) 
{ 
    if (set2.Contains(item1)) 
    { 
     isFound = true; 
     break; 
    } 
}

Вы можете оптимизировать этот код дальше, делая меньший список в HashSet вместо всегда использовать List2.

источник

2011-02-20 22:58:52 CodesInChaos

Принятый ответ замечательный, однако он не работает с Linq-to-sql, так как нет отображения для Intersect. В этом случае вы должны использовать:

bool isFound = table.Any(row => list2.Contains(row.FieldWithValue));

Это компилируется в WHERE EXSITS

источник

2013-08-29 10:06:07

Как найти элемент списка в другом списке?

ответ

Смежные вопросы