此基数排序代码中的最后一个“for”循环是做什么的?
What does the last `for` loop in this Radix Sort code do?
我正在阅读 Zed A. Shaw 的 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 个 for 循环 radix_sort
。据我所知,第一个只是简单地计算字节值,第二个函数基本上是累积频率table,其中每个条目都是前一个条目的总和。
我仍然无法理解 ByteOf(x, y)
宏和第三个 for 循环。我试过阅读使用 C++ 实现的 Wikipedia page for Radix-sort and I read another article。但是,这些文章中每一篇中编写的代码都与他编写的代码不匹配。
我了解基数排序的原理。基本上,我们根据每个数字对其进行分组,为我们遇到的每个新数字重新排列分组。例如,要对数组 [223, 912, 275, 100, 633, 120, 380]
进行排序,您首先将它们按个位分组,这样您将得到 [380, 100, 120]
、[912]
、[633, 223]
、[275]
。然后你对十位和百位做同样的事情,直到你有 运行 个数字。
如果能帮助解释他的代码,我们将不胜感激。
谢谢。
ByteOf(x, y) 等同于:
#define ByteOf(x, y) ((*(x) >> (offset*8)) & 0xff)
也就是说,它将字节#{offset} 的值隔离在一个值内。
第二个循环是一种分配器。如果前六个 counts[] 在第一个循环之后是 1,2,4,0,16,25,那么在第二个循环之后它们将是 0,1,3,7,7,23。这指示第三个循环(通过 source[])将目标布局为:
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];
}
我认为它更清楚地显示了关系,即第i个源元素正在被复制到目标中的索引。 dest 中的索引位于先前为此 digit 计算的分区 (count[]) 的开头。由于此位置现在有一个数字,我们增加此分区的开始以防止 over-writing 它。
请注意,(source+i) 两边的括号对于在 ByteOf 中获取正确的转换地址是必需的。
我正在阅读 Zed A. Shaw 的 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 个 for 循环 radix_sort
。据我所知,第一个只是简单地计算字节值,第二个函数基本上是累积频率table,其中每个条目都是前一个条目的总和。
我仍然无法理解 ByteOf(x, y)
宏和第三个 for 循环。我试过阅读使用 C++ 实现的 Wikipedia page for Radix-sort and I read another article。但是,这些文章中每一篇中编写的代码都与他编写的代码不匹配。
我了解基数排序的原理。基本上,我们根据每个数字对其进行分组,为我们遇到的每个新数字重新排列分组。例如,要对数组 [223, 912, 275, 100, 633, 120, 380]
进行排序,您首先将它们按个位分组,这样您将得到 [380, 100, 120]
、[912]
、[633, 223]
、[275]
。然后你对十位和百位做同样的事情,直到你有 运行 个数字。
如果能帮助解释他的代码,我们将不胜感激。 谢谢。
ByteOf(x, y) 等同于:
#define ByteOf(x, y) ((*(x) >> (offset*8)) & 0xff)
也就是说,它将字节#{offset} 的值隔离在一个值内。
第二个循环是一种分配器。如果前六个 counts[] 在第一个循环之后是 1,2,4,0,16,25,那么在第二个循环之后它们将是 0,1,3,7,7,23。这指示第三个循环(通过 source[])将目标布局为:
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];
}
我认为它更清楚地显示了关系,即第i个源元素正在被复制到目标中的索引。 dest 中的索引位于先前为此 digit 计算的分区 (count[]) 的开头。由于此位置现在有一个数字,我们增加此分区的开始以防止 over-writing 它。
请注意,(source+i) 两边的括号对于在 ByteOf 中获取正确的转换地址是必需的。