Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: bsearch in C

Reply
Thread Tools

Re: bsearch in C

 
 
Eric Sosman
Guest
Posts: n/a
 
      08-07-2003
Edward A Thompson wrote:
>
> Is there any common knowledge out there about what the threshold for
> bsearch (stdlib.h) performing better than a sequential search of an
> array? If I have an array of 600 structure vs 6000?


Too many unknowns: The nature and quality of the bsearch()
implementation, the complexity of the comparison function, the
comparative overhead of actually calling a function for each
comparison as opposed to performing it in-line inside the search
loop, the behavior of your virtual memory system, the phase of
the moon, ...

If the bsearch() implementation uses a binary search (not
required by the Standard, but probably pretty common), an
average successful search will take about lg(N)-1 probes to
find a key in an N-element array, and an average unsuccessful
search will take about lg(N) probes to establish that the key
isn't there. For 600 elements that's nine-and-change probes;
for 6000 it's twelve-and-change.

As suggested above, you can't really predict the crossover
point given such meager data. There's more than one way to
search sequentially -- Knuth devotes more than twelve pages
of TAOCP to the topic -- so it's hard to predict what sort of
performance "a sequential search" will give. Still, a few
*very* *general* *and* *approximate* ideas:

- A sequential search in a haphazardly arranged array
will probe about N/2 elements for a successful search,
or all N elements in an unsuccessful search. This
will be greater than lg(N) for all except the smallest
arrays -- but the probes themselves may be a good deal
simpler, and you needn't incur the cost of sorting the
array beforehand.

- If you sort the array, a successful sequential search
still averages N/2 probes but an unsuccessful search
drops from N-for-sure to N/2-on-the-average (with some
assumptions about the distribution of the keys).

- Self-organizing ("move to front" or "move toward front")
arrays can exploit non-uniform search patterns in ways
binary search cannot match.

All very nice in theory, but not too useful in practice. The
first -- the VERY FIRST -- thing you should do is measure the
performance of your program and decide whether the searching
contributes an unacceptable amount of running time. If it does,
consider ways to reduce that time -- but if it doesn't, all the
time you spend optimizing it is time wasted. Utterly wasted.

Finally, a personal opinion (with which others may disagree,
perhaps vehemently): don't use bsearch(). The binary search
is such a simple algorithm to implement that you might as well
just do it in-line where it's needed, and not pay performance
penalties for generality you don't need. (By the way, you may
be interested in an invention of mine: I'm calling it the "wheel.")

--
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      08-08-2003
Ben Pfaff wrote:
>
> Eric Sosman <(E-Mail Removed)> writes:
>
> > Finally, a personal opinion (with which others may disagree,
> > perhaps vehemently): don't use bsearch(). The binary search
> > is such a simple algorithm to implement that you might as well
> > just do it in-line where it's needed, and not pay performance
> > penalties for generality you don't need. (By the way, you may
> > be interested in an invention of mine: I'm calling it the "wheel.")

>
> bsearch() is most useful when you've already called qsort() on
> the array, because you already have the comparison function
> handy.


... except that the comparison functions for qsort() and
bsearch() receive different arguments. The qsort() comparator
gets pointers to two array elements, while the bsearch()
comparator gets one pointer to an array element and one
pointer to a "key." Unless the key happens to be the first
(or only) thing in the array element, you can't use the
same comparator for both qsort() and bsearch().

--
(E-Mail Removed)
 
Reply With Quote
 
 
 
 
Arthur J. O'Dwyer
Guest
Posts: n/a
 
      08-08-2003

On Fri, 8 Aug 2003, Eric Sosman wrote:
>
> Ben Pfaff wrote:
> > Eric Sosman <(E-Mail Removed)> writes:
> >
> > > Finally, a personal opinion (with which others may disagree,
> > > perhaps vehemently): don't use bsearch(). The binary search
> > > is such a simple algorithm to implement that you might as well
> > > just do it in-line where it's needed, and not pay performance
> > > penalties for generality you don't need. (By the way, you may
> > > be interested in an invention of mine: I'm calling it the "wheel.")

> >
> > bsearch() is most useful when you've already called qsort() on
> > the array, because you already have the comparison function
> > handy.

>
> ... except that the comparison functions for qsort() and
> bsearch() receive different arguments. The qsort() comparator
> gets pointers to two array elements, while the bsearch()
> comparator gets one pointer to an array element and one
> pointer to a "key"


... which is allowed to be of the same type as the array elements.

> Unless the key happens to be the first
> (or only) thing in the array element, you can't use the
> same comparator for both qsort() and bsearch().


Of course you can!
For example,

