sorting a list of objects using one of their methods?

[Grady Weyenberg]

Hi,

I have @list=($obj_1,$obj_2,...) where each $obj, although of different
classes, have a common inherited method, $obj->name.

I am trying to sort @list alphabetically using the value of $obj->name.
I have tried

@list = sort {$a->name cmp $b->name} @list;

but this fails with:
'Can't call method "name" without a package or object reference.'
and I'm not sure how to pass a reference in this context.

Will this be possible using Perl's sort directly on the object list, or
will I need to write my own sorting function?

Thanks,
Grady

 

[John Bokma]

Hi,

I have @list=($obj_1,$obj_2,...) where each $obj, although of different
classes, have a common inherited method, $obj->name.

I am trying to sort @list alphabetically using the value of $obj->name.
I have tried

@list = sort {$a->name cmp $b->name} @list;

but this fails with:
'Can't call method "name" without a package or object reference.'
and I'm not sure how to pass a reference in this context.

Sounds like you don't have only objects refs in your list, try to debug
with:

for my $item ( @list ) {

print ref $item, "\n";
}

to see what you have in your list.

Will this be possible using Perl's sort directly on the object list, or
will I need to write my own sorting function?

AFAIK what you want should work, but it sounds like not all objects in
your list are actually object refs.

(Note: if your list is very long, and your name function is slow, you
might want to use a "Schwartzian Transform".)

 

[Florian Kaufmann]

I can't help you with the error message. I only have an optimization
hint once it is running: If the method call is not cheap (in terms of
runtime) and if its result (per object) is const during the sort,
consider the Schwartzian Transform: http://en.wikipedia.org/wiki/Schwartzian_transform#History.
It only calls the name subroutine once per object, whereas the naive
approach calls it many many times per object. To be more precise,
assuming that the complexity of perl's sort is n*log(n), name would be
called log(n) per object.

# untested example:

@list =
map { $_->[0] }
sort { $a->[1] cmp $b->[1]}
map { [ $_, $_->name ] }
@list;

Flo

 

[Uri Guttman]

FK> I can't help you with the error message. I only have an optimization
FK> hint once it is running: If the method call is not cheap (in terms of
FK> runtime) and if its result (per object) is const during the sort,
FK> consider the Schwartzian Transform: http://en.wikipedia.org/wiki/Schwartzian_transform#History.

FK> It only calls the name subroutine once per object, whereas the
FK> naive approach calls it many many times per object. To be more
FK> precise, assuming that the complexity of perl's sort is n*log(n),
FK> name would be called log(n) per object.

nope. name is called once per object and cached which makes it O(N). it
doesn't change the growth curve of sort but factors out the method call
so it is O(N) and not O(N * log N).

and if you want the ST or the faster GRT and don't want to deal with
coding it, use Sort::Maker which does all the work for you.

uri

 

[John Bokma]

FK> I can't help you with the error message. I only have an
optimization FK> hint once it is running: If the method call is not
cheap (in terms of FK> runtime) and if its result (per object) is
const during the sort, FK> consider the Schwartzian Transform:
http://en.wikipedia.org/wiki/Schwartzian_transform#History.

FK> It only calls the name subroutine once per object, whereas the
FK> naive approach calls it many many times per object. To be more
FK> precise, assuming that the complexity of perl's sort is
n*log(n), FK> name would be called log(n) per object.

nope. name is called once per object and cached which makes it O(N).
it doesn't change the growth curve of sort but factors out the method
call so it is O(N) and not O(N * log N).

I read FK as: naive requires O( log N) get_name calls per object. Each
comparison does 2 calls, so in total O( N * 2 * log N ) = O( N log N).

A simple test I wrote shows for:

10240 objects, shuffled, naive ~ 248, 086 calls, which is close to 10240
x 2 x log 10240.

Of course ST results in 10240 calls exactly.

 

[Uri Guttman]

FK> It only calls the name subroutine once per object, whereas the
FK> naive approach calls it many many times per object. To be more
FK> precise, assuming that the complexity of perl's sort is
JB> I read FK as: naive requires O( log N) get_name calls per object. Each
JB> comparison does 2 calls, so in total O( N * 2 * log N ) = O( N log N).

