Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Problem in nested sorts

Reply
Thread Tools

Problem in nested sorts

 
 
David McNerney
Guest
Posts: n/a
 
      03-22-2006
I get some interesting results when I run the following code on Perl
5.8.5 or 5.8.6:

---- begin code ----
#!/usr/bin/perl -w
use strict;

package another;
sub testFunction
{
my @values = sort
{
print "[testFunction, sort function 1] a=$a b=$b\n";
$a <=> $b
} (1,2,3,4,5);
my @values2 = sort
{
print "[testFunction, sort function 2] a=$a b=$b\n";
$a <=> $b
} (1,2,3,4,5);
}

package my_package;
my @seqnums = (486098561006,486098561006);
@seqnums = sort
{
&another::testFunction;
return $a <=> $b;
} @seqnums;
-------- end code -----

It seems that the second time I try to do a sort in a function/method
invoked from within another sort, $a and $b are not defined. If I
define a separate sort function with prototypes, the problem goes away.
The problem also goes away if I have everything in the same package
(ie, get rid of the 2 "package" statements and the "another::" in the
call to &testFunction).

Can anyone see something I'm doing wrong here? Needless to say, the
above code is a minimal test case, and I'm aware that sorting
(1,2,3,4,5) and not doing anything with the results would not normally
be worthwhile...

 
Reply With Quote
 
 
 
 
Brian McCauley
Guest
Posts: n/a
 
      03-23-2006
David McNerney wrote:
> I get some interesting results when I run the following code on Perl
> 5.8.5 or 5.8.6:
> sub testFunction
> {


> }
>
> package my_package;
> @seqnums = sort
> {
> &another::testFunction;
> return $a <=> $b;
> } @seqnums;


> It seems that the second time I try to do a sort in a function/method
> invoked from within another sort, $a and $b are not defined.


Yes, $another::a and $my_package::a are not the same variable.

>If I define a separate sort function with prototypes, the problem goes away.


Yes, that's largely why that option was introduced.

> The problem also goes away if I have everything in the same package
> (ie, get rid of the 2 "package" statements and the "another::" in the
> call to &testFunction).


Yes, $main::a and $main::a are the same variable

> Can anyone see something I'm doing wrong here?


Not reading "perldoc -f sort"? (In particular the bits containing the
word "package").

 
Reply With Quote
 
 
 
 
David McNerney
Guest
Posts: n/a
 
      03-23-2006
> Yes, $another::a and $my_package::a are not the same variable.

Of course they are not the same variable, but if you re-read my code
you'll note that that isn't relevant here.

It sounds like you know Perl well enough. If you read over my code
carefully, I think you'll realize why what you said doesn't relate.

Hint: &testFunction is located entirely in the package "another". It is
doing a simple sort of a locally defined list. During that sort, $a and
$b should be defined, and they are -- but only the first time such a
sort is done. If the call to &testFunction is moved outside the sort
(but still in package "my_package") then both sorts work fine.

Another hint: it's great to try to help folks out on usenet, but try
actually >reading< before getting sarcastic. You thought you saw a
fairly common misunderstanding about the $a and $b vars in perl sorts,
and started typing before reading closely enough to realize that
something else was going on in this case.

Cheers,

Dave

 
Reply With Quote
 
Anno Siegel
Guest
Posts: n/a
 
      03-23-2006
David McNerney <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> I get some interesting results when I run the following code on Perl
> 5.8.5 or 5.8.6:
>
> ---- begin code ----
> #!/usr/bin/perl -w
> use strict;
>
> package another;
> sub testFunction
> {
> my @values = sort
> {
> print "[testFunction, sort function 1] a=$a b=$b\n";
> $a <=> $b
> } (1,2,3,4,5);
> my @values2 = sort
> {
> print "[testFunction, sort function 2] a=$a b=$b\n";
> $a <=> $b
> } (1,2,3,4,5);
> }
>
> package my_package;
> my @seqnums = (486098561006,486098561006);
> @seqnums = sort
> {
> &another::testFunction;
> return $a <=> $b;
> } @seqnums;
> -------- end code -----
>
> It seems that the second time I try to do a sort in a function/method
> invoked from within another sort, $a and $b are not defined. If I
> define a separate sort function with prototypes, the problem goes away.
> The problem also goes away if I have everything in the same package
> (ie, get rid of the 2 "package" statements and the "another::" in the
> call to &testFunction).
>
> Can anyone see something I'm doing wrong here? Needless to say, the
> above code is a minimal test case, and I'm aware that sorting
> (1,2,3,4,5) and not doing anything with the results would not normally
> be worthwhile...


