--$num_to_look_for until(exists $hash{$num_to_look_for});
[download]

++ Thanks, I really like this suggestion. Much of the time the ranges tend to be short - perhaps around 50 to 100 wide. However, sometimes they might up to several thousand wide, as they might be representing multiple pages-worth of english text. I'll give it a whirl on some real examples.

There is not really enough information here yet.

How would the extent each of the ranges be established?

Do the ranges overlap?

Are the ranges contiguous?

Can you reasonably guestimate the minimum and maximium integer values?

There are various ways of dealing with ranges, some more complicated than others (I remember Abigail-II recommending red-black trees to a similar question once, but can't locate it now), but which would be the simplest or fastest or otherwise 'best' depends very much on the details of your requirements.

How would the extent each of the ranges be established?

They come from the source fragments of the composite string. Say the composite string is made up of three fragments "FOO" "QUUX" and "BAR". Each of these fragments is a string-based object, with extra info attached to it that I need to access. My ranged hash (or maybe array - thanks dragonchild) would then look like:

# ... stands for the fragment's metadata
{ 0 => Fragment->new('FOO', ...),
  3 => Fragment->new('QUUX', ...),
  7 => Fragment->new('BAR', ...) }
# and the composite string looks like
"FOOQUUXBAR";
[download]

I want to be able to get back to the source fragment object (and its associated data) quickly from a given offset in the composite string.

Do the ranges overlap?

Nope

Are the ranges contiguous?

Yup

Can you reasonably guestimate the minimum and maximium integer values?

Not easily, no - the fragments might be quite short or several thousand characters long, and the total number of fragments is also very variable.

Thanks/

Assuming "a few thousand" is less than say low tens of thousands, then using an array, and storing the (same)object in each element of the range would certainly be the fastest method. The limitation being the memory consumption if your array is likely to get very large.

{ 
    my array;
    sub set{ 
        my( $frag, $start, @meta ) = @_;
        @array[ $start .. ( $start + length( $freg ) -1 ) ] = 
            ( Fragment->new( $frag, @meta ) ) x length( $frag );
        return $array[ $start ];
    }
    sub find{
        my( $offset ) = @_;
        return $array[ $offset ];
    }
}
...
set( 'FOO', 0, ... );
set( 'QUUX', 3, ... );
set( 'BAR', 7, ... );
...

my $found = find( 5 );
print $found->value; # prints 'QUUX';
[download]

If that consumes too much space, then you could use a scalar to represent the array (in less space) and an array to store the objects.

{ 
    my $pseudo;
    my @frags;
    sub set{
        my( $frag, $offset, @meta ) = @_;
        push @frags, Fragment->new( $frag, @meta );
        $pseudo .= pack( 'v', $#frags ) x length( $frag );
        return $frags[ -1 ];
    }
    sub find{
        my $offset = @_;
        my $index = unpack( 'v', substr( $pseudo, $offset, 2 ) );
        return $frags[ $index ];
    }
}
[download]

With this, you push the objects onto an array once for each fragment, and then store the index at which you pushed it, converted to it's binary representation, once for each position it represents.

This way is also very fast but reduces the memory consumption. A fragment that contains 100 characters requires about 200 + 24 bytes of storage, rather than 100 * 24 bytes. The limitation is that using a 16-bit integer to hold the indexes limits you to 64K fragments. You could move to 32-bits whch would probably cover mosts needs, with the obvious increase in memory usage.

---

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail

• Always check to see if number entered is an exact match before searching
• Use a parallel array to allow a modified binary search

Cheers - L~R

If space is really too much of an issue to have an array of every value in the range, but you need more speed than a simplistic solution like my previous post will give you, than you could store the sorted list of keys from your hash and binary search it. This is probably the best compromise if you have major speed and memory concerns.

Of course, this all depends on what the data is like, and how it is used. A simpler solution will almost certainly suffice, unless you are accessing megabytes of data thousands of times.


When's the last time you used duct tape on a duct? --Larry Wall