diff options
Diffstat (limited to 'test/monniaux/binary_search/binary_search.c')
-rw-r--r-- | test/monniaux/binary_search/binary_search.c | 130 |
1 files changed, 130 insertions, 0 deletions
diff --git a/test/monniaux/binary_search/binary_search.c b/test/monniaux/binary_search/binary_search.c new file mode 100644 index 00000000..f16d15b8 --- /dev/null +++ b/test/monniaux/binary_search/binary_search.c @@ -0,0 +1,130 @@ +#include <stdio.h> +#include <stdlib.h> +#include <inttypes.h> +#include "../clock.h" + +typedef int data; +typedef unsigned index; + +/* from Rosetta code */ +int my_bsearch (data *a, index n, data x) { + index i = 0, j = n - 1; + while (i <= j) { + index k = (i + j) / 2; + if (a[k] == x) { + return k; + } + else if (a[k] < x) { + i = k + 1; + } + else { + j = k - 1; + } + } + return -1; +} + +int my_bsearch2 (data *a, index n, data x) { + index i = 0, j = n - 1; + while (i <= j) { + index k = (i + j) / 2; + index kp1 = k+1, km1 = k-1; + data ak = a[k]; + i = ak < x ? kp1 : i; + j = ak > x ? km1 : j; + if (ak == x) { + return k; + } + } + return -1; +} + +int my_bsearch3 (data *a, index n, data x) { + index i = 0, j = n - 1; + while (i <= j) { + index k = (i + j) / 2; + index kp1 = k+1, km1 = k-1; + data ak = a[k]; + _Bool lt = ak < x, gt = ak > x; + i = lt ? kp1 : i; + j = gt ? km1 : j; + if (ak == x) { + return k; + } + } + return -1; +} + +int my_bsearch4 (data *a, index n, data x) { + index i = 0, j = n - 1, k; + k = (i + j) / 2; + while (i <= j) { + index kp1 = k+1, km1 = k-1; + data ak = a[k]; + _Bool lt = ak < x, gt = ak > x; + i = lt ? kp1 : i; + j = gt ? km1 : j; + if (ak == x) { + goto end; + } + k = (i + j) / 2; + } + k=-1; + end: + return k; +} + +void random_ascending_fill(data *a, index n) { + unsigned r = 41; + data v = 0; + for(index i=0; i<n; i++) { + a[i] = v; + v++; + v = (r & 0x40000000) ? (v+1) : v; + r = r * 97 + 5; + } +} + +int main () { + index n=25000; + data v=1502; + data *buf=malloc(n*sizeof(data)); + + cycle_t timestamp0 = get_current_cycle(); + random_ascending_fill(buf, n); + timestamp0 = get_current_cycle()-timestamp0; + + my_bsearch(buf, n, v); + cycle_t timestamp1 = get_current_cycle(); + index pos1 = my_bsearch(buf, n, v); + timestamp1 = get_current_cycle()-timestamp1; + + my_bsearch2(buf, n, v); + cycle_t timestamp2 = get_current_cycle(); + index pos2 = my_bsearch2(buf, n, v); + timestamp2 = get_current_cycle()-timestamp2; + + my_bsearch3(buf, n, v); + cycle_t timestamp3 = get_current_cycle(); + index pos3 = my_bsearch3(buf, n, v); + timestamp3 = get_current_cycle()-timestamp3; + + my_bsearch4(buf, n, v); + cycle_t timestamp4 = get_current_cycle(); + index pos4 = my_bsearch4(buf, n, v); + timestamp4 = get_current_cycle()-timestamp4; + + printf("position1: %d\n" + "position2: %d\n" + "position3: %d\n" + "position4: %d\n" + "randomfill cycles: %" PRIu64 "\n" + "search1 cycles: %" PRIu64 "\n" + "search2 cycles: %" PRIu64 "\n" + "search3 cycles: %" PRIu64 "\n" + "search4 cycles: %" PRIu64 "\n", + pos1, pos2, pos3, pos4, + timestamp0, timestamp1, timestamp2, timestamp3, timestamp4); + + free(buf); +} |