Skip to content

Instantly share code, notes, and snippets.

@albertnetymk

albertnetymk/cache.c

Created Oct 22, 2015
Embed
What would you like to do?
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// copied from http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort#C
void insertion_sort (int *a, int n) {
int i, j, t;
for (i = 1; i < n; i++) {
t = a[i];
for (j = i; j > 0 && t < a[j - 1]; j--) {
a[j] = a[j - 1];
}
a[j] = t;
}
}
static void print_arr(int arr[], int l)
{
for (int i = 0; i < l; ++i) {
printf("%d ", arr[i]);
}
puts(".");
}
static const int rows = 1000;
static const int cols = 1000;
// static const int length = 1027*1027;
static const int length = 1027*8;
static int **arrs;
void row_by_row()
{
clock_t start, end;
double elapsed_time;
start = clock();
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
insertion_sort(arrs[rows-i-1], length);
}
}
end = clock();
elapsed_time = (double)(end - start) / (double)CLOCKS_PER_SEC;
printf("row-by-row: %f seconds\n", elapsed_time);
}
void col_by_col()
{
clock_t start, end;
double elapsed_time;
start = clock();
for (int j = 0; j < cols; ++j) {
for (int i = 0; i < rows; ++i) {
insertion_sort(arrs[rows-i-1], length);
}
}
end = clock();
elapsed_time = (double)(end - start) / (double)CLOCKS_PER_SEC;
printf("col-by-col: %f seconds\n", elapsed_time);
}
int main(int argc, char **argv)
{
arrs = malloc(sizeof *arrs * rows);
for (int i = 0; i < rows; ++i) {
arrs[i] = malloc(sizeof *arrs[i] * length);
for (int j = 0; j < length; ++j) {
// descending order; worst case for insertion sort
arrs[i][j] = length - j;
}
}
row_by_row();
// col_by_col();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment