Most efficient search on small array?

Question

I have a C array, where it rarely (almost never) gets updated:

unsigned long user_values[8];

I want to be able to make lots of quick look-ups (hundreds of times per second on a slow machine), to check if a value is in the array, and if it is, get its index. Almost all of the time, this look-up will fail to find the item in the array.

Normally, I would keep the array sorted, and use binary search, but I am unsure of the efficiency of binary search on very small data sets. Are there any more efficient ways to do this lookup, given its small, known size?

Answer 1

I suggest something like a small hash to immediately detect most of the failures. Something like this:

#define HASH(x)    ((x) & 0xff)   // This can be improved if needed
uint8_t possible[256];

void initHash()
{
    int i;

    memset(possible, 0, sizeof(possible));
    for (i=0;i<8;i++)
        possible[HASH(user_values[i])] = 1;
}

int find(unsigned long val)
{
    // Rule out most failures with a quick test.
    if (!possible[HASH(val)])
        return -1;

    // Now use either binary or linear search.
    ...
}

Note that with up to 8 slots set in a 256 slot hash table, you will weed out 31/32 or 97% of the failures immediately. There are three obvious ways to improve this:

1. You can make the hash table bigger to filter out more failures but at the cost of using more memory. Better yet, you can add a second hash (for example hash on the second to last byte). That would take only another 256 bytes but filter out an addition 97% of the 3% that passed the first hash. This algorithm of multiple hashes is called a Bloom Filter, by the way.
2. You can use 1 bit per hash index instead of one byte which makes the hash table 1/8 the size but requires a lengthier computation to do the hash check.
3. You can supply a better hash function, depending on what kind of data you are expecting.

Answer 2

How much of a speed up are you looking for? Unless there's some exploitable patterns in your sets (arrays), with just 8 checks, it's going to be minimal gains either way. Compilers are generally pretty good at optimizing this sort of thing. I've found that with some gcc compiles, that using pointers in my for loop can buy me a few percent. Unrolling the loop since you know the static 8 offsets might be worth a few percent (and might not).

Here's a hypothetical exploitable data pattern. IF it were the case that your sets/vectors/lists/arrays/callthemwhatyouwill tended to cluster AND your range of candidates to test were evenly distributed across the 0x00000000-to-0xFFFFFFFF range, THEN you might gain a little be having your vectors presorted, and simply testing for less than the first or greater than the last, which would be 2 tests and likely usually fail, and when it didn't, devolve to the linear search through the list. But this kind of thing really depends on the various ratios (how wide are the windows? how much overhead does the presorting add? etc). Only testing against your real world data will tell.

And there's always the real danger that the exploitable pattern, while giving you a 20% speed up normally, behaves terribly in edge cases where your assumptions are violated, hurting you by orders of magnitude.

Answer 3

There is some technique with switch-case jump table, but it's requires that compiler takes advantage of it, which may or may not happen in your specific case. Instead of keeping those values in array (as you wrote values are almost never changed) put them literally as labels:

#define NOT_FOUND -1

int index = NOT_FOUND; // or any other way to mark that number is not found
switch (val)
{
    case 0x00000000UL : // replace with array values
        index = 0; break;
    case 0x00000001UL :
        index = 1; break;
    case 0x00000002UL :
        index = 2; break;
    // ...
};

The only downside is that numbers are now "fixed" in compile-time. Thus to update them you need to recompile your whole program, what may be not acceptable (?).

Answer 4

This program does binary search and linear search (many times so they can be easily timed). On the OP's condition that the search value is usually not found, the linear search takes approximately twice as long as the binary search. It takes 3 iterations of the binary search to reduce 8 elements to 1, but 8 iterations of the linear search. I used unsigned int rather than unsigned long.

#include <stdio.h>
#include <time.h>

#define ARRLEN 8
#define LOOPS 0x7FFFFF

unsigned user_values[ARRLEN] = { 1, 234, 8124, 8335, 10234, 11285, 637774, 788277 };

int main (int argc, char *argv[]) {
    unsigned val;
    int bot, top, mid, loop;
    clock_t start, elap;

    if (argc < 2) return 1;
    if (sscanf (argv[1], "%u", &val) != 1) return 1;

    // binary search
    printf ("Binary search for %u: ", val);
    start = clock();
    for (loop=0; loop!=LOOPS; loop++) {
        bot = 0;
        top = ARRLEN;
        while (top-bot > 1) {
            mid = ((top + bot) >> 1);
            if (user_values[mid] <= val)
                 bot = mid;
            else top = mid;
        }
    }
    elap = clock() - start;
    if (user_values[bot] == val)
         printf ("found");
    else printf ("not found");
    printf (" in count %u\n", (unsigned)elap);

    // linear search
    printf ("Linear search for %u: ", val);
    start = clock();
    for (loop=0; loop!=LOOPS; loop++) {
        for (bot=0; bot<ARRLEN; bot ++)
            if (user_values[bot] == val)
                break;
    }
    elap = clock() - start;
    if (bot<ARRLEN)
         printf ("found");
    else printf ("not found");
    printf (" in count %u\n", (unsigned)elap);

    return 0;
}