Реализация Radix-сортировки для словаря / коллекции KeyValuePair

Question

Я ищу быструю и эффективную реализацию Radix-Sort для коллекции Dictionary/KeyValuePair, если это возможно в C# (но не обязательно). Ключ представляет собой целое число от 1 000 000 до 9 999 999 999. Количество значений варьируется от 5 до нескольких тысяч. В данный момент я использую LINQ-OrderBy, то есть QuickSort. Для меня производительность очень важна, и я хотел бы проверить, будет ли сортировка по Radix быстрее. Я нашел только реализации Array. Конечно, я мог бы попробовать это сам, но поскольку я новичок в этой теме, я считаю, что это не будет самый быстрый и самый эффективный алгоритм.;-) Спасибо.

Rene

Answer 1

Проверяли ли вы свой код, чтобы определить, что сортировка на основе LINQ является узким местом в вашей программе? Вид LINQ довольно чертовски быстр. Например, приведенный ниже код умножает сортировку словаря, содержащего от 1000 до 10000 элементов. Среднее значение, превышающее 1000 циклов, составляет порядка 3,5 миллисекунд.

static void DoIt()
{
    int NumberOfTests = 1000;

    Random rnd = new Random();

    TimeSpan totalTime = TimeSpan.Zero;
    for (int i = 0; i < NumberOfTests; ++i)
    {
        // fill the dictionary
        int DictionarySize = rnd.Next(1000, 10000);
        var dict = new Dictionary<int, string>();
        while (dict.Count < DictionarySize)
        {
            int key = rnd.Next(1000000, 9999999);
            if (!dict.ContainsKey(key))
            {
                dict.Add(key, "x");
            }
        }
        // Okay, sort
        var sw = Stopwatch.StartNew();
        var sorted = (from kvp in dict
                        orderby kvp.Key
                        select kvp).ToList();
        sw.Stop();
        totalTime += sw.Elapsed;
        Console.WriteLine("{0:N0} items in {1:N6} ms", dict.Count, sw.Elapsed.TotalMilliseconds);
    }
    Console.WriteLine("Total time = {0:N6} ms", totalTime.TotalMilliseconds);
    Console.WriteLine("Average time = {0:N6} ms", totalTime.TotalMilliseconds / NumberOfTests);

Обратите внимание, что сообщенное среднее включает время JIT (первый раз в цикле, который занимает приблизительно 35 мс).

В то время как вполне возможно, что хорошая реализация сортировки с помощью радиуса улучшит производительность сортировки, я подозреваю, что ваши усилия по оптимизации лучше потратить в другом месте.