Perl comparison function for binary search

Hi :-)

I wrote this binary search function. I wrote it so that I could pass
a comparison function as the last parameter. But I have to write
"sub" and I noticed that the built in sort function doesn't need it.
So I have to write:

sub { shift <=> shift}
instead of:
{$a <=> b}.

This might be a silly question, but I'd like to know if I can modify the
binary search function to receive a function similar to the one that
"sort" receives.

#/usr/bin/perl -w

use strict;

# By sefault it works on strings
sub binary_search {
my $arr = shift;
my $value = shift;
my $cmpf = shift || sub {shift cmp shift};

my $left = 0;
my $right = @$arr - 1;
while ($left <= $right) {
my $mid = int($right + $left) >> 1;

my $c = &$cmpf($arr->[$mid], $value);
if ($c == 0) {
return 1
}
if ($c > 0) {
$right = $mid - 1
}
else {
$left = $mid + 1
}
}
return 0
};

my @arr = qw(1 2 3 4 5 6 7 8);

for (0 .. 9)
{
print binary_search(\@arr, $_) . "\n"
}


Regards,
Nelson.-

--
http://arhuaco.org

--
To unsubscribe, e-mail: beginners-unsubscribe@perl.org
For additional commands, e-mail: beginners-help@perl.org
http://learn.perl.org/

Re: Perl comparison function for binary search

On Sun, Apr 13, 2008 at 2:38 PM, Nelson Castillo wrote:
> Hi :-)
>
> I wrote this binary search function. I wrote it so that I could pass
> a comparison function as the last parameter. But I have to write
> "sub" and I noticed that the built in sort function doesn't need it.
> So I have to write:
>
> sub { shift <=> shift}
> instead of:
> {$a <=> b}.
>
> This might be a silly question, but I'd like to know if I can modify the
> binary search function to receive a function similar to the one that
> "sort" receives.
snip

Short answer, no, code blocks are not accessible from normal Perl.
You must use an anonymous function.

Medium answer, yes, but you must write your library code in XS.
Normal Perl can't access code blocks, but I believe you can do it in
XS, look at perlguts and perlapi for more info.

Long answer, you can use $a and $b just like the sort function does:

my_sort(sub { $a <=> $b }, @list);

sub my_sort {
my $compare = shift;
local ($a, $b);
#set $a and $b from @_ some how
my $r = $compare->();
if ($r < 0) {
} elsif ($r == 0) {
} else {
}
}

--
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.

--
To unsubscribe, e-mail: beginners-unsubscribe@perl.org
For additional commands, e-mail: beginners-help@perl.org
http://learn.perl.org/

Re: Perl comparison function for binary search

Nelson Castillo wrote:
> Hi :-)

Hello,

> I wrote this binary search function. I wrote it so that I could pass
> a comparison function as the last parameter. But I have to write
> "sub" and I noticed that the built in sort function doesn't need it.
> So I have to write:
>
> sub { shift <=> shift}
> instead of:
> {$a <=> b}.
>
> This might be a silly question, but I'd like to know if I can modify the
> binary search function to receive a function similar to the one that
> "sort" receives.

To find out if you can do the same thing that a Perl built-in function
can do you have to find out what prototype it uses:

$ perl -le'print prototype "CORE::open"'
*;$@
$ perl -le'print prototype "CORE::sort"'


But sort does not have a prototype so you can't replicate what sort does
in perl.

perldoc -f prototype
perldoc perlsub


