排序---基数排序

前言

个人小记

一、简介

基数排序是一种非比较排序，所以排序速度较快，当为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^16
   
    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));

    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^16
    int *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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

三、测试结果

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

四、优化错误原因

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