From e37652d0419529aa86d886ea6cc2d9c06eac6186 Mon Sep 17 00:00:00 2001 From: David Monniaux Date: Sat, 6 Apr 2019 10:09:36 +0200 Subject: use of ternary operators --- test/monniaux/binary_search/binary_search.c | 31 ++++++++++++++++++++++++++--- 1 file changed, 28 insertions(+), 3 deletions(-) diff --git a/test/monniaux/binary_search/binary_search.c b/test/monniaux/binary_search/binary_search.c index c8131c38..73e77a6c 100644 --- a/test/monniaux/binary_search/binary_search.c +++ b/test/monniaux/binary_search/binary_search.c @@ -2,10 +2,12 @@ #include #include #include "../clock.h" +#include "../ternary.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) { @@ -23,6 +25,19 @@ int my_bsearch (data *a, index n, data x) { 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; + if (a[k] == x) { + return k; + } + i = TERNARY32(a[k] < x, k+1, i); + j = TERNARY32(a[k] > x, k-1, j); + } + return -1; +} + void random_ascending_fill(data *a, index n) { unsigned r = 41; data v = 0; @@ -36,17 +51,27 @@ void random_ascending_fill(data *a, index n) { int main () { index n=5000; + data v=1502; data *buf=malloc(n*sizeof(data)); - cycle_t timestamp1 = get_current_cycle(); + cycle_t timestamp0 = get_current_cycle(); random_ascending_fill(buf, n); + timestamp0 = get_current_cycle()-timestamp0; + + cycle_t timestamp1 = get_current_cycle(); + index pos1 = my_bsearch(buf, n, v); timestamp1 = get_current_cycle()-timestamp1; cycle_t timestamp2 = get_current_cycle(); - index pos = my_bsearch(buf, n, 1502); + index pos2 = my_bsearch(buf, n, v); timestamp2 = get_current_cycle()-timestamp2; - printf("position: %d\nrandom fill cycles: %" PRIu64 "\nsearch cycles: %" PRIu64 "\n", pos, timestamp1, timestamp2); + printf("position1: %d\n" + "position2: %d\n" + "random fill cycles: %" PRIu64 "\n" + "search1 cycles: %" PRIu64 "\n" + "search2 cycles: %" PRIu64 "\n", + pos1, pos2, timestamp0, timestamp1, timestamp2); free(buf); } -- cgit