int intcmp(const void *p, const void *q)
{
int i = *(const int*)p, j = *(const int*)q;
return (i < j)? -1: (i != j);
}

Another brain fart?

-Arthur
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      08-08-2003
"Arthur J. O'Dwyer" wrote:
>
> On Fri, 8 Aug 2003, Eric Sosman wrote:
> >
> > ... except that the comparison functions for qsort() and
> > bsearch() receive different arguments. The qsort() comparator
> > gets pointers to two array elements, while the bsearch()
> > comparator gets one pointer to an array element and one
> > pointer to a "key"

>
> ... which is allowed to be of the same type as the array elements.


.... which is exactly what I wrote in the very first phrase of
the very next sentence.

> > Unless the key happens to be the first
> > (or only) thing in the array element, you can't use the
> > same comparator for both qsort() and bsearch().

>
> Of course you can!
> For example,
>
> int intcmp(const void *p, const void *q)
> {
> int i = *(const int*)p, j = *(const int*)q;
> return (i < j)? -1: (i != j);
> }
>
> Another brain fart?


My brain has been known to emit noxious fumes from time
to time, but I think this notion is fully digested. Example:

struct item {
double trouble;
char *coal;
...
int key;
...
float ation;
void *main;
};

The challenge: use qsort() to sort an array of these
things on their `key' elements, and then use bsearch() with
the same comparison functions to search the sorted array.
This won't work:

int key = 42;
bsearch (&key, array, count, sizeof array[0],
same_comparator_as_qsort);

It *is* possible to re-use the comparator, at the cost
of manufacturing a fake node simply to carry the key data:

struct item fake;
fake.key = 42;
bsearch (&fake, ...);

With a small struct like the one shown, this isn't bad --
but with larger structs it can become inconvenient.

--
(E-Mail Removed)
 
Reply With Quote
 
Al Bowers
Guest
Posts: n/a
 
      08-08-2003


Eric Sosman wrote:
> Ben Pfaff wrote:
>
>>Eric Sosman <(E-Mail Removed)> writes:
>>
>>
>>> Finally, a personal opinion (with which others may disagree,
>>>perhaps vehemently): don't use bsearch(). The binary search
>>>is such a simple algorithm to implement that you might as well
>>>just do it in-line where it's needed, and not pay performance
>>>penalties for generality you don't need. (By the way, you may
>>>be interested in an invention of mine: I'm calling it the "wheel.")

>>
>>bsearch() is most useful when you've already called qsort() on
>>the array, because you already have the comparison function
>>handy.

>
>
> ... except that the comparison functions for qsort() and
> bsearch() receive different arguments. The qsort() comparator
> gets pointers to two array elements, while the bsearch()
> comparator gets one pointer to an array element and one
> pointer to a "key." Unless the key happens to be the first
> (or only) thing in the array element, you can't use the
> same comparator for both qsort() and bsearch().
>

Nope; function qsort and bsearch can use the same comparator function.

#include <stdio.h>
#include <stdlib.h>

typedef INTARRAY[6];

void PrintINTARRAY(INTARRAY a);
int cmp(const void *p, const void *q);

int main(void)
{
INTARRAY iarr = { 6,4,9,3,1,10};
int key = 9;

puts("Unsorted");
PrintINTARRAY(iarr);
qsort(iarr,6,sizeof(int),cmp);
puts("\nSorted");
PrintINTARRAY(iarr);
puts("\nLooking for integer 9 in array.....");
if(bsearch(&key,iarr,6,sizeof(int),cmp))
puts("\nThe integer 9 was found in the array");
else puts("\nThe integer 9 was not found in the array");
return 0;
}

void PrintINTARRAY(INTARRAY a)
{
int i, nelements = sizeof(INTARRAY)/sizeof(a);

for(i = 0;i < nelements;i++)
printf("%d\t",a[i]);
putchar('\n');
return;
}

int cmp(const void *v1, const void *v2)
{
const int *i1 = v1, *i2 = v2;
return (*i1 < *i2)? -1: (*i1 != *i2);
}

--
Al Bowers
Tampa, Fl USA
mailto: (E-Mail Removed) (remove the x)
http://www.geocities.com/abowers822/

 
Reply With Quote
 
lawrence.jones@eds.com
Guest
Posts: n/a
 
      08-08-2003
Eric Sosman <(E-Mail Removed)> wrote:
>
> The qsort() comparator
> gets pointers to two array elements, while the bsearch()
> comparator gets one pointer to an array element and one
> pointer to a "key." Unless the key happens to be the first
> (or only) thing in the array element, you can't use the
> same comparator for both qsort() and bsearch().


Not so, you just need to ensure that your key has the same type as your
array elements. In fact, most pre-ANSI specs for bsearch() neglected to
specify which comparison function parameter was the key, which pretty
much forced you to do the same thing.

-Larry Jones

Why is it you always rip your pants on the day everyone has to
demonstrate a math problem at the chalkboard? -- Calvin
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      08-08-2003
(E-Mail Removed) wrote:
>
> Eric Sosman <(E-Mail Removed)> wrote:
> >
> > The qsort() comparator
> > gets pointers to two array elements, while the bsearch()
> > comparator gets one pointer to an array element and one
> > pointer to a "key." Unless the key happens to be the first
> > (or only) thing in the array element, you can't use the
> > same comparator for both qsort() and bsearch().

>
> Not so, you just need to ensure that your key has the same type as your
> array elements. In fact, most pre-ANSI specs for bsearch() neglected to
> specify which comparison function parameter was the key, which pretty
> much forced you to do the same thing.


This is becoming spooky. Three count them three
respondents (so far) have offered counterexamples to my
contention that you can't, in general, use the same
comparator for qsort() and bsearch():

- Arthur J. O'Dwyer shows a comparison function
that works on a pair of `int' objects,

