Comptage des doublons dans une Listbox

Question

J'essaie de développer une application simple en C# pour compter le nombre de doublons dans une liste. J'ai besoin de compter tout le nombre de doublons et d'afficher un suffixe de rang aux 3 premiers éléments les plus dupliqués. Par exemple, supposons qu'une liste a 7 éléments appelés 'apple', 6 éléments appelés 'pear', 4 éléments appelés 'peach' et 3 éléments appelés 'orange', après le processus, elle devrait afficher la liste comme suit:

 
apple (7) 
pear (6) 
peach (4) 
orange 

Answer 1

Voici une autre méthode d'utilisation de Linq, présentée sous la forme d'un test minuté qui permet de voir si elle fonctionne plus rapidement. Ce sont les résultats que j'obtenus avec 1000 itérations:

Total words: 1324 
Min  Max  Mean  Method 
5305  22889  5739.182 LinkMethodToArray 
5053  11973  5418.355 LinkMethod 
3112  6726  3252.457 HashMethod 

Le LinkMethod est seulement d'environ 1,6 fois plus lent dans ce cas. Pas aussi mauvais que beaucoup de code Linq que j'ai testé la performance, mais ce n'était que 1324 mots.

Edit # 1

C'était avant d'ajouter le genre. Avec le tri, vous pouvez voir qu'il est comparable à la méthode Linq. Bien sûr, copier le hachage dans une liste, puis trier la liste n'est pas le moyen le plus efficace de le faire. Nous pourrions améliorer cela. Il y a quelques façons qui me viennent à l'esprit, mais aucune d'elles n'est simple et nécessiterait d'écrire beaucoup de code personnalisé.

