У алгоритма сортировки radix может быть разное время выполнения для данных с другим порядком?

Question

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

Я тестирую с 10.000.000 и 100.000.000 целыми числами в интервале [0, 1000000]. Эти цифры могут быть в серповидном, временном и случайном порядке.

Время выполнения для 100.000.000 номеров в порядке полумесяца и падения составляет около 20 секунд. Но для того же числа элементов со случайным порядком время выполнения составляет около 110 секунд.

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

Кто-нибудь знает, почему это происходит?

Это мой код:

void radix(Number** numbers) 
    { 
     unsigned int i, k, e = 1; 
     Number* bucket[10]; 
     Number* tail[10]; 
     Number* index; 

     for(k = 0; k < 7; k++, e *= 10) 
     { 
      for(i = 0; i < 10; i++) bucket[i] = tail[i] = NULL; 

      index = *numbers; 
      while(index != NULL) 
      { 
       i = (index->value/e) % 10; 

       if(tail[i] == NULL) 
        bucket[i] = index; 
       else 
        tail[i]->next = index; 

       tail[i] = index; 
       index = index->next; 
      } 

      for(i = 0; i < 10; i++) 
      { 
       if(tail[i] != NULL) 
       { 
        *numbers = bucket[i]; 
        index = tail[i]; 
        for(i++; i < 10; i++) 
        { 
         if(tail[i] != NULL) 
         { 
          index->next = bucket[i]; 
          index = tail[i]; 
         } 
        } 
       } 
      } 

      index->next = NULL; 
     } 
    } 

где Number является:

typedef struct number 
{ 
    unsigned int value; 
    struct number* next; 
} Number; 

Answer 1

Ответ, вероятно, будет связано с доступом к памяти и локальности ссылок.

По возрастанию/убыванию имеет регулярный шаблон, который может иметь большую временную локальность, а не столько по отношению к ведрам, сколько скорее по отношению к тому, как узлы связанного списка используются для чисел (особенно если они не смежны).

Например, если мы возьмем вход:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... 

Пройдется из ковша от 0 до 9 ведра, а затем обратно в ведро 0. Когда мы возвращаемся к ведру 0, мы доступ к number узел, доступ к которому был получен сравнительно недавно (всего 9 итераций назад), который, скорее всего, будет кэшироваться в более быструю и меньшую память.

Если мы используем случайный заказ, кто знает, когда мы вернемся к ведру 0? В результате существует большая вероятность того, что мы долгое время перемещаем данные из DRAM в кеш, прежде чем мы вернемся к памяти, используемой для числа на голове любого данного ведра. Результат может перевести на большее количество таких бывших number узлов, которые выселяются из кеша, и больше промахов в кеше, когда мы возвращаемся к такому ведру.

Неправильные предсказания отрасли также могут потреблять немного времени в отношении нерегулярного заказа. Профилирование должно помочь устранить причину.

Одна из возможных попыток, если вы на самом деле ограничены памятью, состоит в том, чтобы превратить ваши ведра в, скажем, развернутые списки, в которые вы глубоко скопировали числа. Это приведет к тому, что вы больше не будете получать доступ к памяти для ранее вставленных чисел, которые могли быть вставлены во многие итерации назад (потенциально большая переменная из-за случайного упорядочения). При этом мы начинаем возвращать некоторую временную локальность (и, возможно, пространственную локальность, если числа были смежно распределены), мы в противном случае проиграли бы с таким видом связанного списка. Затем возникает вопрос о повторном использовании непрерывной памяти для ковшей (для которой всего 10) вместо элементов внутри ведер с переменными шагами между ними. Мы также получаем пространственную локальность внутри ведер с развернутым представлением.

Но если все те же данные, только в другом порядке, это может повлиять на цену ? От 20 до 110 секунд слишком много для тех же данных.

Эффективность памяти может привести к различиям в порядках величин. http://lwn.net/Articles/250967/

Я не эксперт в этом вопросе (более «профиль его и попробуйте оптимизировать на основе рекомендаций»), но на основе прошлых результатов, которые я получил от оптимизации памяти, я часто ставил их на уровне с точки зрения эффекта с алгоритмической оптимизацией. Исключения будут тогда, когда разница в сложности будет грубой (ex: linearithmic vs quadratic), но даже линейно-лимитичный алгоритм может очень эффективно превзойти линейный с очень большими входами, если первый значительно более удобен для кеширования.