Реализация Radix-Sort для словаря / коллекции KeyValuePair - PullRequest
Новая
       26

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

1 голос
/ 03 октября 2011

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

Рене

1 Ответ

0 голосов
/ 03 октября 2011

Проверяли ли вы свой код, чтобы определить, что сортировка на основе 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 мс).

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

...