¿Cómo puedo saber rápidamente si una lista contiene solo duplicados?

Question

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

Como referencia, esta 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 de que se puede mejorar enormemente:

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

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

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

Editar: Resultado He probado soluciones Jon de Ani y de con pequeñas modificaciones y se encontró durante la referencia múltiple se ejecuta en la aplicación de destino que Ani s tiene aproximadamente el doble de rendimiento de Jon en mi máquina (algunos Core 2 Duo en Win7-64). Generar la matriz de entradas ya lleva tanto tiempo como las comprobaciones respectivas, por lo que estoy satisfecho con el resultado. ¡Gracias a todos!

Answer 1

Claramente, LINQ no proporcionará la solución óptima aquí, 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); 

Para el caso concreto que mencionas (0 - 31), aquí hay un rápido , solución basada en arreglos. No escala muy bien cuando el rango de números posibles es grande (use una solución de hash 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: corrigió los errores según lo señalado por Jon Skeet. También debo señalar que su algo es más inteligente y probablemente más rápido.

Answer 2

Bueno, dados sus requisitos exactos, podemos ser un poco más inteligentes. 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 una "salida temprana" si alguna vez se encuentra un trío.

(no sé improvisada si esto va a ser más rápido o más lento que el enfoque de incrementar y luego la comprobación de pares no coincidentes después de Ani.)

Answer 3

me gustaría crear una matriz de 32 elementos enteros, inicializado a cero. Vamos a llamarlo "billy".

Para cada elemento de la matriz de entrada, me Valor mínimo de Billy [elemento] de 1.

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

Answer 4

Es casi seguro que una exageración cuando se' sólo he conseguido pares 14-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 de uno banderas de bits en uint32.Sugiero tomar cada elemento y calcular máscara = (1 elemento SHL) y ver qué sucede si intentas 'or', 'xor' o agregar los valores de la máscara. Mire los resultados para casos válidos y no válidos. Para evitar el desbordamiento, es posible que desee utilizar uint64 para la adición (ya que un uint32 podría desbordarse si hay dos de 31, cuatro de cuatro u ocho de 29).

Answer 6

supongo (nunca midió 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; 
} 

Usted puede tener los valores dobles en la variable "dos veces"; Por supuesto, solo funciona con valores inferiores a 32;