How to find an element in a linked list of blocks (containing n elements) as fast as possible?

My data structure is a linked list of blocks. A block contains 31 elements of 4 byte and one 4 byte pointer to the next block or NULL(in summary 128 bytes per block). I add elements from time to time. If the last block is full, I add another block via pointer.

One objective is to use as less memory (= blocks) as possible and having no free space between two elements in a block.

This setting is fix. All code runs on a 32-bit ARM Cortex-A8 CPU with NEON pipeline.

Question: How to find a specific element in that data structure as quickly as possible?

Approach (right now): I use sorted blocks and binary search to check for an element (9 bit of the 4 byte are the search criteria). If the desired element is not in the current block I jump to the next block. If the element is not in the last block and the last block is not yet full, I use the result of the binary search to insert the new element (if necessary I make space using memmove within this block). Thus all blocks are always sorted.

Do you have an idea to make that faster? This is how I search right now: (q->getPosition() is an inline function that just extracts the 9-bit position开发者_如何学JAVA from the element via "& bitmask")

do
{
    // binary search algorithm (bsearch)
    // from http://www.google.com/codesearch/
    // p?hl=en#qoCVjtE_vOw/gcc4/trunk/gcc-
    // 4.4.3/libiberty/bsearch.c&q=bsearch&sa=N&cd=2&ct=rc

    base = &(block->points[0]);

    if (block->next == NULL)
    {
        pointsInBlock = pointsInLastBlock;
        stop = true;
    }
    else
    {
        block = block->next;
    }

    for (lim = pointsInBlock; lim != 0; lim >>= 1)
    {
        q = base + (lim >> 1);

        cmp = quantizedPosition - q->getPosition();

        if (cmp > 0)
        {
            // quantizedPosition > q: move right
            base = q + 1;
            lim--;
        }
        else if (cmp == 0)
        {
            // We found the QuantPoint
            *outQuantPoint = q;
            return true;
        }
        // else move left
    }
}
while (!stop);

Since the bulk of the time is spent in the within-block search, that needs to be as fast as possible. Since the number of elements is fixed, you can completely unroll that loop, as in:

if (key < a[16]){
  if (key < a[8]){
    ...
  }
  else { // key >= a[8] && key < a[16]
    ...
  }
}
else { // key >= a[16]
  if (key < a[24]){
    ...
  }
  else { // key >= a[24]
    ...
  }
}

Study the generated assembly language and single-step it in a debugger, to make sure the compiler's giving you good code.

You might want to write a little program to print out the above code, as it will be hard to write by hand, or possibly generate it with macros.

ADDED: Just noticed your 9-bit search criterion. In that case, just pre-allocate an array of 512 4-byte words, and index it directly. That's the fastest, and the least code.

ALSO ADDED: If you need to keep your block structure, there's another way to do the unrolled binary search. It's the Jon Bentley method:

i = 0;
if (key >= a[i+16]) i += 16;
if (key >= a[i+ 8]) i +=  8;
if (key >= a[i+ 4]) i +=  4;
if (key >= a[i+ 2]) i +=  2;
if (i < 30 && key >= a[i+ 1]) i +=  1; // this excludes 31
if (key == a[i]) // then key is found

That's slower than the if-tree above, because of manipulating i, but could be substantially less code.

Let the number of elements in each block be m and the total number of blocks currently in the list be n. Then the current time complexity of you algorithm is O(n log m).

If you cannot move elements once they are added to a block, then I don't think you can do better in terms of time complexity than what you are already doing. (You could keep track of the maximum and minimum elements in a block, and skip the blocks if the element does not lie in this range. But this is not going to give you much gain. This will also waste space keeping track of the minimum and maximum for each block)

If you can afford to spend time while inserting the element and can move elements from one block to another, then here is a scheme that has time complexity O(log (mn)).

Basically, you keep all elements in sorted order. When a new element has to be inserted, binary search across block boundaries and insert it in its correct location, shifting elements to create space. This will lead to O(nm) time while inserting elements but O(log (mn)) when finding an element.

if this search criterion for an element is fixed, you had better to move the searching into a separate index structure, because the maximal number of elements you distinguish by your search criterion is only 2^9 = 512 indexes, so the maximal size of the search index would be (2 + 4)*512 = 3072, but you could surely use other that static one if you needed, saving some memory. Right now, imagine it as a field of 512 pairs <9-bit index, direct address>, that should be very fast (only one NULL-check and dereference call respectively).

Generally the answer on your question also depend on what other operations you want to perform on your structure and how frequently each of them (including the search ability). If all you want is search(9 bits)->add/modify/read, the your block structure would be useless. You could write them here and maybe add what language you'r using.

Edit 3: I just noticed you can't change the blocks' size. But is your search for efficiency reasons only, or do you need the elements of list to be unique (by those 9 bits)?