Comment savoir rapidement si une liste contient uniquement des doublons?

Question

Il y a plusieurs questions connexes, mais je cherche une solution spécifique à mon cas. Il y a un tableau de (généralement) 14 entiers. Comment puis-je savoir rapidement si chaque int apparaît exactement deux fois (c'est-à-dire qu'il y a 7 paires)? La plage de valeurs va de 1 à 35. L'aspect principal ici est la performance.

Pour référence, ceci est ma solution actuelle. Il a été écrit pour ressembler à la spécification aussi près que possible et sans la performance à l'esprit, donc je suis certain est peut améliorer considérablement:

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

LINQ est facultative. Je ne me soucie pas comment, tant qu'il est rapide :)

Edit: Il y a le cas particulier qu'un int apparaît 2n fois avec n> 1. Dans ce cas, le chèque doit échec, à savoir là devrait être 7 paires distinctes.

Edit: Résultat J'ai testé les solutions de Ani et Jon avec de petites modifications et a trouvé au cours de référence multiples fonctionne dans l'application cible qui a environ deux fois le débit de Jon Ani sur ma machine (certains Core 2 Duo sur Win7-64). Générer le tableau d'ints prend déjà environ aussi longtemps que les vérifications respectives, donc je suis content du résultat. Merci a tous!

Answer 1

Il est clair que, LINQ ne fournira pas la solution optimale ici, bien que j'améliorer votre solution LINQ actuelle à:

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

Pour le cas précis que vous mentionnez (0 - 31), voici plus rapide , solution basée sur un tableau. Il ne s'adapte pas très bien lorsque la gamme de nombres possibles est grande (utilisez une solution de hachage dans ce cas).

// 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: correction de bugs signalés par Jon Skeet. Je devrais également souligner que son algo est plus intelligent et probablement plus rapide.

Answer 2

Eh bien, compte tenu de vos besoins exacts, nous pouvons être un peu plus intelligents. Quelque chose comme ceci:

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

En gros, cela garde une trace de combien de valeurs non apparié vous avez encore, et a un « early out » si elle trouve toujours un brelan.

(Je ne sais pas désinvolture que ce sera plus rapide ou plus lent que l'approche d'Ani incrémenter puis la vérification des paires non appariées par la suite.)

Answer 3

Je voudrais créer un tableau de 32 éléments entiers, initialisé à zéro. Appelons ça "billy".

Pour chaque élément du tableau d'entrée, j'incrémenter [élément] billy 1.

A la fin, vérifiez si billy ne contient que 0 ou 2.

Answer 4

Presque certainement surpuissance quand vous » ve seulement eu 14 paires-ish et les seules valeurs possibles 32-ish, mais dans le cas général, vous pouvez faire quelque chose comme ceci:

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 gamme d'articles est 0-31, vous pouvez stocker 32 de un drapeaux bit dans un uint32.Je suggère de prendre chaque élément et de calculer mask = (1 item SHL), et de voir ce qui se passe si vous essayez 'or', 'xor', ou en ajoutant les valeurs du masque. Regardez les résultats pour les cas valides et invalides. Pour éviter les débordements, vous pouvez utiliser uint64 pour l'addition (car uint32 peut déborder s'il y a deux 31, quatre quatre 30 ou huit vingt-neuf).

Answer 6

Je suppose que (jamais mesuré la vitesse) ce codesnipet peut vous donner un nouveau point de vue:

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

Vous pouvez avoir les valeurs dans la variable doublé « deux fois »; Bien sûr, cela ne fonctionne que pour des valeurs inférieures à 32;