我有两个 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
}
}
我尝试使用 Intersect 和 Any，但它们返回的是 bool 类型，所以我无法完全应用它们。
B.Intersect(A).Count(); //should do the job
B包含{0, 1, 2}，而A包含{0, 0, 0, 0, 0, 4}，这将返回1，而不是5。 - Jon Hanna标准实现 B.Intersect(A).Count() 有很大的优势，因为它简洁易读，除非你有明显的性能问题，否则应该选择它。
当性能成为问题时，您可以引入 HashSet<int>，它在资源使用和搜索时间上是一个不错的折衷方案。但是，由于您担心性能问题，我们应该进行一些测试（我正在使用我编写的这个免费工具）：
CPU：1.8 GHz Pentium Core 2 Duo
每个列表中的项目数：1000
迭代次数：100
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个滴答声
它仅使用了第二佳方法（HashSet<int>）的58％。我甚至不与其他进行比较。请注意，它会严重占用内存，并且对于广泛范围（假设为Int32.MaxValue / 2），它会使用大量内存（此外，它的大小受限于Int32.MaxValue，因此您无法拥有完整的有符号32位整数范围）。如果它的限制对您没有问题，则应该选择它。
还要注意，如果您可以对输入做出一些假设，则可以进一步优化搜索函数（例如，如果您可以假设集合是有序的）。
它们如何扩展（Y轴刻度是对数）：
请注意，当项目数量增加时，Except的表现优于Intersect。还要注意，对于这种微不足道的对象（一个整数），并行执行没有任何性能收益（另请参见Finding the difference between two lists of strings）：比较是如此微不足道，以至于开销和同步比收益更高（除非它是针对非常多的项目进行了良好调整的算法）。
如果您真的想要最后一点性能提升，甚至可以实现自己的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;
}
请注意，在设置器内部有一个分支，我们不必担心优化它，因为模式很简单（始终是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;
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();
我曾经遇到过同样的问题，但我在寻找更高效的解决方案。
// 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;
}
你可以通过使用这个来获得这个
A.Count(match => B.Contains(match));
或者
var count = A.Count(B.Contains);
从理论上讲，由于必须完全检查两个列表中的一个，并针对该列表中的每个元素检查其是否包含在另一个列表中，因此您可以做的唯一一件事是改进搜索另一个列表中元素的方法，以渐近方式改进该方法。我看到的可能性如下（我假设我们正在查找列表A中的元素在元素B中）：
B进行排序（在LINQ中使用OrderBy轻松完成）-复杂度为O(m log m)-并使用二分搜索算法在其中搜索元素。总体复杂度为O(n log m)（将n视为A中的元素数量，将m视为B中的元素数量）。B转换为字典（使用ToDictionary方法）（复杂度为O(m)）。这样，总体复杂度变为max(O(n), O(m))。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
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提供的方法。
HashSet<T> 不提供重复项。 - fuboDictionary<T, int>来存储元素及其计数。代码会稍微长一些，但仍然足够高效。 - Serhiy Chupryk对于第一个列表，我们实际上不能使用 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(x => B.Contains(x)).Count()的意思是在集合A中筛选出所有存在于集合B中的元素，然后计算这些元素的数量。 - tafa