clong@topaz.rutgers.edu (Chris Long) (09/28/89)
I find myself needing a really hot 68000 binary search routine. This routine will be called millions of times, so it should be as efficient as possible. I need it to go through about 10,000 items, each with a size of ~ 10 bytes. Does anyone have something like this already coded? The most helpful response gets a postcard with an incredibly ugly picture of Hill Center, the mathematical and computer sciences building here. -- Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ 08901 (201) 846-5569 "The proofs are so obvious that they can be left to the reader." Lars V. Ahlfors, _Complex Analysis_
dal@syntel.mn.org (Dale Schumacher) (09/28/89)
[clong@topaz.rutgers.edu (Chris Long) writes...] > > I find myself needing a really hot 68000 binary search routine. This > routine will be called millions of times, so it should be as efficient > as possible. I need it to go through about 10,000 items, each with a > size of ~ 10 bytes. Does anyone have something like this already coded? Direct from the dLibs library source archive... here is bsearch()... -----------------------------------8<----------------------------------- #include <stdio.h> int _bsearch; /* index of element found, or where to insert */ char *bsearch(key, base, num, size, cmp) register char *key; /* item to search for */ register char *base; /* base address */ int num; /* number of elements */ register int size; /* element size in bytes */ register int (*cmp)(); /* comparison function */ { register int a, b, c, dir; a = 0; b = num - 1; while(a <= b) { c = (a + b) >> 1; /* == ((a + b) / 2) */ if (dir = (*cmp)((base + (c * size)), key)) { if (dir > 0) b = c - 1; else /* (dir < 0) */ a = c + 1; } else { _bsearch = c; return(base + (c * size)); } } _bsearch = b; return(NULL); } -----------------------------------8<----------------------------------- You will probably want to hard code the comparison function, since I assume this is a special purpose "as fast as possible" application of the more general function. Also, obviously, conversion to hand-optimized 68000 assembly is left as an exercise to the reader. > The most helpful response gets a postcard with an incredibly ugly > picture of Hill Center, the mathematical and computer sciences > building here. Actually, I'd prefer if you just sent me back your optimized assembly code conversion. That way I can re-generalize it (to take a compare function pointer) and include it in the next dLibs release. > Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ 08901 (201) 846-5569 > > "The proofs are so obvious that they can be left to the reader." > Lars V. Ahlfors, _Complex Analysis_ I hope this is want you needed. \\ / Dale Schumacher 399 Beacon Ave. \\ / (alias: Dalnefre') St. Paul, MN 55104-3527 >< ...umn-cs!midgard.mn.org!syntel!dal United States of America / \\ "What is wanted is not the will to believe, but the will to find out, / \\ which is the exact opposite." -Bertrand Russell
leo@philmds.UUCP (Leo de Wit) (10/03/89)
In article <Sep.27.16.19.22.1989.2257@topaz.rutgers.edu> clong@topaz.rutgers.edu (Chris Long) writes: | |I find myself needing a really hot 68000 binary search routine. This |routine will be called millions of times, so it should be as efficient |as possible. I need it to go through about 10,000 items, each with a |size of ~ 10 bytes. Does anyone have something like this already coded? If you're really in for speed, why bother with _binary_ searching ? Use hashed searching instead. The binary one will need some 13, 14 lookups & compares, the hashing one - depending on the hashing function and the filling - much less (1? 2? 3?) plus some time to calculate the hashing function. Leo.