JB> A simple test I wrote shows for:

JB> 10240 objects, shuffled, naive ~ 248, 086 calls, which is close to 10240
JB> x 2 x log 10240.

JB> Of course ST results in 10240 calls exactly.

not to be annoying, what is your point? you generated numbers that
agreed with my analysis. remember that O() math is about growth rates
and not about absolute counts. yes you can save a ton of real world work
with caching of sort keys but it still won't change the growth rate.

uri

 

[John Bokma]

FK> It only calls the name subroutine once per object, whereas the
FK> naive approach calls it many many times per object. To be more
FK> precise, assuming that the complexity of perl's sort is

JB> I read FK as: naive requires O( log N) get_name calls per
object. Each JB> comparison does 2 calls, so in total O( N * 2 * log
N ) = O( N log N).

JB> A simple test I wrote shows for:

JB> 10240 objects, shuffled, naive ~ 248, 086 calls, which is close
to 10240 JB> x 2 x log 10240.

JB> Of course ST results in 10240 calls exactly.

not to be annoying, what is your point?

Uhm, your reply was unclear to me, it looked (to me) like you and FK
disagreed.

you generated numbers that
agreed with my analysis.

Heh, and what I thought all along, but your reply to FK was (again to
me) vague, especially since FK seemed to talk about the naive method in
the end, and you started with "nope. name is called once per object and
cached).

remember that O() math is about growth rates
and not about absolute counts.

Heh, teach your grandmother to suck eggs. I have a MSc.

yes you can save a ton of real world
work with caching of sort keys but it still won't change the growth
rate.

That depends on what's going on in the comparison routine, of course
(e.g. imagine get_name being O(N)).

 

[Uri Guttman]

FK> It only calls the name subroutine once per object, whereas the
FK> naive approach calls it many many times per object. To be more
FK> precise, assuming that the complexity of perl's sort is

^^^^^^^^^^^^^^^^^

JB> Uhm, your reply was unclear to me, it looked (to me) like you and FK
JB> disagreed.

look at the underlined comment from FK. that is what i didn't understand
or agree with. actually looking at it now i think he meant in the normal
sort. his wording wasn't the best IMO.

JB> Heh, teach your grandmother to suck eggs. I have a MSc.

so? you know how many people screw up O() numbers? and i was taught
algorithms by the R of RSA . and my grandmother made great chicken
soup!

JB> That depends on what's going on in the comparison routine, of course
JB> (e.g. imagine get_name being O(N)).

that of course is not a issue as the higher level sort O(N log N) will swamp
out the work in each method call. you have to consider name() to be a
constant factor for the analysis. sure if the compare is ridiculously
slow (as in something like -M on a file) it could ruin a real world
sort. but this is now way off topic and i will stop. we are not
disagreeing about anything.

uri

 

[John Bokma]

[..]

[snip]

look at the underlined comment from FK. that is what i didn't
understand or agree with. actually looking at it now i think he meant
in the normal sort. his wording wasn't the best IMO.

To me "To be more precise" talks about the naive approach.

JB> Heh, teach your grandmother to suck eggs. I have a MSc.

so? you know how many people screw up O() numbers?

Not enough to just assume everybody does.

that of course is not a issue as the higher level sort O(N log N) will
swamp out the work in each method call. you have to consider name() to
be a constant factor for the analysis.

If each get_name takes O(N), then it's no longer a constant factor. (I
can't think of any example why it would take O(N), but I've seen enough
code written by people who probably could even make it O(N^2)).

be a constant factor for the analysis. sure if the compare is
ridiculously slow (as in something like -M on a file) it could ruin a
real world sort.

Or if the number of objects is very high.

 

[Grady Weyenberg]

Sounds like you don't have only objects refs in your list, try to debug
with:

for my $item ( @list ) {

print ref $item, "\n";
}

to see what you have in your list.

(Note: if your list is very long, and your name function is slow, you
might want to use a "Schwartzian Transform".)

Thanks for the pointer and optimization tip. Turns out that my original
code worked after all, the problem was that my list was populated with
undefs due to a subtle earlier bug, but the error text mislead me. The
ref function should help me avoid that in the future.

thanks,
Grady