Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Re: hashing intervals

by choroba (Chancellor)
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
لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (4)
As of 2016-10-27 11:43 GMT
Find Nodes?
    Voting Booth?
    How many different varieties (color, size, etc) of socks do you have in your sock drawer?

    Results (360 votes). Check out past polls.