Что делает последний цикл `for` в этом коде сортировки Radix? - PullRequest
Новая
       26

Что делает последний цикл `for` в этом коде сортировки Radix?

0 голосов
/ 03 июня 2019

Я читал книгу Learn C The Hard Way Зеда А. Шоу, и я просматривал его реализацию алгоритма сортировки по основанию.

Это его код: 

#define ByteOf(x, y) (((u_int8_t *)x)[y])

static inline void radix_sort(short offset, uint64_t max,
        uint64_t * source, uint64_t * dest)
{
  uint64_t count[256] = { 0 };
  uint64_t *cp = NULL;
  uint64_t *sp = NULL;
  uint64_t *end = NULL;
  uint64_t s = 0;
  uint64_t c = 0;

  // Count occurences of every byte value
  for (sp = source, end = source + max; sp < end; sp++) {
    count[ByteOf(sp, offset)]++;
  }

  // transform count into index by summing
  // elements and storing them into same array.
  for (s = 0, cp = count, end = count + 256; cp < end; cp++) {
    c = *cp;
    *cp = s;
    s += c;
  }

  // fill dest with right values in the right place
  for (sp = source, end = source + max; sp < end; sp++) {
    cp = count + ByteOf(sp, offset);
    printf("dest[%d] = %d\n", *cp, *sp);
    dest[*cp] = *sp;
    ++(*cp);
  }
}

Выше приведена только вспомогательная функция. Его фактическая сортировка по основанию сделана здесь: 

void RadixMap_sort(RadixMap * map)
{
  uint64_t *source = &map->contents[0].raw;
  uint64_t *temp = &map->temp[0].raw;

  radix_sort(0, map->end, source, temp);
  radix_sort(1, map->end, temp, source);
  radix_sort(2, map->end, source, temp);
  radix_sort(3, map->end, temp, source);
}

Вот структуры, которые он определил: 

typedef union RMElement {
  uint64_t raw;
  struct {
    uint32_t key;
    uint32_t value;
  } data;
} RMElement;

typedef struct RadixMap {
  size_t max;
  size_t end;
  uint32_t counter;
  RMElement *contents;
  RMElement *temp;
} RadixMap;

Я могу понять первые 2 цикла для встроенной функции radix_sort. Насколько я понимаю, первая просто подсчитывает байтовые значения, а вторая функция в основном составляет таблицу накопленной частоты, где каждая запись является суммой предыдущих записей.

Я все еще не могу обернуть голову вокруг макроса ByteOf(x, y) и третьего цикла for. Я попытался прочитать страницу Википедии для Radix-sort, и я прочитал другую статью , в которой использовалась реализация C ++. Однако код, написанный в каждой из этих статей, не соответствует коду, который он написал.

Я понимаю, как Radix Sort работает в принципе. По сути, мы группируем его в соответствии с каждой цифрой, переставляя группировки для каждой новой цифры, с которой мы сталкиваемся. Например, чтобы отсортировать массив [223, 912, 275, 100, 633, 120, 380], сначала нужно сгруппировать их по разряду цифр, чтобы получить [380, 100, 120], [912], [633, 223], [275]. Затем вы делаете то же самое с десятками и сотнями, пока не исчерпаете цифры.

Буду признателен за любую помощь в объяснении его кода. Спасибо.

1 Ответ

1 голос
/ 03 июня 2019

ByteOf (x, y) совпадает с: 

#define ByteOf(x, y)  ((*(x) >> (offset*8)) & 0xff)

То есть он изолирует значение байта # {смещения} внутри значения.

Второй цикл является своего рода распределителем. Если бы первые шесть отсчетов [] были 1,2,4,0,16,25 после первого цикла, они были бы 0,1,3,7,7,23 после второго. Это направляет третий цикл (над источником []), чтобы расположить место назначения как: 

ByteOf       index       number of values
0            0           1
1            1           2
2            3           4
3            7           0 -- there are none.
4            7           16
5            23          25

Мне немного понятнее переписать третий цикл как: 

  for (i = 0; i < max; i++) {
    dest[count[ByteOf((source+i), offset)]++] = source[i];
  }

Я думаю, что это показывает связь более четко, то есть, что элемент источника ith копируется в индекс в dest. Индекс в dest находится в начале раздела (count []), ранее вычисленного для этой цифры . Поскольку теперь в этом месте есть число, мы увеличиваем начало этого раздела, чтобы предотвратить его перезапись.

Обратите внимание, что квадратные скобки (source + i) необходимы для получения правильного адреса для приведения в ByteOf.

...