如何快速判断列表是否仅包含重复项？

Question

有很多相关的问题,但我正在寻找一个特定于我的案例的解决方案.有一组(通常)14个整数.如何快速判断每个int是否恰好出现两次(即有7对)？值范围从1到35.这里的主要方面是性能.

作为参考,这是我目前的解决方案.编写的内容尽可能地与规范相似,没有考虑到性能,因此我确信可以大大改进:

var pairs = Array
    .GroupBy (x => x)
    .Where (x => x.Count () == 2)
    .Select (x => x.ToList ())
    .ToList ();
IsSevenPairs = pairs.Count == 7;

使用Linq是可选的.我不在乎如何,只要它快:)

编辑:有一个特殊情况,int出现2n次,n> 1.在这种情况下,检查应该失败,即应该有7个不同的对.

编辑:结果 我测试了Ani和Jon的解决方案,经过微小的修改,在目标应用程序的多个基准测试运行期间发现,Ani在我的机器上有大约两倍Jon的吞吐量(在Win7-64上有一些Core 2 Duo).生成整数数组已经需要大约相应的检查,所以我对结果感到满意.谢谢,全部!

Answer 1

那么,根据您的具体要求,我们可以更聪明一些.像这样的东西:

public bool CheckForPairs(int[] array)
{
    // Early out for odd arrays.
    // Using "& 1" is microscopically faster than "% 2" :)
    if ((array.Length & 1) == 1)
    {
        return false;
    }

    int[] counts = new int[32];
    int singleCounts = 0;
    foreach (int item in array)
    {
        int incrementedCount = ++counts[item];
        // TODO: Benchmark to see if a switch is actually the best approach here
        switch (incrementedCount)
        {
            case 1:
                singleCounts++;
                break;
            case 2:
                singleCounts--;
                break;
            case 3:
                return false;
            default:
                throw new InvalidOperationException("Shouldn't happen");
        }
    }
    return singleCounts == 0;
}

基本上,这会记录您仍然拥有多少未配对的值,并且如果它找到三种不同的值,则会"早出".

(我不知道这是否比Ani的增量方法更快或更慢,然后检查不匹配的对.)

Answer 2

很明显,LINQ不会在这里提供最佳解决方案,尽管我会将您当前的LINQ解决方案改进为:

// checks if sequence consists of items repeated exactly once
bool isSingleDupSeq = mySeq.GroupBy(num => num)
                           .All(group => group.Count() == 2);

// checks if every item comes with atleast 1 duplicate
bool isDupSeq = mySeq.GroupBy(num => num)
                     .All(group => group.Count() != 1);

对于您提到的特定情况(0 - 31),这是一个更快的,基于阵列的解决方案.当可能的数字范围很大时,它不能很好地扩展(在这种情况下使用散列解决方案).

// elements inited to zero because default(int) == 0
var timesSeenByNum = new int[32];

foreach (int num in myArray)
{
    if (++timesSeenByNum[num] == 3)
    {
        //quick-reject: number is seen thrice
        return false;
    }
}

foreach (int timesSeen in timesSeenByNum)
{
    if (timesSeen == 1)
    {
        // only rejection case not caught so far is
        // if a number is seen exactly once
        return false;
    }
}

// all good, a number is seen exactly twice or never
return true;   

编辑:修正了Jon Skeet指出的错误.我还应该指出,他的算法更聪明,可能更快.