juwaidah1990 has asked for the wisdom of the Perl Monks concerning the following question:

Hello, I made a program that generates a random number between 1 and 100 then it tries to guess it using binary search... It works perfectly, the only thing is that it's kinda slow, may be it's the search methode I used... I don't know, anyways, here's the code, please tell me if it can be improved :) 
#!/usr/bin/perl -w
use strict;
my $max = 100;
my $min = 1;
my @numbers = $min..$max;
my $target = int(1 + rand 100);
my $interval;
my $guess;
my $result = 3;

while ($result!=1) {
  $interval = $max - $min;
  $guess = $min + int($interval/2);
  print "\$result = $result; \$min = $min; \$max = $max; \$interval = 
+$interval; \$guess = $guess\n";
  $result = ✓
  ($result == 0) && ($min = $guess);
  ($result == 2) && ($max = $guess);
}
sub check {
  print "\$guess = $guess; \$target = $target\n\n";
  ($guess < $target) ? 0 : ($guess > $target) ? 2 : 1;
}

[download]

Replies are listed 'Best First'.
Re: Number gussing game
by ysth (Canon) on Jun 28, 2007 at 07:12 UTC
    One thing is your subroutine call &check; either declare sub check earlier in the file, so you can just say $result = check;, or add parentheses ($result = &check();) (or both). Calling a sub with & but without () has a special effect that is rarely wanted or needed; it's harmless in this case, but not doing it accidentally is a good habit to form.

    I also note that if $target is 100, $guess will reach 99 and stay there forever; try having $max be one more than the end of the possible range.

[reply]
[d/l]
[select]
Re: Number gussing game
by GrandFather (Saint) on Jun 28, 2007 at 07:48 UTC

    If you change your result constants to -1, 0 and 1 then you can change your test code to:

      $result = $guess <=> $target;
  $min = $guess if $result == -1;
  $max = $guess if $result == 1;

    [download]

    which uses the numeric comparison operator <=> (or spaceship, see 'Equality Operators' in perlop) to perform the check. You need to change the while loop test of course.

    Note too the use of if as a statement modifier to make the code a little clearer.

    $guess and $interval should be declared within the loop to make it more obvious that their values are not used outside the loop. You should almost never use variables global to a sub inside the sub - pass them in as parameters.

    DWIM is Perl's answer to Gödel
[reply]
[d/l]
Re: Number gussing game
by davido (Cardinal) on Jun 28, 2007 at 07:17 UTC

    The most guesses that should be necessary when finding one element in a set of a hundred using a binary search should be seven. I would be surprised if a properly implemented binary search could be considered slow with such a small data set. How are you timing it?


    Dave

[reply]
Re: Number gussing game
by roboticus (Chancellor) on Jun 28, 2007 at 11:10 UTC

    juwaidah1990:

    It doesn't appear to be slow on my machine. I wrapped a for loop around it to guess all the numbers, and it ran quite nicely--with the exception of the case of $target=100. You'll want to fix that!

    ...roboticus

[reply]
      I remember I read about adding brackets after the function call but I just forgot to add them :D however, I don't like removing the ampersand, i think it helps distinguish the difference between user defined functions and built-in function... I will actually do that, even though I don't know a lot about the <=> :D but using -1, 0, and 1 makes more sense than using 0, 1, and 2... It's just that considering it's just a loop, i think it should run faster than this!
[reply]
Re: Number gussing game
by juwaidah1990 (Initiate) on Jun 28, 2007 at 21:56 UTC
    I remember I read about adding brackets after the function call but I just forgot to add them :D however, I don't like removing the ampersand, i think it helps distinguish the difference between user defined functions and built-in function... I will actually do that, even though I don't know a lot about the <=> :D but using -1, 0, and 1 makes more sense than using 0, 1, and 2... It's just that considering it's just a loop, i think it should run faster than this!
[reply]

      How are you timing it? Consider:

      print time, "\n";
1 for 1 .. 1000000000;
print time, "\n";

      [download]

      is just a loop, but takes a while to run (about 48 seconds on my system) and can be timed accurately enough as shown. You loop executes in about 10 micro seconds (timed over 1 million iterations) which doesn't seem excessively slow to me.

      DWIM is Perl's answer to Gödel
[reply]
[d/l]
        May be it's a problem in my pc, the loop took 184 seconds, which is almost 4 times slower than your machine :) Thank you all for your participation, Cheers!
[reply]

Back to Seekers of Perl Wisdom