简介
网上看到一些有趣的程序和算法，里面涉及到的技术和思路非常的有趣，每当读到诸如此类，都让我拍案叫绝，独乐乐不如众乐乐，随有了此篇文章。文章中的代码都是用C/C++实现，如果对C/C++不熟悉也没关系，大体思路是相通的。
有趣的数组遍历
先来看一段数组遍历访问的代码，请问这段代码是否会正确执行：
void arr_test()
{
int p[5];
int n = sizeof(p)/sizeof(int);
for(int i = 0; i < n; ++i)
{
i[p] = 32;
}
}
上面面这段代码会正确的编译执行，原因是编译器会通过[]左边的值类型来决定[]的类型：
[]左边为值类型，则[]中为指针[]左边为指针，则[]中为值类型
假设指针变量为p，数组索引为i，如果是int类型的数组，那么当前地址为p + i * sizeof(int)，无论p和i的位置如何排列，最终结果保持不变。
如果索引或者指针是函数返回值，它们的先后执行会影响最终计算结果吗？
int p[5] = {1, 2, 3, 4, 5};
int* pt = p;
int i = 2;
int get_index()
{
pt = pt + i;
return i;
}
int arr_test_1()
{
return pt[get_index()];
}
int arr_test_2()
{
return get_index()[pt];
}
对于arr_test_1 返回值为3，所以如果我们期望get_index修改指针pt，传统访问数组的方法不可行。根据我们上面学到的内容，使用arr_test_2函数来先修改指针pt，这样就能得到我们期望的5。
但现实并没有那么美好，目前测试只有clang编译器std所有标准得到期望值5，gcc和msvc测试了std14，std20 都是先获取pt值，再执行get_index,结果为0。
这段程序是对C++17 creates a practical use of the backward array index operator -by Raymond Chen的赏析。
radix 排序算法
不使用比较操作符能否对一组数排序呢？有一个开发者讲述自己在刚入职时，使用了此算法对一组数排列，大大提升了性能，同时让自己的其他同事大为震惊。当然此算法的时间复杂度和空间复杂度说来话长，这里不再赘述。这个算法的核心理念是通过逐位排序，最终得到排序结果。它的流程如下：
- 找到数组中最大的数
max - 从个位开始到最高位进行排序
- 申请数组
int count[10]，因为10进制数的范围为0-9 - 遍历整个数组，统计此位对应的数量，假设统计个位，如果此数组的所有数字个位为
8的有10个，则count[8] = 10 - 为此位计算它们尾数的位置，假设
count[0] = 5，count[1] = 8，则0-5的位置被5个0占领，1的位置为8-13 - 遍历整个数组，找到此位对应的位置，记录值
- 申请数组
- 编译所有位后，得到结果为排序结果
const int k_base = 10;
// 获取最大值
int get_max(const int* arr, size_t n)
{
int max = 0;
for(int i = 0; i < n; ++i)
{
if(arr[i] > max)
{
max = arr[i];
}
}
return max;
}
void sort_by_exp(int* arr, size_t n, int exp)
{
// 统计对应位数数量
int count[k_base] = {0};
for(int i = 0; i < n; ++i)
{
int key = (arr[i] / exp) % k_base;
count[key]++;
}
// 计算对应位数尾数位置
for(int i = 1; i < k_base; ++i)
{
count[i] += count[i - 1];
}
// 因为记录的是尾数的位置，所以要倒序遍历，得到对应排序结果
int output[n];
for(int i = n - 1; i >= 0; i--)
{
int key = (arr[i] / exp) % k_base;
output[count[key] - 1] = arr[i];
count[key]--;
}
// 赋值给原数组
for(int i = 0; i < n; ++i)
{
arr[i] = output[i];
}
}
void radix_sort(int* arr, size_t n)
{
int max = get_max(arr, n);
for(int exp = 1; max / exp > 0; exp *= k_base)
{
sort_by_exp(arr, n, exp);
}
}
排列一亿8位电话号码
有开发者说接到一个需求，小于一亿8位数电话号码，内存只有100M，需要在一分钟内从硬盘读取文件，排序后写入文件。
看到这个问题的第一反应是 100000000 * 4byte 大概是 381M，看来没有好的解决方案，内存大小已经不满足条件，不用考虑后面的排序算法了。后面看到云风的解决方案，实现非常的优雅高效，这里来赏析一番。
排序算法的核心和radix思路非常的相似，甚至这里更加简单，此数列里的元素全为自然数，只是有些数不存在，那么我们只要遍历找出存在的数字，标记对应位置即可。按照此思路此算法如下：
/*
arr 数组指针
n 数组长度
length 数组元素最大值
*/
void pos_sort(int* arr, size_t n, int length)
{
int* output = (int*)malloc(length * sizeof(int));
memset(output, 0, length * sizeof(int));
// 标记自然数所对应位置
for(int i = 0; i < n; ++i)
{
int key = arr[i];
output[key] = 1;
}
// 获得要排序值，通过索引得到位置
for(int i = 0, key = 0; i < length; ++i)
{
if(output[i] != 0)
{
arr[key] = i;
key++;
}
}
free(output);
}
云风首先定义了数据结构，以及申请内存，这里涉及将32bit的数通过1bit来记录，这样直接将内存由381m变为不到12M。所以是满足要求使用100m内存对1亿数排序。
#define N (100000063/64)
struct bitset {
uint64_t bits[N];
};
static struct bitset *
number_new() {
struct bitset *S = (struct bitset *)malloc(sizeof(*S));
memset(S, 0, sizeof(*S));
return S;
}
这段代码首先申请64bit的数组，因为是整除，最大的余数为63，因此要加上63，再除以64保证空间足够。另外利用结构体的数据结构，最后调用malloc(sizeof(*S))申请内存，避免了直接使用unit64_t要使用传统的sizeof(arr) * sizeof(uint64_t)来计算数组长度，简化了书写，减少了错误。
核心算法是如何通过位记录值，最后写入时在将通过位还原出索引：
// 将32位数，通过标记1bit来记录
static void
number_insert(struct bitset *S, uint32_t v) {
assert(v < N * 64);
S->bits[v / 64] |= 1 << (v % 64);
}
// 通过索引乘以64，再加上1bit所在的位置得到最终值
static void
number_writefile(const char * filename, struct bitset *S) {
FILE *f = fopen(filename, "wb");
if (f == NULL)
return;
int i,j;
for (i=0;i<N;i++) {
uint64_t v = S->bits[i];
for (j = 0; j < 64 && v != 0; j++) {
if (v & 1) {
fprintf(f, "%d\n", i * 64 + j);
}
v >>= 1;
}
}
fclose(f);
}
结尾
计算机技术是一门非常有趣的学科，无数的开发者的智慧和经验令人叹为观止，去享受这些聪明才智为我们带来的快乐。