sorting a list of objects using one of their methods?

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

Re: sorting a list of objects using one of their methods?

Grady Weyenberg wrote:

> 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".)

--
John

Arachnids near Coyolillo - part 1
http://johnbokma.com/mexit/2006/05/04/arachnids-coyolillo-1. html

Re: sorting a list of objects using one of their methods?

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

Re: sorting a list of objects using one of their methods?

>>>>> "FK" == Florian Kaufmann writes:

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

--
Uri Guttman ------ uri@stemsystems.com -------- http://www.sysarch.com --
----- Perl Architecture, Development, Training, Support, Code Review ------
----------- Search or Offer Perl Jobs ----- http://jobs.perl.org ---------
--------- Gourmet Hot Cocoa Mix ---- http://bestfriendscocoa.com ---------

Re: sorting a list of objects using one of their methods?

Uri Guttman wrote:

>>>>>> "FK" == Florian Kaufmann writes:
>
> 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.

--
John

Arachnids near Coyolillo - part 1
http://johnbokma.com/mexit/

Re: sorting a list of objects using one of their methods?

>>>>> "JB" == John Bokma writes:

JB> Uri Guttman wrote:
>>>>>>> "FK" == Florian Kaufmann writes:
>>
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).

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

--
Uri Guttman ------ uri@stemsystems.com -------- http://www.sysarch.com --
----- Perl Architecture, Development, Training, Support, Code Review ------
----------- Search or Offer Perl Jobs ----- http://jobs.perl.org ---------
--------- Gourmet Hot Cocoa Mix ---- http://bestfriendscocoa.com ---------

Re: sorting a list of objects using one of their methods?

Uri Guttman wrote:

>>>>>> "JB" == John Bokma writes:
>
> JB> Uri Guttman wrote:
> >>>>>>> "FK" == Florian Kaufmann writes:
> >>
> 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).
>
> 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)).

--
John

http://johnbokma.com/mexit/

Re: sorting a list of objects using one of their methods?

>>>>> "JB" == John Bokma writes:

JB> Uri Guttman wrote:
>>>>>>> "JB" == John Bokma writes:
>>
JB> Uri Guttman wrote:
>> >>>>>>> "FK" == Florian Kaufmann writes:
>> >>
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.
^^^^^^^^^^^^^^^^^


>> not to be annoying, what is your point?

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.

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

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

--
Uri Guttman ------ uri@stemsystems.com -------- http://www.sysarch.com --
----- Perl Architecture, Development, Training, Support, Code Review ------
----------- Search or Offer Perl Jobs ----- http://jobs.perl.org ---------
--------- Gourmet Hot Cocoa Mix ---- http://bestfriendscocoa.com ---------

Re: sorting a list of objects using one of their methods?

Uri Guttman wrote:

>>>>>> "JB" == John Bokma writes:

[..]

> >> >> n*log(n), FK> name would be called log(n) per object.


[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.

--
John

http://johnbokma.com/

Re: sorting a list of objects using one of their methods? RESOLVED

On Wed, 23 Jan 2008 19:09:08 +0000, John Bokma wrote:
>
> 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