我有两个 int 类型，List比如List A和List B。List A我想检查中有多少项List B。我能够做到这一点，但什么是我试图避免的有效方法foreach，因为优化是我代码中的主要目标。
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
}
}
我尝试使用Intersectand Any，但它返回bool了，所以我无法完全应用它们。
B.Intersect(A).Count(); //should do the job
标准实现B.Intersect(A).Count()具有简短易读的巨大优势，除非您有衡量的性能问题，否则您应该使用它。
当性能是一个您可以引入的问题时HashSet<int>，它是资源使用和搜索时间的一个很好的折衷方案。但是，因为您担心性能，我们应该进行一些测试（我正在使用我编写的这个免费工具）：
CPU：1.8 GHz Pentium Core 2 Duo
迭代次数：100
每个列表中的项目数：1000
A.Where(a => B.Contains(a)).Count(): 8338 滴答
A.Intersect(B).Count(): 288 滴答
B.Count - B.Except(A).Count(): 313 滴答
现在让我们HashSet<int>在我们的测试中介绍（从任何其他答案中选择实现）：
HashSet<int>: 163 滴答声
它的表现要好得多。我们能做得更好吗？如果输入范围是已知的（并且是有限的），那么使用BitArray. 在这个例子中，我假设（为简单起见）只有正数，但很容易适应。
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;
}
它表现如何？
BitArray: 95 滴答
它只需要第二最佳方法的 58% ( HashSet<int>)。我什至不和别人比较。请注意，它大量使用内存并且在很宽的范围内（比方说Int32.MaxValue / 2）它使用大量内存（此外，它的大小仅限于Int32.MaxValue那么你不能拥有完整的有符号 32 位整数范围。如果它的限制不是问题那么你绝对应该接受它。
另请注意，如果您可以对输入进行一些假设，那么您可以进一步优化您的搜索功能（例如，如果您可以假设集合是有序的）。
它们如何按比例放大（Y 轴比例为对数）：
请注意，这比项目数量增加时Except表现更好。Intersect另请注意，对于这种微不足道的对象（整数），并行执行它不会有任何性能提升（另请参阅查找两个字符串列表之间的差异）：比较是如此微不足道，以至于开销和同步化高于收益（除非它是对大量项目进行良好调整的算法）。
如果您真的在寻找最后一点性能提升，您甚至可以实现自己的BitArray类（没有不需要的东西和错误检查）：
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;
}
请注意，在 setter 内部有一个分支，我们不必担心将其优化掉，因为true分支预测器的模式很容易（总是）。没有性能提升使它比这更复杂。
最新测试：
迭代次数：100
每个列表中的项目数：1000000
HashSet<int>: 144748 滴答
BitArray: 37292 滴答
FastBitArray: 28966 滴答
让我们从视觉上比较它们（蓝色系列是测试 1,000 个项目，橙色系列是 1,000,000 个；Y 轴是对数，以便与 1k 系列进行比较）。我们知道很慢的方法被简单地省略了：
相同的数据仅显示 1M 系列和线性 Y 轴：
A.Where(a=>B.Contains(a)).Count ()
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
或者
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;
HashSet（理论上，在操作中添加和检查是否存在O(1)）
他们俩都O(n)在哪里n = A.Count，而不是O(m * n)在一起m = B.Count，所以O(x^2)。
（从技术上讲，它们是O(n) + O(m)因为建造的HashSet是O(m)，但它仍然是O(x)）......
最后，它们在时间上是线性的，而不是二次的......但这一切都取决于 B 的长度......如果 B 是 1-3 个元素，那么Contain像你一样直接使用可能会更快。
一般来说，如果你知道 A 比 B 大得多，那么你应该把 A 放在里面HashSet，把 B 留在List里面（如果 B 比 A 大得多，你应该做相反的事情）
我有同样的问题，但我正在寻找更有效的东西。
// 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
我的解决方案等同于内部Intersect方法，只是计数而不复制元素。这就是为什么它快 2 倍以上的原因。
代码：
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;
}
您可以使用相交和计数方法
List<int> A = new List<int>;
List<int> B = new List<int>;
// Some logic....item added in both lists. Then
int count = A.Intersect(B).Count();
你可以用这个得到这个
A.Count(match => B.Contains(match));
或者
var count = A.Count(B.Contains);
好吧，从理论的角度来看，因为您必须完全检查两个列表中的一个，并且对于该列表的每个元素，检查它是否包含在另一个列表中，您唯一可以做的渐近改进方法就是改进搜索另一个列表中的元素。我看到的可能性如下（我想我们正在寻找元素列表A的元素B）：
OrderBy）列表中的项目B- 复杂性O(m log m)- 并使用二分搜索算法搜索其中的元素。总体复杂度是O(n log m)（取n中的元素数量A和m中的元素数量B）。ToDictionary方法） （复杂性）。这样，整体的复杂度就变成了。BO(m)max(O(n), O(m))在 LINQ 中，另一种方法是在两个列表之间执行内部连接。这可能更具可读性，但我的猜测是它的性能不高。
让我知道是否有任何不清楚的地方。
可能不是最好的性能，但比 OP 和 linq 解决方案更好。
另一种方法Except()
int Result = B.Count - B.Except(A).Count();
首先，重要的是要知道您的列表是否可以包含重复项以及如何计算它们以防万一。
例如：
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
如果您需要在另一个列表中获取任何元素与其相等的元素的数量，那么您需要编写自己的方法来做到这一点，因为现有的库方法使用不允许重复的集合（如 Set）。您可以尝试使用 HashSet 来存储第二个列表中的项目（这将提高您的查找速度）
public static int GetDuplicatesCount(List<int> listA, List<int> listB)
{
var tempB = new HashSet<int>(listB);
return listA.Count(tempB.Contains);
}
对于上面的列表，它将返回 8。您也可以尝试配置更详细的版本：
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;
}
秒表确认显式循环比 LINQ 运行得更快。所以总结一下：如果您需要考虑第一个列表中的重复项，那么您需要使用我提供的最后一个方法。如果没有 - 使用fubo提供的方法
如果列表非常大，并且您想提高效率，那么您需要做的第一件事就是对它们进行排序。第二件事是删除目标（非计数列表）中的重复项。但是，如果问题足够大，那么其他答案中描述的简单 linq 表达式是不够的。您应该将数据推送到 SQL 服务器并运行查询以获得答案。然后，如果问题很大，sqlserver 的多线程将负责您需要的扩展。
我们不能真正将 HashSet 用于第一个列表，因为该列表完全有可能包含重复的条目......但是我们可以为第二个列表创建一个 HashSet（增加空间复杂度 + O(m) 但我们可以开始使用 HashSet)，因为重复没有意义...然后我们可以遍历第一个列表并检查 HashSet 是否包含该值...这将是 O(n) 复杂度（for 循环）和 O(1) 复杂度HashSet 检查...
使用 LinqPad....
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
A.Where(B.Distinct().ToDictionary(_ => _).ContainsKey).Count(); //This should work for other scenario with good performance
从严格的数据结构的角度来看，如果您的输入是unsorted，则可以做到的最好的事情是 O(n*m) 。请参阅下面的注释，了解为什么 O(n+m) 不一定正确。
恶心的伪代码：
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;
如果列表未排序，则列表 A 遍历 O(n)，列表 B 遍历 O(m)
因此，最佳解决方案在 O(n*m) 处运行，您只需遍历每个列表一次。请注意，即使 A 中有多个相同的元素，该each_a_entry != each_a_entry->next.value()行表示我们不与 B 的元素进行比较，从而节省了一些时间。
我敢肯定，假设您可以创建大小为 n 的地图，您可以使用散列结构更快地做到这一点；但是，我假设我们没有无限的内存，因此无法创建超大的哈希图。
如果您的两个列表中的信息随着时间的推移而收集，则考虑在插入/删除项目时跟踪重叠。这样，确定答案的成本将在列表的生命周期内摊销，而不是一次性事件中发生。