Advertisement
1gA

Radix Sort

1gA
Sep 20th, 2019
144
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <math.h>
  5. #include <stdbool.h>
  6. #include <time.h>
  7. #include <omp.h>
  8.  
  9. #define NO_MKL
  10. //#define TEST
  11. #define TEST2
  12.  
  13. //Ignore the test functions, I didn't bother removing them
  14.  
  15. void checkNullPtr(void *ptr){
  16.     if(ptr == NULL){
  17.         printf("Allocation Failed\n");
  18.         exit(1);
  19.  
  20.     }
  21. }
  22.  
  23. #ifdef TEST2
  24. void printArr(int *arr, size_t length){
  25.     for(int i=0; i<length; i++){
  26.         printf("%d ", arr[i]);
  27.     }
  28.     printf("\n");
  29. }
  30.  
  31. void checkAscending(int *arr, size_t length){
  32.     bool ascending = true;
  33.     if(length <= 1){
  34.         printf("%zd element in array\n", length);
  35.     }else{
  36.         for(int i=1; i<length; i++){
  37.             if(arr[i] < arr[i - 1]){
  38.                 ascending = false;
  39.             }
  40.         }
  41.         if(ascending){
  42.             printf("Ascending\n");
  43.         }else{
  44.             printf("Not Ascending - Test Failed\n");
  45.         }
  46.     }
  47. }
  48.  
  49. #endif
  50.  
  51. //Was gonna write a version using mkl - hasn't happened yet
  52. #ifdef NO_MKL
  53. int getMax(int *arr, size_t length){
  54.     int max = 0;
  55.     for(int i=0; i<length; i++){
  56.         if(arr[i] > max){
  57.             max = arr[i];
  58.         }
  59.     }
  60.     return max;
  61. }
  62. #endif
  63.  
  64. inline int tgtPlace(int value, int base, int power){
  65.     return  (int)(value / pow(base, power)) % base;
  66. }
  67.  
  68. void countingSort(int *arr, int *out, size_t length, int base, int power, int *count, int *partitions, int pSize){
  69.     int digit;
  70.     memset(count, 0, sizeof(int) * base * pSize);
  71.     #ifdef TEST
  72.     printf("Counting\n");
  73.     #endif
  74.     #pragma omp parallel
  75.     {
  76.         #pragma omp for private(digit)
  77.         for(int i=0; i<pSize; i++){
  78.             if(i != pSize - 1){
  79.                 for(int j=partitions[i]; j<partitions[i + 1]; j++){
  80.                     digit = tgtPlace(arr[j], base, power);
  81.                     count[i + digit * pSize + 1]++;
  82.                 }
  83.             }else{
  84.                 for(int j=partitions[i]; j<length; j++){
  85.                     digit = tgtPlace(arr[j], base, power);
  86.                     if(digit < base - 1){
  87.                         count[i + digit * pSize + 1]++;
  88.                     }
  89.                 }
  90.             }
  91.         }
  92.  
  93.         #pragma omp barrier
  94.         if(omp_get_thread_num() == 0){
  95.             #ifdef TEST
  96.             printf("Histogram\n");
  97.             #endif
  98.             for(int i = 1; i < base * pSize; i++){
  99.                 count[i] += count[i - 1];
  100.             }
  101.            
  102.             #ifdef TEST
  103.             printf("Rearranging\n");
  104.             #endif
  105.         }
  106.         #pragma omp barrier
  107.  
  108.         #pragma omp for
  109.         for(int i=0; i<pSize; i++){
  110.             if(i != pSize - 1){
  111.                 for(int j=partitions[i]; j<partitions[i + 1]; j++){
  112.                     digit = tgtPlace(arr[j], base, power);
  113.                     out[count[i + digit * pSize]++] = arr[j];
  114.                 }
  115.             }else{
  116.                 for(int j=partitions[i]; j<length; j++){
  117.                     digit = tgtPlace(arr[j], base, power);
  118.                     out[count[i + digit * pSize]++] = arr[j];
  119.                 }
  120.             }
  121.         }
  122.     }
  123. }
  124.  
  125. void radixSort(int *arr, size_t length, int max, unsigned int maxPartitions){
  126.     int base = 0;
  127.     int lL2 = (int) log2(length);
  128.     if(lL2 < 15){
  129.         //base = pow(2, lL2);
  130.         base = 2<<(lL2 - 1);
  131.  
  132.     }else{
  133.         base = 32768;
  134.     }
  135.  
  136.     //printf("base %d\n", base);
  137.     int maxI = (int) log(max) / log(base);
  138.  
  139.  
  140.     int *count = NULL;
  141.     int *partitions = NULL;
  142.     int pSize;
  143.     if(length > maxPartitions){
  144.         count = malloc(base * maxPartitions * sizeof(int));
  145.         partitions = malloc(maxPartitions * sizeof(int));
  146.         pSize = maxPartitions;
  147.     }else{
  148.         count = malloc(base * length * sizeof(int));
  149.         partitions = malloc(length * sizeof(int));
  150.         pSize = length;
  151.     }
  152.     checkNullPtr(count);
  153.     checkNullPtr(partitions);
  154.  
  155.  
  156.     partitions[0] = 0;
  157.     #pragma omp parallel for
  158.     for(int i=1; i<pSize; i++){
  159.         partitions[i] = (int) length / pSize * i;
  160.     }
  161.  
  162.     int *arrT = NULL;
  163.     arrT = malloc(length * sizeof(int));
  164.     int *arrT2 = NULL;
  165.     arrT2 = malloc(length * sizeof(int));
  166.     checkNullPtr(arrT);
  167.     checkNullPtr(arrT2);
  168.  
  169.     int *temp;
  170.  
  171.     #ifdef TEST
  172.     printf("Running\n");
  173.     #endif
  174.  
  175.     countingSort(arr, arrT, length, base, 0, count, partitions, pSize);
  176.     if(maxI > 0){
  177.         for(int i=1; i<maxI; i++){
  178.  
  179.             countingSort(arrT, arrT2, length, base, i, count, partitions, pSize);
  180.            
  181.             #ifdef TEST
  182.             printArr(arrT, length);
  183.             #endif
  184.  
  185.             temp = arrT;
  186.             arrT = arrT2;
  187.             arrT2 = temp;
  188.         }
  189.         countingSort(arrT, arr, length, base, maxI, count, partitions, pSize);
  190.     }else{
  191.         #ifdef TEST
  192.         printf("Copying\n");
  193.         #endif
  194.         memcpy(arr, arrT, sizeof(int) * length);
  195.     }
  196.  
  197.  
  198.     //memcpy(arr, arrT, sizeof(int) * length);
  199.  
  200.     free(arrT);
  201.     free(arrT2);
  202.     free(count);
  203.     free(partitions);
  204.     //return arr;
  205. }
  206.  
  207.  
  208. //For benchmarking purposes
  209. int compFunc (const void * a, const void * b) {
  210.    return ( *(int*)a - *(int*)b );
  211. }
  212.  
  213. #define ARR_LENGTH 200000
  214. int main(){
  215.     //int arr[] = {0, 1, 2, 4, 5, 2, 5, 3, 8, 9};
  216.     int length = ARR_LENGTH;
  217.     int arr[ARR_LENGTH];
  218.  
  219.     double rSSum = 0, qSSum = 0;
  220.     int repeats=100;
  221.  
  222.     clock_t start, end;
  223.  
  224.     for(int count=0; count<repeats; count++){
  225.         srand(time(NULL));
  226.         for(int i=0; i<length; i++){
  227.             arr[i] = rand();
  228.             //printf("%d ", arr[i]);
  229.         }
  230.         //printf("\n");
  231.         omp_set_num_threads(6);
  232.         start = clock();
  233.         radixSort(arr, length, getMax(arr, length), 6);
  234.         end = clock();
  235.         rSSum += (double) ((double)(end - start) / CLOCKS_PER_SEC);
  236.         //printf("%f\n", (double) ((double)(end - start) / CLOCKS_PER_SEC) );
  237.         checkAscending(arr, length);
  238.  
  239.         srand(time(NULL));
  240.         for(int i=0; i<length; i++){
  241.             arr[i] = rand();
  242.             //printf("%d ", arr[i]);
  243.         }
  244.  
  245.         start = clock();
  246.         qsort(arr, length, sizeof(int), compFunc);
  247.         end = clock();
  248.         qSSum += (double) ((double)(end - start) / CLOCKS_PER_SEC);
  249.         //printf("%f\n", (double) ((double)(end - start) / CLOCKS_PER_SEC) );
  250.         checkAscending(arr, length);
  251.     }
  252.     printf("Radix Average: %f \nqSort Average: %f \nqSort / Radix: %f \n", rSSum / repeats, qSSum / repeats, qSSum/rSSum);
  253.  
  254.  
  255.  
  256.     //printArr(arr, length);
  257.  
  258.  
  259. }
Advertisement
RAW Paste Data Copied
Advertisement