Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com Mar 7 '12 at 18:07

This question came from our site for professional and enthusiast programmers.

add comment

1 Answer 1

up vote 1 down vote accepted

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;
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.