GNU libavl 2.0.1

www.delorie.com/gnu/docs/avl/libavl_279.html

search

	Buy GNU books!

GNU libavl 2.0.1

[ < ]

[ > ]

[ << ]

[ Up ]

[ >> ]

[Top]

[Contents]

[Index]

[ ? ]

Chapter 3

Section 3.1

1. The following program can be improved in many ways. However, we will implement a much better testing framework later, so this is fine for now.

<@xref{\NODE\, , License.>,1} #include <stdio.h> #define @cindex MAX_INPUT macro MAX_INPUT 1024 <@xref{\NODE\, , Sequentially search an array of int.>s,16} int
main (void)
{ int array[MAX_INPUT]; int n, i; for (n = 0; n < MAX_INPUT; n++) if (scanf ("%d", &array[n]) != 1) break; for (i = 0; i < n; i++)
{ int result = seq_search (array, n, array[i]); if (result != i) printf ("seq_search()returned%dlookingfor%d-expected%d\n", result, array[i], i); } return 0; }

Section 3.4

1. Some types don't have a largest possible value; e.g., arbitrary-length strings.

Section 3.5

1. Knuth's name for this procedure is "uniform binary search." The code below is an almost-literal implementation of his Algorithm U. The fact that Knuth's arrays are 1-based, but C arrays are 0-based, accounts for most of the differences.

The code below uses for (;;) to assemble an "infinite" loop, a common C idiom.

