fbsdgj.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#ifdef _WIN32
# include <windows.h>
#else
# include <sys/time.h>
# include <sys/resource.h>
#endif

double get_time();
void original_merge_sort(int* list, int len, int* sorted);
void insert_sort(int *list, int len, int *sorted);
void optimized_merge_sort(int* list, int len, int* sorted);
void more_optimized_merge_sort(int *list, int len, int *sorted);
void merge(int* left, int l_len, int* right, int r_len, int* sorted);
void print_arr(int* arr, int l);

double benchmark(void (*baseline)(int *, int, int *), void (*contender)(int *, int, int *))
{ // Returns how many times faster contender is from baseline
  // Uses differential timing: https://youtu.be/vrfYLlR8X8k?t=39m18s

    // Prepare samples
    enum { SAMPLE_SIZE = 100000, N = 10 };
    int *samples[N * 4], *samples_sorted[N * 4];
    for(int i = 0; i < N * 4; ++i)
    {
        samples[i] = malloc(SAMPLE_SIZE * sizeof(int));
        samples_sorted[i] = malloc(SAMPLE_SIZE * sizeof(int));
        for(int j = 0; j < SAMPLE_SIZE; ++j)
            samples[i][j] = rand();
    }

    // Run baseline 2n times
    double time_2a = 0;
    for(int i = 0; i < N * 2; ++i)
    {
        double startTime = get_time();
        baseline(samples[i], SAMPLE_SIZE, samples_sorted[i]);
        time_2a += get_time() - startTime;
    }

    // Run baseline n times and contender n times
    double time_ab = 0;
    for(int i = 0; i < N; ++i)
    {
        double startTime = get_time();
        baseline(samples[2 * N + i], SAMPLE_SIZE, samples_sorted[2 * N + i]);
        time_ab += get_time() - startTime;
    }
    for(int i = 0; i < N; ++i)
    {
        double startTime = get_time();
        contender(samples[3 * N + i], SAMPLE_SIZE, samples_sorted[3 * N + i]);
        time_ab += get_time() - startTime;
    }

    // Calculate relative improvement
    double r = time_2a / (2 * time_ab - time_2a) - 1;

    // Clean up
    for(int i = 0; i < 4 * N; ++i)
    {
        free(samples[i]);
        free(samples_sorted[i]);
    }

    return r;
}

int main() {
    srand(time(NULL));
    printf("optimized_merge_sort is %.2f%% faster than original_merge_sort\n",
        benchmark(original_merge_sort, optimized_merge_sort) * 100);
    printf("more_optimized_merge_sort is %.2f%% faster than original_merge_sort\n",
        benchmark(original_merge_sort, more_optimized_merge_sort) * 100);
}

void original_merge_sort(int* list, int len, int* sorted) {
    // length of 1 is sorted
    if (len == 1) {
        *sorted = *list;
        return;
    }

    // split into two sub lists
    int l_len = len / 2, r_len = (len+1) / 2;
    int left[l_len], right[r_len];
    for (int i=0; i<len; i++) {
        if (i < l_len)
            left[i] = list[i];
        else
            right[i-l_len] = list[i];
    }

    // original_merge_sort left and right lists
    //int *sl, *sr;
    int sl[l_len], sr[r_len];
    original_merge_sort(left, l_len, sl);
    original_merge_sort(right, r_len, sr);

    // merge
    merge(sl, l_len, sr, r_len, sorted);
}

void merge(int* left, int l_len, int* right, int r_len, int* sorted) {
    int i=0, l=0, r=0;
    // populate the buffer
    while (l<l_len && r<r_len)
        sorted[i++] = (left[l] <= right[r]) ? left[l++] : right[r++];

    //handle remaining elements
    while (l<l_len)
        sorted[i++] = left[l++];
    while (r<r_len)
        sorted[i++] = right[r++];
}

void print_arr(int* arr, int l) {
    for (int i=0; i<l; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

void insert_sort(int *list, int len, int *sorted)
{
    memcpy(sorted, list, len * sizeof(int));
    for(int i = 1; i < len; ++i)
    {
        int j = i, key = sorted[j];
        while(key < sorted[j-1] && j > 0)
        {
            sorted[j] = sorted[j-1];
            --j;
        }
        sorted[j] = key;
    }
}

void optimized_merge_sort(int *list, int len, int *sorted)
{
    if (len <= 1) {
        if(len == 1)
            *sorted = *list;
        return;
    }

    // You don't need to split into two lists explicitly,
    // because list is read-only anyway
    int l_len = len / 2, r_len = (len+1) / 2,
        sl[l_len], sr[r_len];
    optimized_merge_sort(list, l_len, sl);
    optimized_merge_sort(list + l_len, r_len, sr);

    merge(sl, l_len, sr, r_len, sorted);
}

void more_optimized_merge_sort(int *list, int len, int *sorted)
{
    if (len <= 1) {
        if(len == 1)
            *sorted = *list;
        return;
    }

    // Use insert sort for sufficiently small lists, because it has better
    // constants. Play around with this number and see how speed changes
    if(len <= 20) {
        insert_sort(list, len, sorted);
        return;
    }

    int l_len = len / 2, r_len = (len+1) / 2,
        sl[l_len], sr[r_len];
    more_optimized_merge_sort(list, l_len, sl);
    more_optimized_merge_sort(list + l_len, r_len, sr);

    merge(sl, l_len, sr, r_len, sorted);
}

double get_time()
{

#ifdef _WIN32

    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart / (double)f.QuadPart;

#else

    struct timeval t;
    gettimeofday(&t, NULL);
    return t.tv_sec + t.tv_usec*1e-6;

#endif

}