Puisque nous voulons utiliser ce qui est déjà disponible et que nous voulons que le code soit clair, je dois dire que Linq est en fait un très bon choix. Cela a changé mon opinion sur Linq .. un peu. J'ai vu beaucoup trop d'autres comparaisons où Linq finit désastreusement plus lentement (de l'ordre de 1000 fois plus lentement) pour donner le feu vert à l'utilisation de Linq partout et partout, mais certainement dans ce lieu il brille très bien. Je suppose que la morale est, comme elle l'a toujours été, test, test, test.

Voici les valeurs avec le tri ajouté à HashMethod.

Total words: 1324 
Min  Max  Mean  Method 
5284  21030  5667.808 LinkMethodToArray 
5081  36339  5425.626 LinkMethod 
5017  27583  5288.602 HashMethod 

Edit # 2

Quelques optimisations simples (pré-initialisation à la fois le dictionnaire et la liste) font HashMethod un peu noticably plus vite.

Total words: 1324 
Min  Max  Mean  Method 
5287  16299  5686.429 LinkMethodToArray 
5081  21813  5440.758 LinkMethod 
4588  8420  4710.659 HashMethod 

Edit # 3

Avec un jeu de mot plus, ils deviennent beaucoup plus encore. En fait, la méthode Linq semble se démarquer à chaque fois. Voici la Constitution des États-Unis (les sept articles et signatures). Cela peut être dû au fait que la déclaration contient beaucoup de mots répétés ("Il a ...").

Total words: 4545 
Min  Max  Mean  Method 
13363  36133  14086.875 LinkMethodToArray 
12917  26532  13668.914 LinkMethod 
13601  19435  13836.955 HashMethod 

code:

using System; 
using System.Collections.Generic; 
using System.Diagnostics; 
using System.IO; 
using System.Linq; 
using System.Threading; 

class Program 
{ 
    static void Main() 
    { 
     Thread.CurrentThread.Priority = ThreadPriority.Highest; 

     // Declaration.txt is a copy of the Declaration of Independence 
     // which can be found here: http://en.wikisource.org/wiki/United_States_Declaration_of_Independence 
     string declaration = File.ReadAllText("Declaration.txt"); 
     string[] items = declaration.ToLower().Split(new char[] { ',', '.', ':', ';', '-', '\r', '\n', '\t', ' ' }, StringSplitOptions.RemoveEmptyEntries); 

     // pre-execute outside timing loop 
     LinqMethodToArray(items); 
     LinqMethod(items); 
     HashMethod(items); 

     int iterations = 1000; 
     long min1 = long.MaxValue, max1 = long.MinValue, sum1 = 0; 
     long min2 = long.MaxValue, max2 = long.MinValue, sum2 = 0; 
     long min3 = long.MaxValue, max3 = long.MinValue, sum3 = 0; 

     Console.WriteLine("Iterations: {0}", iterations); 
     Console.WriteLine("Total words: {0}", items.Length); 

     Stopwatch sw = new Stopwatch(); 

     for (int n = 0; n < iterations; n++) 
     { 
      sw.Reset(); 
      sw.Start(); 
      LinqMethodToArray(items); 
      sw.Stop(); 
      sum1 += sw.ElapsedTicks; 
      if (sw.ElapsedTicks < min1) 
       min1 = sw.ElapsedTicks; 
      if (sw.ElapsedTicks > max1) 
       max1 = sw.ElapsedTicks; 

      sw.Reset(); 
      sw.Start(); 
      LinqMethod(items); 
      sw.Stop(); 
      sum2 += sw.ElapsedTicks; 
      if (sw.ElapsedTicks < min2) 
       min2 = sw.ElapsedTicks; 
      if (sw.ElapsedTicks > max2) 
       max2 = sw.ElapsedTicks; 

      sw.Reset(); 
      sw.Start(); 
      HashMethod(items); 
      sw.Stop(); 
      sum3 += sw.ElapsedTicks; 
      if (sw.ElapsedTicks < min3) 
       min3 = sw.ElapsedTicks; 
      if (sw.ElapsedTicks > max3) 
       max3 = sw.ElapsedTicks; 
     } 

     Console.WriteLine("{0,-10} {1,-10} {2,-10} Method", "Min", "Max", "Mean"); 
     Console.WriteLine("{0,-10} {1,-10} {2,-10} LinkMethodToArray", min1, max1, (double)sum1/iterations); 
     Console.WriteLine("{0,-10} {1,-10} {2,-10} LinkMethod", min2, max2, (double)sum2/iterations); 
     Console.WriteLine("{0,-10} {1,-10} {2,-10} HashMethod", min3, max3, (double)sum3/iterations); 
    } 

    static void LinqMethodToArray(string[] items) 
    { 
     var ranking = (from item in items 
         group item by item into r 
         orderby r.Count() descending 
         select new { Name = r.Key, Rank = r.Count() }).ToArray(); 
     for (int n = 0; n < ranking.Length; n++) 
     { 
      var item = ranking[n]; 
      DoSomethingWithItem(item); 
     } 
    } 

    static void LinqMethod(string[] items) 
    { 
     var ranking = (from item in items 
         group item by item into r 
         orderby r.Count() descending 
         select new { Name = r.Key, Rank = r.Count() }); 
     foreach (var item in ranking) 
      DoSomethingWithItem(item); 
    } 

    static void HashMethod(string[] items) 
    { 
     var ranking = new Dictionary<string, int>(items.Length/2); 
     foreach (string item in items) 
     { 
      if (!ranking.ContainsKey(item)) 
       ranking[item] = 1; 
      else 
       ranking[item]++; 
     } 
     var list = new List<KeyValuePair<string, int>>(ranking); 
     list.Sort((a, b) => b.Value.CompareTo(a.Value)); 
     foreach (KeyValuePair<string, int> pair in list) 
      DoSomethingWithItem(pair); 

    } 

    static volatile object hold; 
    static void DoSomethingWithItem(object item) 
    { 
     // This method exists solely to prevent the compiler from 
     // optimizing use of the item away so that this program 
     // can be executed in Release build, outside the debugger. 
     hold = item; 
    } 
} 

Answer 2

Comme nous ne connaissons pas la source de données que vous utilisez, voici un exemple générique LINQ qui pourrait vous aider à démarrer.

string[] items = { "apple", "pear", "peach", "apple", "orange", "peach", "apple" }; 

var ranking = (from item in items 
       group item by item into r 
       orderby r.Count() descending 
       select new { name = r.Key, rank = r.Count() }).Take(3); 

Ceci renvoie une collection d'objets contenant le name and rank des 3 premiers éléments. Bien sûr, vous devez remplacer la matrice items ici par ce que chaque source de données que vous utilisez pour remplir la ListBox, et si les éléments ne sont pas simplement des chaînes simples mais des éléments plus complexes, vous ajusteriez la requête LINQ de manière appropriée.

Voici un exemple de ce qui précède qui remplira une zone de liste avec les données comme dans le formulaire que vous avez montré.

string[] items = { "apple", "pear", "peach", "apple", "orange", "peach", "apple" }; 

    var ranking = (from item in items 
       group item by item into r 
       orderby r.Count() descending 
       select new { name = r.Key, rank = r.Count() }).ToArray(); 

    for (int i = 0; i < ranking.Length; ++i) 
    { 
    var item = ranking[i]; 
    if (i < 3) 
    { 
     listBox1.Items.Add(string.Format("{0} ({1})", item.name, item.rank)); 
    } 
    else 
    { 
     listBox1.Items.Add(item.name); 
    } 
    } 

Cela fait la même chose que le premier exemple, mais les transforme les résultats à un tableau et alimente une zone de liste avec les articles avec les 3 premiers éléments montrant là rang.