Algorithm Alley
by Jon Bentley 


Listing One
/* bsearch.c -- time binary search algorithms for cache effects
    From Dr. Dobb's Journal, April 2000
        Input lines:  algnum n numtests
        Output lines: algnum n numtests scrambled clicks nanosecs_per_elem
        See timedriver for algnum codes
    bsearch gives scrambled tests; bsearch -o gives ordered
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXN 10000000

typedef int DataType;

DataType x[MAXN];
int n;

/* Alg 1: From Programming Pearls, 2nd Ed., Column 8 */
int binarysearch1(DataType t, int lo, int hi)
    /* return least u s.t. x[u] >= t */
{       int l, u, m;
        l = lo - 1;
        u = hi + 1;
        while (l+1 != u) {
                m = (l + u) / 2;
                if (x[m] < t)
                        l = m;
                else
                        u = m;
        }
        return u;
}

/* Algs 2 and 3: Return range of equal values */
typedef struct range {
        int lo, hi;
} Range;
int warmstart = 0;  /* 1 to change start of second binary search */
Range binarysearch2(DataType t, int lo, int hi)
    /* pre: sorted(0, n-1)
           post: bsl = min l s.t. x[l] >= t
                 bsu = max u s.t. x[u] <= t
     */
{       int l, u, m;
        Range answer;
        l = lo - 1;
        u = hi + 1;
        while (l+1 != u) {
                m = (l + u) / 2;
                if (x[m] < t)
                        l = m;
                else
                        u = m;
        }
        answer.lo = u;
        l = lo - 1;  /* cold start */
        if (warmstart)
                l = answer.lo;
        u = hi + 1;
        while (l+1 != u) {
                m = (l + u) / 2;
                if (x[m] <= t)
                        l = m;
                else
                        u = m;
        }
        answer.hi = l;
        return answer;
}
/* Timing */
int p[MAXN];  /* permutation vector */
void scramble(int n)
{       int i, j;
        DataType t;
        for (i = n-1; i > 0; i--) { /* call 15-bit rand twice */
                j = (RAND_MAX*rand() + rand()) % (i + 1);
                t = p[i]; p[i] = p[j]; p[j] = t;
        }
}
#define assert(v) { if ((v) == 0) 
                        printf("  binarysearch bug i=%d n=%d\n", i, n); }
int main(int argc, char *argv[])
{       int i, algnum, numtests, test, start, clicks;
        int pos, b, e, wantscramble;
        Range answer;
        DataType t;
        wantscramble = 1;
        if (argc > 1 && argv[1][0] == '-' && argv[1][1] == 'o') 
                                                   /* "ordered" searches */
                wantscramble = 0;
        while (scanf("%d %d %d", &algnum, &n, &numtests) != EOF) {
                x[0] = 0;
                for (i = 1; i < n; i++)
                        x[i] = x[i-1] + rand() % 2;
                for (i = 0; i < n; i++)
                        p[i] = i;
                if (wantscramble)
                        scramble(n);
                start = clock();
                for (test = 0; test < numtests; test++) {
                        for (i = 0; i < n; i++) {
                                t = x[p[i]];
                                switch (algnum) {
                                case 1:
                                        pos = binarysearch1(t, 0, n-1);
                                        assert(pos == 0 || x[pos-1] < t);
                                        assert(pos == n || x[pos] >= t);
                                        break;
                                case 2:
                                case 3:
                                        warmstart = 0;
                                        if (algnum == 3)
                                                warmstart = 1;
                                        answer = binarysearch2(t, 0, n-1);
                                        b = answer.lo;
                                        e = answer.hi;
                                        assert(b < 0   || x[b]   >= t);
                                        assert(b < 1   || x[b-1] <  t);
                                        assert(e > n-1 || x[e]   <= t);
                                        assert(e > n-2 || x[e+1] >  t);
                                        break;
                                }
                        }
                }
                clicks = clock() - start;
                printf("%d\t%d\t%d\t%d\t%d\t%g\n",
                        algnum, n, numtests, wantscramble, clicks,
                        1e9*clicks/((float) CLOCKS_PER_SEC*n*numtests));
        }
        return 0;
}





1