- Al Bowers demonstrates a complete program to
qsort() and bsearch() an array of `int',

- Larry Jones points out that everything works if
the key and the array elements have the same
type.

The spooky part is that all three of these folks are
right, as far as they go -- but that even though all three
quoted the sentence beginning with "Unless," not one of
them seems to have read it.

YES, people! There ARE cases where you CAN use the
same comparator for both qsort() and bsearch()! I admit
it freely! You've got me! It's a fair cop.

... but it's a SPECIAL CASE, not a general property
of the qsort() and bsearch() functions. It is SOMETIMES
true that you can use the same comparison function with
both qsort() and bsearch(), but NOT ALWAYS true.

(By the way, I've made an improvement to my new
"wheel" invention: the latest model is triangular instead
of square, eliminating twenty-five percent of the jolts.)

--
(E-Mail Removed)
 
Reply With Quote
 
lawrence.jones@eds.com
Guest
Posts: n/a
 
      08-09-2003
Rich Grise <(E-Mail Removed)> wrote:
>
> The challenge: use qsort() to sort an array of these
> things on their `key' elements, and then use bsearch() with
> the same comparison functions to search the sorted array.
> This won't work:
>
> int key = 42;
> bsearch (&key, array, count, sizeof array[0],
> same_comparator_as_qsort);


No, but this will:

struct item keyitem;
keyitem.key = 42;
bsearch(&keyitem, array, count, sizeof array[0],
same_comparator_as_qsort);

-Larry Jones

I never get to do anything fun. -- Calvin
 
Reply With Quote
 
Ben Pfaff
Guest
Posts: n/a
 
      08-11-2003
Eric Sosman <(E-Mail Removed)> writes:

> The challenge: use qsort() to sort an array of these
> things on their `key' elements, and then use bsearch() with
> the same comparison functions to search the sorted array.
> This won't work:
>
> int key = 42;
> bsearch (&key, array, count, sizeof array[0],
> same_comparator_as_qsort);
>
> It *is* possible to re-use the comparator, at the cost
> of manufacturing a fake node simply to carry the key data:
>
> struct item fake;
> fake.key = 42;
> bsearch (&fake, ...);


That's the way I've always used it, and that's the way I've
always assumed it was meant to be used.
 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      08-12-2003
Ben Pfaff wrote:

> Eric Sosman <(E-Mail Removed)> writes:
>
>> It *is* possible to re-use the comparator, at the cost
>> of manufacturing a fake node simply to carry the key data:
>>
>> struct item fake;
>> fake.key = 42;
>> bsearch (&fake, ...);

>
> That's the way I've always used it, and that's the way I've
> always assumed it was meant to be used.


Curiously, I seem to recall that it isn't the way I started off using it. At
some point, I discovered that this was (what I now think of as) The Right
Way To Use bsearch, but I seem to recall that as a newbie I used to just
pass the key field itself into bsearch and hope like hell that it would
work. (Often, amazingly, it did.)

--
Richard Heathfield : (E-Mail Removed)
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Struggling with bsearch - on a struct! Angus Comber C Programming 4 02-06-2004 04:49 AM
bsearch script segfault Ramprasad A Padmanabhan C Programming 11 12-05-2003 01:00 PM
a small bsearch example Ramprasad A Padmanabhan C Programming 1 10-28-2003 09:37 AM
Re: bsearch in C Richard Heathfield C Programming 0 08-07-2003 09:12 PM
Re: bsearch in C Artie Gold C Programming 0 08-07-2003 09:06 PM



Advertisments