Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: Lookup closest hash key

by nif (Sexton)
on Jan 25, 2011 at 16:20 UTC ( #884167=note: print w/ replies, xml ) Need Help??


in reply to Lookup closest hash key

Why not to code B-Tree yourself?

#!/usr/bin/perl use strict; use warnings; my %distances = ( 100 => 'London', 200 => 'Paris', 300 => 'Rome', 600 => 'Berlin' ); my @distances = sort {$a<=>$b} keys %distances; sub make_btree { my $first = shift; my $nof = shift; if ( $nof == 1 ) { return { Value => $distances[$first] }, } else { my $m = int($nof/2); my $val = ( $distances[$first+$m-1] + $distances[$first+$m] )/ +2; return { Value => $val, Left => make_btree($first, $m), Right => make_btree($first+$m, $nof-$m), } } } my $BTREE = make_btree(0, scalar @distances); #use Data::Dumper; #print Dumper( $BTREE ); sub closest_city { my $key = shift; my $btree = $BTREE; while ( exists $btree->{Left} ) { my $v = $btree->{Value}; $btree = $btree->{ $key<$v ? 'Left' : 'Right' } } $distances{ $btree->{Value} }; } print q{closest_city(5)="}, closest_city(5), qq{"\n}; print q{closest_city(149)="}, closest_city(149), qq{"\n}; print q{closest_city(150)="}, closest_city(150), qq{"\n}; print q{closest_city(203)="}, closest_city(203), qq{"\n}; print q{closest_city(290)="}, closest_city(290), qq{"\n}; print q{closest_city(500)="}, closest_city(500), qq{"\n}; print q{closest_city(5000)="}, closest_city(5000), qq{"\n};
Output:
closest_city(5)="London" closest_city(149)="London" closest_city(150)="Paris" closest_city(203)="Paris" closest_city(290)="Rome" closest_city(500)="Berlin" closest_city(5000)="Berlin"
Following B-Tree will be generated in this example:
250 / \ 150 450 / | | \ 100 200 300 600 | | | | London Paris Rome Berlin


Comment on Re: Lookup closest hash key
Select or Download Code
Re^2: Lookup closest hash key
by Just in (Sexton) on Jan 26, 2011 at 01:07 UTC

    That's awesome! Thanks to you and Simon. Now I've got more ideas and code to benchmark.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (7)
As of 2015-07-02 01:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

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









    Results (25 votes), past polls