The result is strange, but there's much optimization going on around
the comparison function and I'm no too amazed the mechanism can break
under stress. Note that the comparison function cannot be recursive.
I suppose the reason is related to what you are seeing.

In any case, if your comparison function contains an expensive call
(as to another sort()), that begs to be factored out of the sort, if
at all possible. See if a Schwartz transform, or the techniques offered
by Sort::Maker apply.

Anno
--
If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.
 
Reply With Quote
 
robic0
Guest
Posts: n/a
 
      03-24-2006
On 22 Mar 2006 12:19:26 -0800, "David McNerney" <(E-Mail Removed)> wrote:

>I get some interesting results when I run the following code on Perl
>5.8.5 or 5.8.6:
>
>---- begin code ----
>#!/usr/bin/perl -w
>use strict;
>
>package another;
>sub testFunction
>{
> my @values = sort
> {
> print "[testFunction, sort function 1] a=$a b=$b\n";
> $a <=> $b
> } (1,2,3,4,5);
> my @values2 = sort
> {
> print "[testFunction, sort function 2] a=$a b=$b\n";
> $a <=> $b
> } (1,2,3,4,5);
>}
>
>package my_package;
>my @seqnums = (486098561006,486098561006);
>@seqnums = sort
>{
> &another::testFunction;
> return $a <=> $b;
>} @seqnums;
>-------- end code -----
>
>It seems that the second time I try to do a sort in a function/method
>invoked from within another sort, $a and $b are not defined. If I
>define a separate sort function with prototypes, the problem goes away.
>The problem also goes away if I have everything in the same package
>(ie, get rid of the 2 "package" statements and the "another::" in the
>call to &testFunction).
>
>Can anyone see something I'm doing wrong here? Needless to say, the
>above code is a minimal test case, and I'm aware that sorting
>(1,2,3,4,5) and not doing anything with the results would not normally
>be worthwhile...


Apparently theres no problem with nested sorts within a package as
you've said. Nesting between pkgs seems to fail after the first
sucessfull intra-package nested sort. Even subsequent calls fail.

The $a and $b are confined withing the package as you said as well.

Also, you mentioned
"If I define a separate sort function with prototypes, the problem goes away."

Be aware there is nested sorts are not the same as sort comparison function.
You can define your own "comparison" function that returns true of false, you
can't define a sort function that will have any local affect as in a nested
sort call. Sorts are autonomous.
The form you might be thinking of here is the "sort SUBNAME list".

From the hard to understand docs:
"# using a prototype allows you to use any comparison subroutine
# as a sort subroutine (including other package's subroutines)
package other;
sub backwards ($$) { $_[1] cmp $_[0]; } # $a and $b are not set here
package main;
@new = sort other::backwards @old;
"
Note that $a and $b are not set here as it says. And it only returns t/f
based on the comparison.

This is very different from the behavior you have uncovered.
In general, intermediate $a, $b results are not usefull.

I don't know if "nesting" sorts is good for anything, it might be but
intermediate $a,$b values depend on the method and comparisons.
Nested or complex comparisons are usefull however. For instance
if $a, or $b contain a reference to multifield records where a
multi field sort is needed.

So the bottom like is you probably are just showing a behavior that
deadends in a place that is of no use and designed to fail gracefully
and without documentation. Of course $a and $b generate warnings when
they are not defined (I commented it out below).

Good find!


use strict;
#use warnings;

