Re: Lookup closest hash key

[nif]

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

[Just in]

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