排序---基数排序

前言

个人小记

---

一、简介

基数排序是一种非比较排序，所以排序速度较快，当为32位int整数排序时，可以将数分为个位十位分别为2^16,使得拷贝只需要两轮，从而达到2*n，然后给一个偏移量，使得可以对负数排序。以下是一个非正确（自以为正确）的基数排序优化和未优化的比较。（注意：这可是对1000万的数据排序！前几个排序都是10万的数据！）

二、代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX_ARR 10000000
#define swap(a,b)\
{\__typeof(a) __c=a;\a=b,b=__c;\
}
#define TEST(func,arr,l,r)\
{\printf("test:%s \t",#func);\int n=r-l;\int* t=(int*)malloc(sizeof(int)*n);\long long a=clock();\func(t,l,r);\long long b=clock();\if(check(t,n))printf("OK %lldms\n",(b-a)*1000/CLOCKS_PER_SEC);\else printf("FAIL\n");\free(t);\
}int check(int *t,int n)
{for(int i=1;i<n;i++){if(t[i-1]>t[i])return 0;}return 1;
}int * init_arr(int n)
{int*arr=(int*)malloc(sizeof(int)*n);for(int i=0;i<n;i++){if(rand()%2)arr[i]=-rand()%10000000;else arr[i]=rand()%10000000;}return arr;
}
int *cont,*temp;
void PO_radix_sort(int *arr,int l,int r)
{int k=65536;//2^16memset(cont,0,sizeof(int)*k*2);for(int i=l;i<r;i++){if(arr[i]<0)cont[k+abs(arr[i]%k)]++;//理论个位else cont[arr[i]%k]++;}for(int i=1;i<k;i++)cont[i]=cont[i-1]+cont[i];for(int i=r-1;i>=l;i--){if(arr[i]<0)temp[--cont[abs(arr[i]%k)]]=arr[i];else temp[--cont[arr[i]%k]]=arr[i];}memcpy(arr+l,temp,sizeof(int)*(r-l));memset(cont,0,sizeof(int)*k*2);for(int i=l;i<r;i++){if(arr[i]<0)cont[k+abs(arr[i]/k)]++;//理论十位else cont[arr[i]/k]++;}for(int i=1;i<k;i++)cont[i]=cont[i-1]+cont[i];for(int i=r-1;i>=l;i--){if(arr[i]<0)temp[--cont[abs(arr[i]/k)]]=arr[i];else temp[--cont[arr[i]/k]]=arr[i];}memcpy(arr+l,temp,sizeof(int)*(r-l));return ;
}
void radix_sort(int *arr,int l,int r)
{int k=65536;//2^16int *cont_1=(int *)malloc(sizeof(int)*k*2);int *temp_1=(int *)malloc(sizeof(int)*(r-l));memset(cont_1,0,sizeof(int)*k*2);for(int i=l;i<r;i++){if(arr[i]<0)cont_1[k+abs(arr[i]%k)]++;//理论个位else cont_1[arr[i]%k]++;}for(int i=1;i<k;i++)cont_1[i]=cont_1[i-1]+cont_1[i];for(int i=r-1;i>=l;i--){if(arr[i]<0)temp_1[--cont_1[abs(arr[i]%k)]]=arr[i];else temp_1[--cont_1[arr[i]%k]]=arr[i];}memcpy(arr+l,temp_1,sizeof(int)*(r-l));memset(cont_1,0,sizeof(int)*k*2);for(int i=l;i<r;i++){if(arr[i]<0)cont_1[k+abs(arr[i]/k)]++;//理论十位else cont_1[arr[i]/k]++;}for(int i=1;i<k;i++)cont_1[i]=cont_1[i-1]+cont_1[i];for(int i=r-1;i>=l;i--){if(arr[i]<0)temp_1[--cont_1[abs(arr[i]/k)]]=arr[i];else temp_1[--cont_1[arr[i]/k]]=arr[i];}memcpy(arr+l,temp_1,sizeof(int)*(r-l));free(cont_1);free(temp_1);return ;
}int main()
{srand((unsigned)time(0));int *arr=init_arr(MAX_ARR);cont=(int*)malloc(sizeof(int)*65536*2);temp=(int *)malloc(sizeof(int)*MAX_ARR);TEST(radix_sort,arr,0,MAX_ARR); TEST(PO_radix_sort,arr,0,MAX_ARR); free(arr);free(cont);free(temp);return 0;
}

三、测试结果

test:radix_sort         OK 284ms
test:PO_radix_sort      OK 302ms

四、优化错误原因

1.内存局部性: radix_sort 在每次调用时都会分配新的内存，这可能意味着它使用的内存更有可能在CPU的缓存中，因为它是最近分配的。相比之下，PO_radix_sort 使用的是预先分配的全局数组，这些数组可能不在缓存中，尤其是在程序运行了其他代码之后。内存局部性差可能导致更多的缓存未命中，从而降低性能。

2.内存碎片: 如果程序在调用 PO_radix_sort 之前已经运行了一段时间，全局数组可能会在物理内存中分散开来，这增加了内存访问的开销。而 radix_sort 动态分配的内存更有可能是连续的，这有助于提高访问速度。

3.编译器优化: 动态分配的内存可能使得编译器能够更好地优化 radix_sort 函数，因为编译器知道这些内存是局部的，并且其生命周期仅限于函数调用。全局变量通常更难以优化，因为它们必须在整个程序的生命周期内保持有效。

4.多次函数调用: 如果 TEST 宏多次调用 PO_radix_sort，全局数组 cont 和 temp 不会在每次调用之间清除或重新初始化，这可能导致性能下降。而 radix_sort 每次调用都会得到新的内存，这确保了每次排序都是从一个干净的状态开始的。

5.内存分配策略: 操作系统的内存分配策略可能也会影响性能。例如，某些系统可能会更快地分配大块内存，而其他系统可能在处理多个小的分配时更有效率。