Подсчет дубликатов в списке

Question

Я пытаюсь разработать простое приложение на C # для подсчета количества дубликатов в списке. Мне нужно подсчитать все количество дубликатов и отобразить суффикс ранга для трех наиболее дублированных элементов. Например, предположим, что список состоит из 7 элементов, называемых «яблоками», 6 элементов, называемых «грушами», 4 элементов, называемых «персиковыми», и 3 элементов, называемых «оранжевыми», после процесса список должен отображаться как:

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

Answer 1

Поскольку мы не знаем, какой источник данных вы используете, вот общий пример LINQ, который может помочь вам начать работу.

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

Возвращает коллекцию объектов, содержащую name and rank из трех верхних элементов.

Конечно, вы бы заменили массив items здесь тем, что каждый источник данных вы используете для заполнения ListBox, и если элементы не просто строки, а более сложные элементы, вы бы соответствующим образом скорректировали запрос LINQ. *

Вот пример вышеупомянутого, который заполнит список данными, как в форме, которую вы показали.

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

Это делает то же, что и в первом примере, но преобразует результаты в массив и заполняет список элементами с первыми 3 элементами, показывающими их ранг.

Answer 2

Вот альтернативный метод использования Linq, представленный в виде временного теста, чтобы увидеть, который работает быстрее.Вот результаты, которые я получил за 1000 итераций:

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

В этом случае LinkMethod работает примерно в 1,6 раза медленнее.Не так плохо, как много кода Linq, который я тестировал на производительность, но это было всего 1324 слова.

Edit # 1

Это было до добавления сортировки.С помощью сортировки вы можете увидеть, что это сопоставимо с методом Linq.Конечно, копирование хеша в список и последующая сортировка списка - не самый эффективный способ сделать это.Мы могли бы улучшить это.Есть несколько способов, которые приходят на ум, но ни один из них не прост и потребует написания большого количества пользовательского кода.

Поскольку мы хотим использовать то, что уже доступно, и хотим, чтобы код был понятным,Я должен сказать, что Linq на самом деле очень хороший выбор.Это немного изменило мое мнение о Linq.Я видел слишком много других сравнений, где Linq заканчивается катастрофически медленнее (в 1000 раз медленнее), чтобы дать зеленый свет использованию Linq где угодно и везде, но, безусловно, в этом одном месте он светит очень хорошо.

Полагаю, мораль, как и всегда, - тест, тест, тест.

Вот значения с сортировкой, добавленной в 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

Несколько простых оптимизаций (предварительная инициализация словаря и списка) делают HashMethod заметно быстрее.

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

Edit# 3

С большим набором слов они становятся намного более ровными.На самом деле, метод Linq, кажется, каждый раз обнуляется.Вот Конституция США (все семь статей и подписи).Это может быть связано с тем, что декларация содержит много повторяющихся слов («У него есть ...»).

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

Код:

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