Beefy Boxes and Bandwidth Generously Provided by pair Networks Cowboy Neal with Hat
laziness, impatience, and hubris
 
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 about the Monastery: (15)
As of 2014-04-17 14:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (449 votes), past polls