Come faccio a sapere rapidamente se un elenco contiene solo i duplicati?

Question

Ci sono diverse questioni connesse, ma sto cercando una soluzione specifica per il mio caso. C'è una serie di (di solito) 14 numeri interi. Come faccio a sapere rapidamente se ogni int appare esattamente il doppio (vale a dire ci sono 7 coppie)? L'intervallo di valori è da 1 a 35. L'aspetto principale è prestazioni.

Per riferimento, questo è il mio attuale soluzione. È stato scritto per assomigliare le specifiche il più possibile e senza prestazioni in mente, quindi sono certo è possibile migliorare 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:)

Modifica V'è il caso particolare che un int compare volte 2n con n> 1. In questo caso il controllo deve sicuro , cioè non dovrebbe essere 7 coppie distinte .

Modifica: Risultato Ho provato le soluzioni di Ani e Jon con piccoli cambiamenti e l'ho trovato nel corso di più corse di riferimento nella applicazione di destinazione che Ani offre circa il throughput doppio di Jon sulla mia macchina (alcuni Core 2 Duo su Win7-64). Generare la matrice di int prende già circa fino a quando i rispettivi controlli, quindi sono contento del risultato. Grazie, tutti!

Answer 1

Chiaramente, LINQ non fornirà il ottimale soluzione 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 soluzione più veloce basata su array. Non scala molto bene quando la gamma di possibili numeri è grande (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;   

EDIT: Risolto bug come le punte da Jon Skeet. Vorrei anche sottolineare che la sua algo è più intelligente e probabilmente più veloce.

Answer 2

Bene, dato le vostre esigenze, possiamo essere un po 'più intelligente. 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;
}

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

(non so due piedi se questo sarà più veloce o più lento rispetto l'approccio di Ani di incrementare e poi controllando per le coppie senza eguali in seguito.)

Answer 3

I creerebbe un array di 32 elementi interi, inizializzato a zero. Chiamiamolo "Billy".

Per ogni elemento dell'array input, avrei incremento billy [elemento] 1.

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

Answer 4

Quasi certamente eccessivo quando hai 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 bandiere a un bit in un uint32. Vorrei suggerire di prendere ogni elemento e la maschera di calcolo = (1 articolo SHL), e vedere cosa succede se si cerca 'or'ing,' xor'ing, o aggiungendo i valori della maschera. Guardate i risultati per i casi validi e non validi. Per evitare di troppo pieno, si consiglia di utilizzare un uint64 per l'aggiunta (dal momento che un Uint32 potrebbe traboccare se ci sono due 31 di, o quattro anni '30, o otto 29 del).

Answer 6

Credo che (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;
}

È possibile avere i valori raddoppiati nella variabile "due volte"; Naturalmente funziona solo per valori inferiori a 32;