> #/usr/bin/perl -w
>
> use strict;
>
> # By sefault it works on strings
> sub binary_search {
> my $arr = shift;
> my $value = shift;
> my $cmpf = shift || sub {shift cmp shift};

"shift cmp shift" is ambiguous (there is no guarantee which shift will
be called first.) You should probably use "$_[0] cmp $_[1]" instead.

Because you only have two options, either strings or numbers, you could
do it something like this:

use Scalar::Util qw/ looks_like_number /;

sub binary_search {
my $arr = shift;
my $value = shift;
my $cmpf = looks_like_number( $value )
? sub { $_[0] <=> $_[1] }
: sub { $_[0] cmp $_[1] };


> my $left = 0;
> my $right = @$arr - 1;

That is usually written as:

my $right = $#$arr;


> while ($left <= $right) {
> my $mid = int($right + $left) >> 1;

The int() is superfluous. $right and $left are integers so adding them
together will produce an integer.


> my $c = &$cmpf($arr->[$mid], $value);

That is usually written as:

my $c = $cmpf->($arr->[$mid], $value);


> if ($c == 0) {
> return 1
> }
> if ($c > 0) {
> $right = $mid - 1
> }
> else {
> $left = $mid + 1
> }
> }
> return 0
> };
>
> my @arr = qw(1 2 3 4 5 6 7 8);
>
> for (0 .. 9)
> {
> print binary_search(\@arr, $_) . "\n"
> }


John
--
Perl isn't a toolbox, but a small machine shop where you
can special-order certain sorts of tools at low cost and
in short order. -- Larry Wall

--
To unsubscribe, e-mail: beginners-unsubscribe@perl.org
For additional commands, e-mail: beginners-help@perl.org
http://learn.perl.org/

Re: Perl comparison function for binary search

On Sun, Apr 13, 2008 at 3:10 PM, John W. Krahn wrote:
(cut)

> > my $c = &$cmpf($arr->[$mid], $value);
> >
>
> That is usually written as:
>
>
> my $c = $cmpf->($arr->[$mid], $value);

Thanks Chas. and John for your feedback. I think I'm happy with this version:

#!/usr/bin/perl -w

use strict;

# By sefault it works on strings
sub binary_search {
my $arr = shift;
my $value = shift;
my $cmpf = shift || sub {$_[0] cmp $_[1]};

my $left = 0;
my $right = $#$arr;

while ($left <= $right) {
my $mid = ($right + $left) >> 1;
my $c = $cmpf->($arr->[$mid], $value);
return 1
if ($c == 0);
if ($c > 0) {
$right = $mid - 1
} else {
$left = $mid + 1
}
}
return 0
}

my @arr = qw(1 2 3 11); # the array must be sorted

print "searching in @arr\n";
print "Let's use a string comparison function first\n";

for (0, 2, 3, 11, 12)
{
print "is $_ there? => " . binary_search(\@arr, $_) . "\n"
}

print "\nNow let's use a numerical comparison function\n";

for (1, 11)
{
print "is $_ there? => " . binary_search(\@arr, $_, sub {$_[0] <=>
$_[1]}) . "\n"
}

Thanks,
Nelson.-

--
http://arhuaco.org

--
To unsubscribe, e-mail: beginners-unsubscribe@perl.org
For additional commands, e-mail: beginners-help@perl.org
http://learn.perl.org/

Re: Perl comparison function for binary search

Nelson Castillo wrote:
> On Sun, Apr 13, 2008 at 3:10 PM, John W. Krahn wrote:
> (cut)
>
>>> my $c = &$cmpf($arr->[$mid], $value);
>>>
>> That is usually written as:
>>
>>
>> my $c = $cmpf->($arr->[$mid], $value);
>
> Thanks Chas. and John for your feedback. I think I'm happy with this version:
>
> #!/usr/bin/perl -w
>
> use strict;
>
> # By sefault it works on strings
> sub binary_search {
> my $arr = shift;
> my $value = shift;
> my $cmpf = shift || sub {$_[0] cmp $_[1]};
>
> my $left = 0;
> my $right = $#$arr;
>
> while ($left <= $right) {
> my $mid = ($right + $left) >> 1;
> my $c = $cmpf->($arr->[$mid], $value);
> return 1
> if ($c == 0);
> if ($c > 0) {
> $right = $mid - 1
> } else {
> $left = $mid + 1
> }
> }
> return 0
> }
>
> my @arr = qw(1 2 3 11); # the array must be sorted
>
> print "searching in @arr\n";
> print "Let's use a string comparison function first\n";
>
> for (0, 2, 3, 11, 12)
> {
> print "is $_ there? => " . binary_search(\@arr, $_) . "\n"
> }

That won't work correctly unless the numbers are sorted correctly:

$ perl -le' print for sort { $a cmp $b } 0, 2, 3, 11, 12'
0
11
12
2
3



John
--
Perl isn't a toolbox, but a small machine shop where you
can special-order certain sorts of tools at low cost and
in short order. -- Larry Wall

--
To unsubscribe, e-mail: beginners-unsubscribe@perl.org
For additional commands, e-mail: beginners-help@perl.org
http://learn.perl.org/

Re: Perl comparison function for binary search

On Sun, Apr 13, 2008 at 10:17 PM, John W. Krahn wrote:
>
> Nelson Castillo wrote:
(cut)
> That won't work correctly unless the numbers are sorted correctly:
>
> $ perl -le' print for sort { $a cmp $b } 0, 2, 3, 11, 12'
> 0
> 11
> 12
> 2
> 3

Hi. I wanted to stress that with different comparators the search
behaves differently. The
set is intentionally sorted in the wrong way in the first call to
binary_search.
I know that in short: you need to use the same comparator for sorting
and for searching.

N.-

--
http://arhuaco.org

--
To unsubscribe, e-mail: beginners-unsubscribe@perl.org
For additional commands, e-mail: beginners-help@perl.org
http://learn.perl.org/