sorting a list of objects using one of their methods?

Discussion in 'Perl Misc' started by Grady Weyenberg, Jan 23, 2008.

  1. 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
     
    Grady Weyenberg, Jan 23, 2008
    #1
    1. Advertising

  2. Grady Weyenberg

    John Bokma Guest

    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
     
    John Bokma, Jan 23, 2008
    #2
    1. Advertising

  3. 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
     
    Florian Kaufmann, Jan 23, 2008
    #3
  4. Grady Weyenberg

    Uri Guttman Guest

    >>>>> "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 ------ -------- 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 ---------
     
    Uri Guttman, Jan 24, 2008
    #4
  5. Grady Weyenberg

    John Bokma Guest

    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/
     
    John Bokma, Jan 24, 2008
    #5
  6. Grady Weyenberg

    Uri Guttman Guest

    >>>>> "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 ------ -------- 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 ---------
     
    Uri Guttman, Jan 24, 2008
    #6
  7. Grady Weyenberg

    John Bokma Guest

    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/
     
    John Bokma, Jan 24, 2008
    #7
  8. Grady Weyenberg

    Uri Guttman Guest

    >>>>> "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 ------ -------- 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 ---------
     
    Uri Guttman, Jan 24, 2008
    #8
  9. Grady Weyenberg

    John Bokma Guest

    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/
     
    John Bokma, Jan 24, 2008
    #9
  10. 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
     
    Grady Weyenberg, Jan 25, 2008
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. cesco
    Replies:
    5
    Views:
    393
    Maxim Yegorushkin
    Feb 10, 2006
  2. Replies:
    2
    Views:
    1,491
    James Kanze
    Jul 6, 2010
  3. Kenneth McDonald
    Replies:
    5
    Views:
    385
    Kenneth McDonald
    Sep 26, 2008
  4. Aaron Haas
    Replies:
    13
    Views:
    295
    Michael Bostler
    Nov 13, 2010
  5. Stefan Schwarzer

    Naming future objects and their methods

    Stefan Schwarzer, Apr 14, 2012, in forum: Python
    Replies:
    2
    Views:
    307
    Stefan Schwarzer
    Apr 16, 2012
Loading...

Share This Page