代码之家 › 专栏 › 技术社区 › mafu

如何快速判断列表是否只包含重复项?

mahjong duplicates list .net c#

mafu · 技术社区 · 15 年前

有多个相关问题,但我正在寻找一个特定于我的案例的解决方案。有一个(通常)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上的一些Core2 Duo)。生成ints数组已经花费了相应检查的时间,所以我对结果很满意。谢谢大家!

6 回复 | 直到 15 年前

Ani 15 年前

显然,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 15 年前

好吧,考虑到你的具体要求,我们可以更聪明一点。像这样:

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的递增方法快或慢,然后检查不匹配的对。)

Simone 15 年前

我将创建一个32个整数元素的数组,初始化为零。我们叫它“比利”。

对于输入数组的每个元素,我将billy[element]增加1。

最后,检查billy是否只包含0或2。

LukeH 15 年前

几乎可以肯定,当您只有14个ish对和32个ish可能的值时,会造成过度杀戮,但在一般情况下,您可以这样做:

bool onlyPairs = yourArray.ContainsOnlyPairs();

// ...

public static class EnumerableExtensions
{
    public static bool ContainsOnlyPairs<T>(this IEnumerable<T> source)
    {
        var dict = new Dictionary<T, int>();

        foreach (T item in source)
        {
            int count;
            dict.TryGetValue(item, out count);

            if (count > 1)
                return false;

            dict[item] = count + 1;
        }

        return dict.All(kvp => kvp.Value == 2);
    }
}

supercat 15 年前

如果项的范围是0-31,则可以在uint32中存储32个一位标志。我建议取每个项目并计算mask=(1 shl item),然后看看如果尝试“或”ing、“xor”ing或添加mask值会发生什么。查看有效和无效案例的结果。为了避免溢出,您可能需要使用uint64进行添加(因为如果存在两个31秒、四个30秒或八个29秒,uint32可能溢出)。

mafu 15 年前

我想(从未测量过速度)这个代码截图可以给你一个新的观点:

int[] array = { 0, 1, 2, 3, 1, 1, 3, 5, 1, 2, 7, 31 }; // this is your sample array

uint[] powOf2 = {
    1, 2, 4, 8,
    16, 32, 64, 128,
    256, 512, 1024, 2048,
    4096, 8192, 16384, 32768,
    65536, 131072, 262144, 524288,
    1048576, 2097152, 4194304, 8388608,
    16777216, 33554432, 67108864, 134217728,
    268435456, 536870912, 1073741824, 2147483648
               };

uint now;
uint once = 0;
uint twice = 0;
uint more = 0;

for (int i = 0; i < array.Length; i++)
{
    now = powOf2[array[i]];

    more |= twice & now;
    twice ^= (once & now) & ~more;
    twice ^= more;
    once |= now;
}

您可以在变量“两次”中得到双倍的值; 当然,它只适用于小于32的值;