CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Advanced:
Finding a word in a sorted list.

 



mariorizzuti
newbie

Jul 25, 2001, 3:47 PM

Post #1 of 1 (976 views)
Finding a word in a sorted list. Can't Post

I have a fixed-length-records file where:

* each record is 18 bytes made by an username (12 bytes) and a number (6 bytes).
* the records are sorted alphabetically.

I am wondering what is the fastest possible way to find the associated numbers of a given list of usernames?
Thanks for any suggestion.

This is what I have so far:
--------
my @user = qw/mario john bill/;

my @sorted_user = sort @user; # sorting allows us to use the last found word as a "$min" for the next one.

my %Line;

my @stats = stat "user.ind";
my $min = 0;
my $max = $stats[7] / 18; # how many records

open INDEX, "user.ind" or die "Can't open 'user.ind': $!";

USER: foreach my $to_find ( @sorted_user ) {
my $last_guess;
while (1) {

my $guess = int ( ($min + $max)/ 2 ); # we are sure that it's between $min and $max, let's try in the middle.

seek (INDEX, 18 * $guess, 0); # this should be more efficient (?) if we used the last read position as offset.

my $bytes = read INDEX, my $record, 18;
croak "Username $to_find couldn't be found." if $bytes != 18 || $guess == $last_guess;

my ($username, $pointer) = unpack "A12 A6", $record;

if ($username eq $to_find ) {

$Line{$username} = $pointer;
$min = $guess; # since the user list is sorted, the next word will be after the one we have just
# found.
next USER;

} elsif ($username lt $to_find ) {

$min = $guess; # our word is not before the one we have just read.

} else {

$max = $guess;

}

$last_guess = $guess;
}
}

close INDEX or die "Can't close 'user.ind': $!";

@user = map {$Line{$_}} @user; # return this
--------

Mario Rizzuti


 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives