Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Re: hashing intervals

by choroba (Canon)
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?

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 chilling in the Monastery: (6)
As of 2015-07-29 06:18 GMT
Find Nodes?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...

    Results (260 votes), past polls