Your skill will accomplishwhat the force of many cannot 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

Replies are listed 'Best First'.
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.

Create A New User
Node Status?
node history
Node Type: note [id://884167]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (7)
As of 2018-03-20 16:01 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (254 votes). Check out past polls.

Notices?