package another;
sub testFunction
{
my @values = sort
{
print "[testFunction, sort function 1] a=$a b=$b\n";
$a <=> $b
} (1,2,3,4,5);
my @values2 = sort
{
print "[testFunction, sort function 2] a=$a b=$b\n";
$a <=> $b
} (1,2,3,4,5);
}

package my_package;
my @seqnums = (3,2,1);
@seqnums = sort
{
&another::testFunction;
print "====== a=$a b=$b ================\n";
return $a <=> $b;
} @seqnums;

__END__

[testFunction, sort function 1] a=1 b=2
[testFunction, sort function 1] a=3 b=4
[testFunction, sort function 1] a=1 b=3
[testFunction, sort function 1] a=3 b=2
[testFunction, sort function 1] a=1 b=5
[testFunction, sort function 1] a=5 b=2
[testFunction, sort function 1] a=5 b=3
[testFunction, sort function 1] a=5 b=4
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
====== a=3 b=2 ================
[testFunction, sort function 1] a= b=
[testFunction, sort function 1] a= b=
[testFunction, sort function 1] a= b=
[testFunction, sort function 1] a= b=
[testFunction, sort function 1] a= b=
[testFunction, sort function 1] a= b=
[testFunction, sort function 1] a= b=
[testFunction, sort function 1] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
[testFunction, sort function 2] a= b=
====== a=2 b=1 ================


***************************
***************************

use strict;
#use warnings;

#package another;
sub testFunction
{
my @values = sort
{
print "[testFunction, sort function 1] a=$a b=$b\n";
$a <=> $b
} (1,2,3,4,5);
my @values2 = sort
{
print "[testFunction, sort function 2] a=$a b=$b\n";
$a <=> $b
} (1,2,3,4,5);
}

#package my_package;
my @seqnums = (3,2,1);
@seqnums = sort
{
# &another::testFunction;
&testFunction;
print "====== a=$a b=$b ================\n";
my @values = sort
{
print "[testFunction, sort function 3] a=$a b=$b\n";
$a <=> $b
} (1,2,3,4,5);
my @values2 = sort
{
print "[testFunction, sort function 4] a=$a b=$b\n";
$a <=> $b
} (1,2,3,4,5);

return $a <=> $b;
} @seqnums;

__END__

[testFunction, sort function 1] a=1 b=2
[testFunction, sort function 1] a=3 b=4
[testFunction, sort function 1] a=1 b=3
[testFunction, sort function 1] a=3 b=2
[testFunction, sort function 1] a=1 b=5
[testFunction, sort function 1] a=5 b=2
[testFunction, sort function 1] a=5 b=3
[testFunction, sort function 1] a=5 b=4
[testFunction, sort function 2] a=1 b=2
[testFunction, sort function 2] a=3 b=4
[testFunction, sort function 2] a=1 b=3
[testFunction, sort function 2] a=3 b=2
[testFunction, sort function 2] a=1 b=5
[testFunction, sort function 2] a=5 b=2
[testFunction, sort function 2] a=5 b=3
[testFunction, sort function 2] a=5 b=4
====== a=3 b=2 ================
[testFunction, sort function 3] a=1 b=2
[testFunction, sort function 3] a=3 b=4
[testFunction, sort function 3] a=1 b=3
[testFunction, sort function 3] a=3 b=2
[testFunction, sort function 3] a=1 b=5
[testFunction, sort function 3] a=5 b=2
[testFunction, sort function 3] a=5 b=3
[testFunction, sort function 3] a=5 b=4
[testFunction, sort function 4] a=1 b=2
[testFunction, sort function 4] a=3 b=4
[testFunction, sort function 4] a=1 b=3
[testFunction, sort function 4] a=3 b=2
[testFunction, sort function 4] a=1 b=5
[testFunction, sort function 4] a=5 b=2
[testFunction, sort function 4] a=5 b=3
[testFunction, sort function 4] a=5 b=4
[testFunction, sort function 1] a=1 b=2
[testFunction, sort function 1] a=3 b=4
[testFunction, sort function 1] a=1 b=3
[testFunction, sort function 1] a=3 b=2
[testFunction, sort function 1] a=1 b=5
[testFunction, sort function 1] a=5 b=2
[testFunction, sort function 1] a=5 b=3
[testFunction, sort function 1] a=5 b=4
[testFunction, sort function 2] a=1 b=2
[testFunction, sort function 2] a=3 b=4
[testFunction, sort function 2] a=1 b=3
[testFunction, sort function 2] a=3 b=2
[testFunction, sort function 2] a=1 b=5
[testFunction, sort function 2] a=5 b=2
[testFunction, sort function 2] a=5 b=3
[testFunction, sort function 2] a=5 b=4
====== a=2 b=1 ================
[testFunction, sort function 3] a=1 b=2
[testFunction, sort function 3] a=3 b=4
[testFunction, sort function 3] a=1 b=3
[testFunction, sort function 3] a=3 b=2
[testFunction, sort function 3] a=1 b=5
[testFunction, sort function 3] a=5 b=2
[testFunction, sort function 3] a=5 b=3
[testFunction, sort function 3] a=5 b=4
[testFunction, sort function 4] a=1 b=2
[testFunction, sort function 4] a=3 b=4
[testFunction, sort function 4] a=1 b=3
[testFunction, sort function 4] a=3 b=2
[testFunction, sort function 4] a=1 b=5
[testFunction, sort function 4] a=5 b=2
[testFunction, sort function 4] a=5 b=3
[testFunction, sort function 4] a=5 b=4


 
Reply With Quote
 
