Data structure to use for complex lookups in an event engine?

Question

What would be an optimal way to organize arbitrary data types into a structure that allows for complex (non-index based) lookups into the data without performing full loop-through's?

For a little background, I am not looking for an answer on how to architect an Event engine, rather I am looking for methods to improve a current implementation.

With the 5 second tour, I have a architecture in place with the following components,

• Signals - Signals what handles to execute
• Handles - Executes when a signal is received
• Queue - Manages handles
• Engine - Manages the queues and processes signals, new handles etc..

My current implementation has a few pitfalls,

1. Signals are currently coupled into a Queue, this is done so the engine can identify Queues in storage and the signals they represent.
2. There are two separate Queue storages, indexed and non-indexed, index exists for lookups on strings/int's, non-index exists for complex signals such as regex, array comparisons etc..

I think that I may have a solution but would like the thoughts of others that have developed similar systems.

With the new architecture I have thought of, it would consist of the following,

1. Queues would store only a "data" property rather than a signal which, would be would passed to the engine for signal comparisons.
2. The engine would no longer have non-index and index storage, rather a single storage would be used that would require loop through lookups.

The library is written in PHP (if that matters), if you want to see the source it's at http://www.github.com/nwhitingx/prggmr.

Answer 1

After doing a lot of research regarding this matter a binary search will provide the greatest gain without to much complexity.

The search function itself is oblivious to the actual data to allow for searching of any arbitrary data, given that it has the ability to be sorted and compared.

The code below is my end result, note that this belongs to an SplFixedArray extension.

public function binsearch($node, $compare)
{
    $low = 0;
    $high = $this->getSize() - 1;

    while ($low <= $high) {
        $mid = ($low + $high) >> 1;
        $nval = $this->offsetGet($mid);
        $cmp = $compare($nval, $node);
        switch (true) {
            case $cmp === true:
                return $mid;
                break;
            case $cmp === 0:
                $low = $mid + 1;
                break;
            case $cmp === 1:
                $high = $mid - 1;
                break;
            default:
                return null;
                break;
        }
    }

    return null;
}

Performance Tests using an array with 1,000,000 nodes

Binary
0.0001220703125
Linear Search
0.0046999454498291

Test code

$array = new FixedArray();
for ($i=0;$i!=1000000;$i++ ){
    $array->push($i);
}
echo "Binary".PHP_EOL;
$t = microtime(true);
$array->binsearch(6570, function($node, $needle){
    if ($node > $needle) {
        return 0;
    }
    if ($node < $needle) {
        return 1;
    }
    if ($node === $needle) {
        return true;
    }
});
echo microtime(true) - $t.PHP_EOL;
echo "Linear Search".PHP_EOL;
while($array->valid()) {
    if ($array->current() == 6570) break;
    $array->next();
}
echo microtime(true) - $t.PHP_EOL;