Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > sorting a list of objects using one of their methods?

Reply
Thread Tools

sorting a list of objects using one of their methods?

 
 
Grady Weyenberg
Guest
Posts: n/a
 
      01-23-2008
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

 
Reply With Quote
 
 
 
 
John Bokma
Guest
Posts: n/a
 
      01-23-2008
Grady Weyenberg <(E-Mail Removed)> 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/0...yolillo-1.html
 
Reply With Quote
 
 
 
 
Florian Kaufmann
Guest
Posts: n/a
 
      01-23-2008
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/Schwart...nsform#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
 
Reply With Quote
 
Uri Guttman
Guest
Posts: n/a
 
      01-24-2008
>>>>> "FK" == Florian Kaufmann <(E-Mail Removed)> 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/Schwart...nsform#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 ------ http://www.velocityreviews.com/forums/(E-Mail Removed) -------- 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 ---------
 
Reply With Quote
 
John Bokma
Guest
Posts: n/a
 
      01-24-2008
Uri Guttman <(E-Mail Removed)> wrote:

>>>>>> "FK" == Florian Kaufmann <(E-Mail Removed)> 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/Schwart...nsform#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/
 
Reply With Quote
 
Uri Guttman
Guest
Posts: n/a
 
      01-24-2008
>>>>> "JB" == John Bokma <(E-Mail Removed)> writes:

JB> Uri Guttman <(E-Mail Removed)> wrote:
>>>>>>> "FK" == Florian Kaufmann <(E-Mail Removed)> 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/Schwart...nsform#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 ------ (E-Mail Removed) -------- 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 ---------
 
Reply With Quote
 
John Bokma
Guest
Posts: n/a
 
      01-24-2008
Uri Guttman <(E-Mail Removed)> wrote:

>>>>>> "JB" == John Bokma <(E-Mail Removed)> writes:

>
> JB> Uri Guttman <(E-Mail Removed)> wrote:
> >>>>>>> "FK" == Florian Kaufmann <(E-Mail Removed)> 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/Schwart...nsform#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/
 
Reply With Quote
 
Uri Guttman
Guest
Posts: n/a
 
      01-24-2008
>>>>> "JB" == John Bokma <(E-Mail Removed)> writes:

JB> Uri Guttman <(E-Mail Removed)> wrote:
>>>>>>> "JB" == John Bokma <(E-Mail Removed)> writes:

>>

JB> Uri Guttman <(E-Mail Removed)> wrote:
>> >>>>>>> "FK" == Florian Kaufmann <(E-Mail Removed)> 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/Schwart...nsform#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 ------ (E-Mail Removed) -------- 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 ---------
 
Reply With Quote
 
John Bokma
Guest
Posts: n/a
 
      01-24-2008
Uri Guttman <(E-Mail Removed)> wrote:

>>>>>> "JB" == John Bokma <(E-Mail Removed)> 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/
 
Reply With Quote
 
Grady Weyenberg
Guest
Posts: n/a
 
      01-25-2008
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

 
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
help sorting objects by their instance field Aaron Haas Ruby 13 11-13-2010 11:15 PM
Sorting list vs sorting vector boltar2003@boltar.world C++ 2 07-06-2010 09:40 AM
Since MSN CHAT went pay per use. Is their any other free ones out their Hugh Computer Support 8 05-19-2004 05:52 PM
What the pros use to power their flashes... and their digital cameras. Dan Sullivan Digital Photography 21 01-04-2004 04:40 PM
Stop Spammers by Hitting Their Servers - Not Their Email. Magic347 Computer Support 27 07-03-2003 04:36 PM



Advertisments