/* Returns the offset within array[] of an element equal to key,
or -1 if key is not in array[]. array[] must be an array of n ints sorted in ascending order,
with array[-1] modifiable. */ int
uniform_binary_search (int array[], int n, int key)
{ int i = (n + 1) / 2 - 1; int m = n / 2; array[-1] = INT_MIN; for (;;)
{ if (key < array[i])
{ if (m == 0) return -1; i -= (m + 1) / 2; m /= 2; } else if (key > array[i])
{ if (m == 0) return -1; i += (m + 1) / 2; m /= 2; } else
return i >= 0 ? i : -1; } }
This code is included in @refalso{600

See also: [ Knuth 1998b], section 6.2.1, Algorithm U.

2a. This actually uses blp_bsearch(), implemented in part (b) below, in order to allow that function to be tested. You can replace the reference to blp_bsearch() by bsearch() without problem.

<@xref{\NODE\, , blp's implementation of bsearch.>(),598} /* Compares the ints pointed to by pa and pb and returns positive if *pa > *pb, negative if *pa < *pb, or zero if *pa == *pb. */ static int
compare_ints (const void *pa, const void *pb)
{ const int *a = pa; const int *b = pb; if (*a > *b)
return 1; else if (*a < *b)
return -1; else
return 0; } /* Returns the offset within array[] of an element equal to key,
or -1 if key is not in array[]. array[] must be an array of n ints sorted in ascending order. */ static int
binary_search_bsearch (int array[], int n, int key)
{ int *p = blp_bsearch (&key, array, n, sizeof *array, compare_ints); return p != NULL ? p - array : -1; }
This code is included in @refalso{600

2b. This function is named using the author of this book's initials. Note that the implementation below assumes that count, a size_t, won't exceed the range of an int. Some systems provide a type called ssize_t for this purpose, but we won't assume that here. (long is perhaps a better choice than int.)

/* Plug-compatible with standard C library bsearch(). */ static void *
blp_bsearch (const void *key, const void *array, size_t count, size_t size, int (*compare) (const void *, const void *))
{ int min = 0; int max = count; while (max >= min)
{ int i = (min + max) / 2; void *item = ((char *) array) + size * i; int cmp = compare (key, item); if (cmp < 0)
max = i - 1; else if (cmp > 0)
min = i + 1; else
return item; } return NULL; }
This code is included in @refalso{597

3. Here's an outline of the entire program:

<@xref{\NODE\, , License.>,1} #include <limits.h> #include <stdio.h> #include <stdlib.h> #include <time.h> <@xref{\NODE\, , Search functions.>,600} <@xref{\NODE\, , Array of search functions.>,601} <@xref{\NODE\, , Timer functions.>,604} <@xref{\NODE\, , Search test functions.>,606} <@xref{\NODE\, , Search test main program.>,609}

We need to include all the search functions we're going to use:

<@xref{\NODE\, , Sequentially search an array of int.>s,16} <@xref{\NODE\, , Sequentially search an array of int.>s using a sentinel,17} <@xref{\NODE\, , Sequentially search a sorted array of int.>s,18} <@xref{\NODE\, , Sequentially search a sorted array of int.>s using a sentinel,19} <@xref{\NODE\, , Sequentially search a sorted array of int.>s using a sentinel (2),20} <@xref{\NODE\, , Binary search of ordered array.>,21} <@xref{\NODE\, , Uniform binary search of ordered array.>,596} <@xref{\NODE\, , Binary search using bsearch.>(),597} <@xref{\NODE\, , Cheating search.>,603}
This code is included in @refalso{599

We need to make a list of the search functions. We start by defining the array's element type:

/* Description of a search function. */ struct search_func
{ const char *name; int (*search) (int array[], int n, int key); };
See also @refalso{602 This code is included in @refalso{599

Then we define the list as an array:

/* Array of all the search functions we know. */ struct search_func search_func_tab[] =
{ {"seq_search()", seq_search}, {"seq_sentinel_search()", seq_sentinel_search}, {"seq_sorted_search()", seq_sorted_search}, {"seq_sorted_sentinel_search()", seq_sorted_sentinel_search}, {"seq_sorted_sentinel_search_2()", seq_sorted_sentinel_search_2}, {"binary_search()", binary_search}, {"uniform_binary_search()", uniform_binary_search}, {"binary_search_bsearch()", binary_search_bsearch}, {"cheat_search()", cheat_search}, }; /* Number of search functions. */ const size_t n_search_func = sizeof search_func_tab / sizeof *search_func_tab;

We've added previously unseen function cheat_search() to the array. This is a function that "cheats" on the search because it knows that we are only going to search in a array such that array[i] == i. The purpose of cheat_search() is to allow us to find out how much of the search time is overhead imposed by the framework and the function calls and how much is actual search time. Here's cheat_search():

/* Cheating search function that knows that array[i] == i. n must be the array size and key the item to search for. array[] is not used. Returns the index in array[] where key is found,
or -1 if key is not in array[]. */ int
cheat_search (int array[], int n, int key)
{ return key >= 0 && key < n ? key : -1; }
This code is included in @refalso{600

We're going to need some functions for timing operations. First, a function to "start" a timer:

/* ``Starts'' a timer by recording the current time in *t. */ static void
start_timer (clock_t *t)
{ clock_t now = clock (); while (now == clock ()) /* Do nothing. */; *t = clock (); }
See also @refalso{605 This code is included in @refalso{599

Function start_timer() waits for the value returned by clock() to change before it records the value. On systems with a slow timer (such as PCs running MS-DOS, where the clock ticks only 18.2 times per second), this gives more stable timing results because it means that timing always starts near the beginning of a clock tick.

We also need a function to "stop" the timer and report the results:

/* Prints the elapsed time since start, set by start_timer(). */ static void
stop_timer (clock_t start)
{ clock_t end = clock (); printf ("%.2fseconds\n", ((double) (end - start)) / CLOCKS_PER_SEC); }

The value reported by clock() can "wrap around" to zero from a large value. stop_timer() does not allow for this possibility.

We will write three tests for the search functions. The first of these just checks that the search function works properly:

/* Tests that f->search returns expect when called to search for
key within array[], which has n elements such that array[i] == i. */ static void
test_search_func_at (struct search_func *f, int array[], int n, int key, int expect)
{ int result = f->search (array, n, key); if (result != expect) printf ("%sreturned%dlookingfor%d-expected%d\n", f->name, result, key, expect); } /* Tests searches for each element in array[] having n elements such that
array[i] == i, and some unsuccessful searches too, all using function f->search. */ static void
test_search_func (struct search_func *f, int array[], int n)
{ static const int shouldnt_find[] = {INT_MIN, -20, -1, INT_MAX}; int i; printf ("Testingintegrityof%s...", f->name); fflush (stdout); /* Verify that the function finds values that it should. */ for (i = 0; i < n; i++) test_search_func_at (f, array, n, i, i); /* Verify that the function doesn't find values it shouldn't. */ for (i = 0; i < (int) (sizeof shouldnt_find / sizeof *shouldnt_find); i++) test_search_func_at (f, array, n, shouldnt_find[i], -1); printf ("done\n"); }
See also @refalso{607 This code is included in @refalso{599

The second test function finds the time required for searching for elements in the array:

/* Times a search for each element in array[] having n elements such that array[i] == i, repeated n_iter times, using function f->search. */ static void
time_successful_search (struct search_func *f, int array[], int n, int n_iter)
{ clock_t timer; printf ("Timing%dsetsofsuccessfulsearches...", n_iter); fflush (stdout); start_timer (&timer); while (n_iter-- > 0)
{ int i; for (i = 0; i < n; i++) f->search (array, n, i); } stop_timer (timer); }

The last test function finds the time required for searching for values that don't appear in the array:

/* Times n search for elements not in array[] having n elements such that array[i] == i, repeated n_iter times, using function f->search. */ static void
time_unsuccessful_search (struct search_func *f, int array[],
int n, int n_iter)
{ clock_t timer; printf ("Timing%dsetsofunsuccessfulsearches...", n_iter); fflush (stdout); start_timer (&timer); while (n_iter-- > 0)
{ int i; for (i = 0; i < n; i++) f->search (array, n, -i); } stop_timer (timer); }

Here's the main program:

<@xref{\NODE\, , Usage printer for search test program.>,615} <@xref{\NODE\, , String to integer function stoi.>(),611} int
main (int argc, char *argv[])
{ struct search_func *f; /* Search function. */ int *array, n; /* Array and its size. */ int n_iter; /* Number of iterations. */ <@xref{\NODE\, , Parse search test command line.>,610} <@xref{\NODE\, , Initialize search test array.>,612} <@xref{\NODE\, , Run search tests.>,613} <@xref{\NODE\, , Clean up after search tests.>,614} return 0; }
This code is included in @refalso{599

if (argc != 4)
usage (); { long algorithm = stoi (argv[1]) - 1; if (algorithm < 0 || algorithm > (long) n_search_func)
usage (); f = &search_func_tab[algorithm]; } n = stoi (argv[2]); n_iter = stoi (argv[3]); if (n < 1 || n_iter < 1)
usage ();
This code is included in @refalso{609

/* s should point to a decimal representation of an integer. Returns the value of s, if successful, or 0 on failure. */ static int
stoi (const char *s)
{ long x = strtol (s, NULL, 10); return x >= INT_MIN && x <= INT_MAX ? x : 0; }
This code is included in @refalso{609

When reading the code below, keep in mind that some of our algorithms use a sentinel at the end and some use a sentinel at the beginning, so we allocate two extra integers and take the middle part.

array = malloc ((n + 2) * sizeof *array); if (array == NULL)
{ fprintf (stderr, "outofmemory\n"); exit (EXIT_FAILURE); } array++; { int i; for (i = 0; i < n; i++) array[i] = i; }
This code is included in @refalso{609

test_search_func (f, array, n); time_successful_search (f, array, n, n_iter); time_unsuccessful_search (f, array, n, n_iter);
This code is included in @refalso{609

free (array - 1);
This code is included in @refalso{609

/* Prints a message to the console explaining how to use this program. */ static void
usage (void)
{ size_t i; fputs ("usage:srch-test<array-size><n-iterations>\n" "whereisoneofthefollowing:\n", stdout); for (i = 0; i < n_search_func; i++) printf ("%ufor%s\n", (unsigned) i + 1, search_func_tab[i].name); fputs ("<array-size>isthesizeofthearraytosearch,and\n" "<n-iterations>isthenumberoftimestoiterate.\n", stdout); exit (EXIT_FAILURE); }
This code is included in @refalso{609

4. Here are the results on the author's computer, a Pentium II at 233 MHz, using GNU C 2.95.2, for 1024 iterations using arrays of size 1024 with no optimization. All values are given in seconds rounded to tenths.

Function Successful searches Unsuccessful searches

seq_search() 18.4 36.3

seq_sentinel_search() 16.5 32.8

seq_sorted_search() 18.6 0.1

seq_sorted_sentinel_search() 16.4 0.2

seq_sorted_sentinel_search_2() 16.6 0.2

binary_search() 1.3 1.2

uniform_binary_search() 1.1 1.1

binary_search_bsearch() 2.6 2.4

cheat_search() 0.1 0.1

Results of similar tests using full optimization were as follows:

Function Successful searches Unsuccessful searches

seq_search() 6.3 12.4

seq_sentinel_search() 4.8 9.4

seq_sorted_search() 9.3 0.1

seq_sorted_sentinel_search() 4.8 0.2

seq_sorted_sentinel_search_2() 4.8 0.2

binary_search() 0.7 0.5

uniform_binary_search() 0.7 0.6

binary_search_bsearch() 1.5 1.2

cheat_search() 0.1 0.1

Observations:

In general, the times above are about what we might expect them to be: they decrease as we go down the table.
Within sequential searches, the sentinel-based searches have better search times than non-sentinel searches, and other search characteristics (whether the array was sorted, for instance) had little impact on performance.
Unsuccessful searches were very fast for sorted sequential searches, but the particular test set used always allowed such searches to terminate after a single comparison. For other test sets one might expect these numbers to be similar to those for unordered sequential search.
Either of the first two forms of binary search had the best overall performance. They also have the best performance for successful searches and might be expected to have the best performance for unsuccessful searches in other test sets, for the reason given before.
Binary search using the general interface bsearch() was significantly slower than either of the other binary searches, probably because of the cost of the extra function calls. Items that are more expensive to compare (for instance, long text strings) might be expected to show less of a penalty.

Here are the results on the same machine for 1,048,576 iterations on arrays of size 8 with full optimization:

Function Successful searches Unsuccessful searches

seq_search() 1.7 2.0

seq_sentinel_search() 1.7 2.0

seq_sorted_search() 2.0 1.1

seq_sorted_sentinel_search() 1.9 1.1

seq_sorted_sentinel_search_2() 1.8 1.2

binary_search() 2.5 1.9

uniform_binary_search() 2.4 2.3

binary_search_bsearch() 4.5 3.9

cheat_search() 0.7 0.7

For arrays this small, simple algorithms are the clear winners. The additional complications of binary search make it slower. Similar patterns can be expected on most architectures, although the "break even" array size where binary search and sequential search are equally fast can be expected to differ.

Section 3.6

1. Here is one easy way to do it:

/* Initializes larger and smaller within range min...max of
array[], which has n real elements plus a (n + 1)th sentinel element. */ int
init_binary_tree_array (struct binary_tree_entry array[], int n,
int min, int max)
{ if (min <= max)
{ /* The `+ 1' is necessary because the tree root must be at n / 2, and on the first call we have min == 0 and max == n - 1. */ int i = (min + max + 1) / 2; array[i].larger = init_binary_tree_array (array, n, i + 1, max); array[i].smaller = init_binary_tree_array (array, n, min, i - 1); return i; } else
return n; }
This code is included in @refalso{617

2.

<@xref{\NODE\, , License.>,1} #include <limits.h> #include <stdio.h> #include <stdlib.h> <@xref{\NODE\, , Binary search tree entry.>,22} <@xref{\NODE\, , Search of binary search tree stored as array.>,23} <@xref{\NODE\, , Initialize smaller.> and larger within binary search tree,616} <@xref{\NODE\, , Show `bin-ary-test'.> usage message,619} <@xref{\NODE\, , String to integer function stoi.>(),611} <@xref{\NODE\, , Main program to test binary_search_tree_array.>(),618}

int
main (int argc, char *argv[])
{ struct binary_tree_entry *array; int n, i; /* Parse command line. */ if (argc != 2)
usage (); n = stoi (argv[1]); if (n < 1)
usage (); /* Allocate memory. */ array = malloc ((n + 1) * sizeof *array); if (array == NULL)
{ fprintf (stderr, "outofmemory\n"); return EXIT_FAILURE; } /* Initialize array. */ for (i = 0; i < n; i++) array[i].value = i; init_binary_tree_array (array, n, 0, n - 1); /* Test successful and unsuccessful searches. */ for (i = -1; i < n; i++)
{ int result = binary_search_tree_array (array, n, i); if (result != i) printf ("Searchingfor%d:expected%d,butreceived%d\n", i, i, result); } /* Clean up. */ free (array); return EXIT_SUCCESS; }
This code is included in @refalso{617

/* Print a helpful usage message and abort execution. */ static void
usage (void)
{ fputs ("Usage:bin-ary-test\n" "whereisthesizeofthearraytotest.\n", stdout); exit (EXIT_FAILURE); }
This code is included in @refalso{617