Beefy Boxes and Bandwidth Generously Provided by pair Networks Bob
P is for Practical
 
PerlMonks  

Re: hashing intervals

by choroba (Abbot)
on Jul 29, 2013 at 16:09 UTC ( #1046886=note: print w/ replies, xml ) Need Help??


in reply to hashing intervals

Here is a simple OO solution with fixed non-overlapping data. It keeps an array of triplets beginning, end, value. It sorts this array at the end to make the retrieval possible. You might need to implement a faster searching algorithm (e.g. binary search) if your data are large and time is critical.

#!/usr/bin/perl use warnings; use strict; use feature qw(say); { package Triplets; sub new { return bless [], shift; } sub add { my $self = shift; push @$self, \@_; } sub sort { my $self = shift; @$self = sort { $a->[0] <=> $b->[0] } @$self; } sub retrieve { my $self = shift; my $value = shift; my $idx = 0; $idx++ while $idx <= $#$self and $self->[$idx][0] <= $value; return $self->[$idx-1][-1] if $idx and $self->[$idx-1][1] >= $ +value; return; } } my $triplets = 'Triplets'->new; while (<DATA>) { my ($int, $value) = split; my ($from, $to) = split /-/, $int, 3; $triplets->add($from, $to, $value); } $triplets->sort; say "$_: ", $triplets->retrieve($_) // 'Undefined' for 1 .. 135; __DATA__ 23-45 12 11-17 2 46-134 23 fixed here!!! 10-10 65 1-1 45 19-20 10
لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ


Comment on Re: hashing intervals
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1046886]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (11)
As of 2014-04-23 20:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (554 votes), past polls