Brian McCauley
Guest
Posts: n/a
 
      03-24-2006
David McNerney wrote:

> You thought you saw a
> fairly common misunderstanding about the $a and $b vars in perl sorts,
> and started typing before reading closely enough to realize that
> something else was going on in this case.


Yes, sorry. May I be clamped in virtual stocks and pelted with virtual
rotten fruit.

I've reproduced your problem and it does look like a particularly nasty
bug in perl.

Actually better pennace for my crime may be to track down the bug and
submit a patch so I'll try that (it may be beyond me).

 
Reply With Quote
 
David McNerney
Guest
Posts: n/a
 
      03-24-2006
Thanks very much to everyone who replied here. Sorry I was a little
terse Brian! I just sent the following to http://www.velocityreviews.com/forums/(E-Mail Removed):

When an anonymous sort function invokes a method or function defined in
another package, and that
method or function does multiple sorts using its own anonymous sort
functions, the second and later
of these latter sorts fail; $a and $b are not defined. This does not
occur if the function is moved
to the same package as the code performing the first sort, nor does it
occur if the latter "nested"
sorts use a seperately defined sort function with prototypes (in which
case, of course, the $a and $b
variables are not used). And, as implied above, the first "nested" sort
executes correctly.

One person on usenet suggested that nobody ought to be doing such a
thing as described above. Actually,
there are many times when working with a large object-oriented Perl
library when one might need
to sort a (often short) list of objects, and compare values returned by
object methods in the comparison function.
A programmer writing such code should not have to think about whether
the object methods they choose
to invoke happen to use multiple non-prototyped sorts in their
implementation.

Below is a test case, verified to demonstrate the problem on Perl 5.8.5
(Linux) and 5.8.6 (Mac OS X):


#!/usr/bin/perl -w
use strict;

package another;
#package my_package;
sub testFunction
{
my @otherList = sort
{
print "[testFunction, sort 1] a=$a b=$b\n";
$a <=> $b
} (5,4,3,2,1);
print "\@otherList, sorted: ".join(", ", @otherList)."\n";

my @otherList2 = sort
{
print "[testFunction, sort 2] a=$a b=$b\n";
$a <=> $b
} (5,4,3,2,1);
print "\@otherList2, sorted: ".join(", ", @otherList2)."\n";
}

