怎么通过贷款网站找做贷款客户,北京专业网站的建设,哈尔滨 网站开发,创建个人主页网站前言
个人小记 一、简介
基数排序是一种非比较排序#xff0c;所以排序速度较快#xff0c;当为32位int整数排序时#xff0c;可以将数分为个位十位分别为2^16,使得拷贝只需要两轮#xff0c;从而达到2*n#xff0c;然后给一个偏移量#xff0c;使得可以对负数排序。以…前言
个人小记 一、简介
基数排序是一种非比较排序所以排序速度较快当为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) __ca;\ab,b__c;\
}
#define TEST(func,arr,l,r)\
{\printf(test:%s \t,#func);\int nr-l;\int* t(int*)malloc(sizeof(int)*n);\long long aclock();\func(t,l,r);\long long bclock();\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 i1;in;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 i0;in;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 k65536;//2^16memset(cont,0,sizeof(int)*k*2);for(int il;ir;i){if(arr[i]0)cont[kabs(arr[i]%k)];//理论个位else cont[arr[i]%k];}for(int i1;ik;i)cont[i]cont[i-1]cont[i];for(int ir-1;il;i--){if(arr[i]0)temp[--cont[abs(arr[i]%k)]]arr[i];else temp[--cont[arr[i]%k]]arr[i];}memcpy(arrl,temp,sizeof(int)*(r-l));memset(cont,0,sizeof(int)*k*2);for(int il;ir;i){if(arr[i]0)cont[kabs(arr[i]/k)];//理论十位else cont[arr[i]/k];}for(int i1;ik;i)cont[i]cont[i-1]cont[i];for(int ir-1;il;i--){if(arr[i]0)temp[--cont[abs(arr[i]/k)]]arr[i];else temp[--cont[arr[i]/k]]arr[i];}memcpy(arrl,temp,sizeof(int)*(r-l));return ;
}
void radix_sort(int *arr,int l,int r)
{int k65536;//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 il;ir;i){if(arr[i]0)cont_1[kabs(arr[i]%k)];//理论个位else cont_1[arr[i]%k];}for(int i1;ik;i)cont_1[i]cont_1[i-1]cont_1[i];for(int ir-1;il;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(arrl,temp_1,sizeof(int)*(r-l));memset(cont_1,0,sizeof(int)*k*2);for(int il;ir;i){if(arr[i]0)cont_1[kabs(arr[i]/k)];//理论十位else cont_1[arr[i]/k];}for(int i1;ik;i)cont_1[i]cont_1[i-1]cont_1[i];for(int ir-1;il;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(arrl,temp_1,sizeof(int)*(r-l));free(cont_1);free(temp_1);return ;
}int main()
{srand((unsigned)time(0));int *arrinit_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.内存分配策略: 操作系统的内存分配策略可能也会影响性能。例如某些系统可能会更快地分配大块内存而其他系统可能在处理多个小的分配时更有效率。
