计算2个列表中存在的项目

Question

我有两个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所以我无法完全应用它们.

Answer 1

B.Intersect(A).Count(); //should do the job

Answer 2

标准实现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滴答

它只需要第二好的方法(HashSet<int>)的58%.我甚至不和别人比较.请注意,它大量使用内存并且范围很广(比方说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蜱

让我们直观地比较它们(蓝色系列测试1000项,橙色系列是1,000,000; Y轴是对数,以便与1k系列轻松比较).我们知道的方法很慢,只是省略了:

相同的数据仅显示1M系列和线性Y轴:

Answer 3

A.Where(a=>B.Contains(a)).Count ()