Come posso sapere rapidamente se un elenco contiene solo duplicati?

Question

Ci sono più domande correlate, ma sto cercando una soluzione specifica per il mio caso. Esiste una matrice di (in genere) 14 numeri interi. Come posso dire rapidamente se ogni int appare esattamente due volte (cioè ci sono 7 coppie)? Il range di valori va da 1 a 35. L'aspetto principale qui è la performance.

Per riferimento, questa è la mia soluzione attuale. È stato scritto per assomigliare il più fedelmente le specifiche possibile e senza prestazioni in mente, quindi sono certo si può essere migliorata notevolmente:

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

utilizzando LINQ è opzionale. Non mi importa come, fintanto che è veloce :)

Edit: C'è il caso particolare che un int appare volte 2n con n> 1. In questo caso il controllo deve fallire, vale a dire che dovrebbe essere 7 coppie distinte.

Edit: Risultato ho provato soluzioni di Ani e Jon con piccoli cambiamenti e ha scoperto durante il punto di riferimento più eseguito in applicazione di destinazione che Ani offre circa il doppio il throughput di Jon sulla mia macchina (alcuni Core 2 Duo su Win7-64). Generare la gamma di intere dura già tanto quanto i rispettivi controlli, quindi sono soddisfatto del risultato. Ringrazia tutti!

Answer 1

Chiaramente, LINQ non fornirà la soluzione ottimale qui, anche se avrei migliorare la vostra soluzione LINQ corrente:

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

Per il caso specifico si parla (0 - 31), ecco una veloce , soluzione basata su array. Non scala molto bene quando la gamma di numeri possibili è ampia (utilizzare una soluzione di hashing in questo 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; 

MODIFICA: bug corretti come indicato da Jon Skeet. Vorrei anche sottolineare che il suo algo è più intelligente e probabilmente più veloce.

Answer 2

Bene, date le vostre esatte esigenze, possiamo essere un po 'più intelligenti. Qualcosa di simile a questo:

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

Fondamentalmente questo tiene traccia di quanti valori spaiato avete ancora, e ha un "fuori presto" se mai lo trova un tris.

(non so estemporaneo se questo sarà più veloce o più lento rispetto approccio di Ani di incremento e poi controllando per coppie abbinate in seguito.)

Answer 3

voglio creare una matrice di 32 elementi interi, inizializzato a zero. Chiamiamolo "billy".

Per ciascun elemento della matrice di ingresso, mi piacerebbe incrementare billy [elemento] 1.

Alla fine, controllare se Billy contiene solo 0 o 2.

Answer 4

Quasi certamente eccessivo quando si' ve ottenuto solo 14-ish coppie e solo il 32-ish valori possibili, ma nel caso generale si potrebbe fare qualcosa di simile:

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

Se la gamma di articoli è 0-31, è possibile memorizzare 32 one bit flag in un uint32.Suggerirei di prendere ogni elemento e calcolare la maschera = (1 elemento SHL), e vedere cosa succede se provi "o", "xo" o aggiungi i valori della maschera. Guarda i risultati per i casi validi e non validi. Per evitare un overflow, potresti voler usare un uint64 per l'addizione (dato che un uint32 potrebbe traboccare se ci sono due 31, o quattro 30 o otto 29).

Answer 6

Credo (mai misurato la velocità) questo codesnipet può dare un nuovo punto di 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; 
} 

Si possono avere i valori raddoppiati nella variabile "due volte"; Ovviamente funziona solo con valori inferiori a 32;