How to do a range query

Question

I have a bunch of numbers timestamps that I want to check against a range to see if they match a particular range of dates. Basically like a BETWEEN .. AND .. match in SQL. The obvious data structure would be a B-tree, but while there are a number of B-tree implementations on CPAN, they only seem to implement exact matching. Berkeley DB has the same problem; there are B-tree indices, but no range matching.

What would be the simplest way to do this? I don't want to use an SQL database unless I have to.

Clarification: I have a lot of these, so I'm looking for an efficient method, not just grep over an array.

Answer 1

Timestamps are numbers. why not common numerical comparaison operators like > and < ?

If you have many of timestamps the problem is not different if you just want to filter your set once. It's O(n) and every other method will be longer.

On the other hand, with a huge set from which you want to extract many different ranges, it could be more efficient to first sort the items. Call the number of search m, the complexity of direct filtering will be O(m.n). With sort followed by search it could be O(n.log(n) + m.log(n)) which is usually much better.

Any O(n.log(n)) sort method will do, including using the built-in sort operator (or b-tree like you suggested). The major difference between efficient sorting methods is if your memory can hold your full set or not. I there is a memory bootleneck to keep both datas and keys (timestamps) in memory you can keep only the timestamp and some index to data in memory and the real data elsewhere (disk file, database). But if your data set is really so big the most efficient solution would probably be to put the whole thing in a database with and index on timestamp (tie to database is real easy using perl).

Then you will have your range. You just use a dicotomic search to look for index of the first element included in range and of the last, complexity will be O(log(n)) (if you do a linear search the whole purpose of sorting will be defeated).

Below example of using sort and binary_search on an array of timestamps, extending use to some data structure with timestamp and content is left as an exercice.

use Search::Binary;

my @array = sort ((1, 2, 1, 1, 2, 3, 2, 2, 8, 3, 8, 3) x 100000);
my $nbelt = @array;

sub cmpfn
{
    my ($h, $v, $i) = @_;
    $i = $lasti + 1 unless $i;
    $record = @array[$i||$lasti + 1];
    $lasti = $i;
    return ($v<=>$record, $i);
}

for (1..1){
    $pos = binary_search(1, $nbelt, 2, \&cmpfn);
}
print "found at $pos\n";

Answer 2

I haven't used it. But found this on searching CPAN. This may provide what you want. You can use Tree::Binary for constructing your data and subclass Tree::Binary::Visitor::Base to do your range queries.

Other easy way is to use SQLite.

Answer 3

grep will be fast, even on a million of them.

# Get everything between 500 and 10,000:

my @items = 1..1_000_000;
my $min = 500;
my $max = 10_000;

my @matches = grep {
  $_ <= $max && $_ >= $min
} @items;

Run under time I get this:

time perl million.pl 

real    0m0.316s
user    0m0.210s
sys 0m0.070s