package my_package;
my @list = (13,12,11);
@list = sort
{
&another::testFunction;
#&testFunction;
return $a <=> $b;
} @list;
print "\@list, sorted: ".join(", ", @list)."\n";

#&another::testFunction;

 
Reply With Quote
 
MSG
Guest
Posts: n/a
 
      03-25-2006
David McNerney wrote:
> Thanks very much to everyone who replied here. Sorry I was a little
> terse Brian! I just sent the following to (E-Mail Removed):
>
> When an anonymous sort function invokes a method or function defined in
> another package, and that
> method or function does multiple sorts using its own anonymous sort
> functions, the second and later
> of these latter sorts fail; $a and $b are not defined. This does not
> occur if the function is moved
> to the same package as the code performing the first sort, nor does it
> occur if the latter "nested"
> sorts use a seperately defined sort function with prototypes (in which
> case, of course, the $a and $b
> variables are not used). And, as implied above, the first "nested" sort
> executes correctly.
>
> One person on usenet suggested that nobody ought to be doing such a
> thing as described above. Actually,
> there are many times when working with a large object-oriented Perl
> library when one might need
> to sort a (often short) list of objects, and compare values returned by
> object methods in the comparison function.
> A programmer writing such code should not have to think about whether
> the object methods they choose
> to invoke happen to use multiple non-prototyped sorts in their
> implementation.
>
> Below is a test case, verified to demonstrate the problem on Perl 5.8.5
> (Linux) and 5.8.6 (Mac OS X):
>
>
> #!/usr/bin/perl -w
> use strict;
>
> package another;
> #package my_package;
> sub testFunction
> {
> my @otherList = sort
> {
> print "[testFunction, sort 1] a=$a b=$b\n";
> $a <=> $b
> } (5,4,3,2,1);
> print "\@otherList, sorted: ".join(", ", @otherList)."\n";
>
> my @otherList2 = sort
> {
> print "[testFunction, sort 2] a=$a b=$b\n";
> $a <=> $b
> } (5,4,3,2,1);
> print "\@otherList2, sorted: ".join(", ", @otherList2)."\n";
> }
>
> package my_package;
> my @list = (13,12,11);
> @list = sort
> {
> &another::testFunction;
> #&testFunction;
> return $a <=> $b;
> } @list;
> print "\@list, sorted: ".join(", ", @list)."\n";
>
> #&another::testFunction;


Although I agree that you have an rather interesting discovery,
(which may take a real Perl expert to explain), there is one even
more "interesting" that you haven't discovered yet, and this one is
going to reveal the fault on your part:

Every Perl textbook states that sort() is "special", its sub is
"special" and its $a and $b are "special". Some even warns "weird
and unexpected result" about messing with those $a and $b. Your
code demenstrated exactly that -- The subs for sort should contain
only comparision tests. Nothing more, nothing less! So if you go
back to your code and comment out those two print statements
inside the sort sub block, your code works perfectly!!

In retrospect, I don't remember ever seeing anyone putting "extra"
statements inside a sort sub.

 
Reply With Quote
 
Anno Siegel
Guest
Posts: n/a
 
      03-25-2006
MSG <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> David McNerney wrote:


[...]

> > Below is a test case, verified to demonstrate the problem on Perl 5.8.5
> > (Linux) and 5.8.6 (Mac OS X):
> >
> >
> > #!/usr/bin/perl -w
> > use strict;
> >
> > package another;
> > #package my_package;
> > sub testFunction
> > {
> > my @otherList = sort
> > {
> > print "[testFunction, sort 1] a=$a b=$b\n";
> > $a <=> $b
> > } (5,4,3,2,1);
> > print "\@otherList, sorted: ".join(", ", @otherList)."\n";
> >
> > my @otherList2 = sort
> > {
> > print "[testFunction, sort 2] a=$a b=$b\n";
> > $a <=> $b
> > } (5,4,3,2,1);
> > print "\@otherList2, sorted: ".join(", ", @otherList2)."\n";
> > }
> >
> > package my_package;
> > my @list = (13,12,11);
> > @list = sort
> > {
> > &another::testFunction;
> > #&testFunction;
> > return $a <=> $b;
> > } @list;
> > print "\@list, sorted: ".join(", ", @list)."\n";
> >
> > #&another::testFunction;


