¿Cómo puedo saber rápidamente si una lista contiene sólo los duplicados?

Question

Hay varias preguntas relacionadas, pero yo estoy buscando una solución específica a mi caso. Hay una serie de (por lo general) 14 números enteros. ¿Cómo puedo decirle rápidamente si cada int aparece exactamente dos veces (es decir, hay 7 pares)? El rango de valores es de 1 a 35. El aspecto principal aquí es el rendimiento.

A modo de referencia, esto es mi solución actual. Fue escrito para parecerse a la espec lo más cerca posible y sin que el rendimiento en mente, así que estoy seguro es se pueden mejorar enormemente:

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

Uso Linq es opcional. No me importa cómo, siempre que es rápido:)

Editar: No es el caso especial de que una int aparece 2n veces con n> 1. En este caso el cheque debe fallar , es decir, no debe ser de 7 pares distintos .

Editar: Resultado Probé soluciones de Ani y Jon de con pequeñas modificaciones y encontrados durante varias ejecuciones de referencia en la aplicación de destino que Ani s tiene sobre el rendimiento dos veces de Jon en mi máquina (algunos Core 2 Duo en Win7-64). La generación de la matriz de enteros que ya lleva casi tan largo como los respectivos controles, así que estoy feliz con el resultado. Gracias a todos!

Answer 1

Es evidente que LINQ no facilita la óptima solución a este problema, a pesar de que podrían mejorar su solución LINQ actual a:

// 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);

En el caso específico que mencionas (0 - 31), he aquí una solución más rápida y basada en matrices. Es no escala muy bien cuando el intervalo de números posibles es grande (utilizar una solución de hashing en este caso).

// 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;   

EDIT: Se ha corregido errores como fuera puntiaguda por Jon Skeet. También debo señalar que su algo es más inteligente y probablemente más rápido.

Answer 2

Bueno, teniendo en cuenta sus necesidades exactas, que puede ser un poco más inteligente. Algo como esto:

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;
}

Básicamente, este realiza un seguimiento de cuántos valores no apareado todavía tiene, y tiene un "antes de tiempo" si alguna vez se encuentra un trío.

(No sé si esta improvisada será más rápido o más lento que el enfoque de incrementar y luego la comprobación de pares incomparables Después de Ani.)

Answer 3

I crearía una serie de 32 elementos enteros, inicializado a cero. Digamos que es "Billy".

Para cada elemento de la matriz de entrada, me Incremento billy [elemento] de 1.

Al final, compruebe si Billy contiene sólo 0 o 2.

Answer 4

Es casi seguro que una exageración cuando sólo tiene 14 pares-ish y valores sólo el 32-ish posibles, pero en el caso general se podría hacer algo como esto:

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);
    }
}

Answer 5

Si la gama de artículos es 0-31, puede almacenar 32 banderas de un bit en un uint32. Yo sugeriría tomar cada elemento y la máscara de computación = (1 artículo SHL), y ver lo que ocurre si se intenta 'OR'ing,' xor'ing, o la adición de los valores de máscara. Mira los resultados de casos válidos y no válidos. Para evitar el desbordamiento, es posible que desee utilizar un uint64 para la adición (ya que una uint32 podría desbordarse si hay dos de 31, o cuatro, o 30 de ocho de 29).

Answer 6

supongo (no se mide la velocidad) esta codesnipet le puede dar un nuevo punto de vista:

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;
}

Puede tener los valores dobles en la variable "dos veces"; Por supuesto que sólo funciona para valores inferiores a 32;