[...]

> ... So if you go
> back to your code and comment out those two print statements
> inside the sort sub block, your code works perfectly!!


I don't see the effect you claim to see.

Have you run your modified test with warnings switched on? Do so.
If you still believe the code works perfectly, please post exactly
what you are running.

Anno
--
If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers.
 
Reply With Quote
 
Peter J. Holzer
Guest
Posts: n/a
 
      03-25-2006
Anno Siegel wrote:

> MSG <(E-Mail Removed)> wrote in comp.lang.perl.misc:
>> David McNerney wrote:

>
> [...]
>
>> > Below is a test case, verified to demonstrate the problem on Perl
>> > 5.8.5 (Linux) and 5.8.6 (Mac OS X):
>> >
>> >
>> > #!/usr/bin/perl -w
>> > use strict;
>> >
>> > package another;
>> > #package my_package;
>> > sub testFunction
>> > {
>> > my @otherList = sort
>> > {
>> > print "[testFunction, sort 1] a=$a b=$b\n";
>> > $a <=> $b
>> > } (5,4,3,2,1);
>> > print "\@otherList, sorted: ".join(", ", @otherList)."\n";
>> >
>> > my @otherList2 = sort
>> > {
>> > print "[testFunction, sort 2] a=$a b=$b\n";
>> > $a <=> $b
>> > } (5,4,3,2,1);
>> > print "\@otherList2, sorted: ".join(", ", @otherList2)."\n";
>> > }
>> >
>> > package my_package;
>> > my @list = (13,12,11);
>> > @list = sort
>> > {
>> > &another::testFunction;
>> > #&testFunction;
>> > return $a <=> $b;
>> > } @list;
>> > print "\@list, sorted: ".join(", ", @list)."\n";
>> >
>> > #&another::testFunction;

>
> [...]
>
>> ... So if you go
>> back to your code and comment out those two print statements
>> inside the sort sub block, your code works perfectly!!

>
> I don't see the effect you claim to see.


I see it.

> Have you run your modified test with warnings switched on?


-w is in the shebang line, isn't it?

> Do so. If you still believe the code works perfectly, please post
> exactly what you are running.


Exactly the code posted by David, except that the two print statements
in another::testFunction are commented out. Works with perl 5.8.0, 5.8.4
and 5.8.7 on Linux. I also modified the second half of testFunction to:

my @values2 = sort
{
# print "[testFunction, sort function 2] a=$a b=$b\n";
$a <=> $b
} (1,3,4,2,5);
die unless (@values2 == 5 && $values2[0] == 1 && $values2[2] == 3);

to verify that the sort works correctly. It does.

I only get warnings if there is a print statement in both sorts.

Replacing the print statement with an assignment to a lexically scoped
variable doesn't change anything, so I think, it isn't the print
statement but rather the interpolation of $a and $b which breaks their
magic.

Oh, and BTW, wrapping { local ($a, $b); ... } around the sort doesn't
help, either.

hp

--
_ | Peter J. Holzer | Löschung von at.usenet.schmankerl?
|_|_) | Sysadmin WSR/LUGA |
| | | (E-Mail Removed) | Diskussion derzeit in at.usenet.gruppen
__/ | http://www.hjp.at/ |
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hardware question of sorts lugnut DVD Video 0 01-20-2007 05:27 PM
Alphabetical sorts Ron Adam Python 7 10-17-2006 04:21 PM
XML parser that sorts elements? jmike@alum.mit.edu Python 6 09-28-2006 03:33 PM
Is there anyway to change the default way NTFS "sorts" files ny name? Jimmy Dean Computer Support 3 09-03-2004 05:18 AM
control-c and threads, signals in 2.3 causing all sorts of issues Srikanth Mandava Python 1 02-19-2004 12:41 PM



Advertisments