In-place decorate-sort-undecorate - best implementation?

Discussion in 'Python' started by Tom Anderson, Aug 3, 2005.

  1. Tom Anderson

    Tom Anderson Guest

    Subtitle: the war on temporary objects continues!

    The page on python performance tips on the python.org wiki
    (<http://wiki.python.org/moin/PythonSpeed/PerformanceTips>) suggests the
    following code for sorting a list using decorate-sort-undecorate, but
    doing it in-place:

    def sortby_inplace(somelist, n):
    somelist[:] = [(x[n], x) for x in somelist]
    somelist.sort()
    somelist[:] = [val for (key, val) in somelist]

    Doesn't the use of list comps there generate two temporary lists? Isn't
    that quite inefficient? Wouldn't it be better to use a good old fashioned
    loop?

    def sortby_inplace(somelist, n):
    for i in xrange(len(somelist)):
    somelist = (somelist[n], somelist)
    somelist.sort()
    for i in xrange(len(somelist)):
    somelist = somelist[1]

    Testing this on a 10k-element list of (float, float, float,
    float) tuples gives me a speedup of 35%. On a million-element list it's
    only 4%, but hey, who sorts million-element lists anyway?

    I don't have python 2.4; anyone care to check how they compare there? I
    used the following timer function:

    import time
    import random
    n = 10000
    r = random.random
    l = [(r(), r(), r(), r()) for i in xrange(n)]

    def time(sorter):
    l2 = []
    l2.extend(l)
    t0 = time.time()
    sorter(l2, 2)
    t1 = time.time()
    return t1 - t0

    tom

    --
    No hay banda
     
    Tom Anderson, Aug 3, 2005
    #1
    1. Advertising

  2. Tom Anderson

    Benji York Guest

    Tom Anderson wrote:
    > I don't have python 2.4; anyone care to check how they compare there? I
    > used the following timer function:


    I think on 2.4 the new "key" option to list.sort would be the fastest
    way to accomplish what you want.
    --
    Benji York
     
    Benji York, Aug 3, 2005
    #2
    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. Thomas Philips
    Replies:
    2
    Views:
    336
    Paul McGuire
    Jun 23, 2004
  2. Replies:
    10
    Views:
    624
    Xah Lee
    Sep 8, 2006
  3. Replies:
    18
    Views:
    518
    Xah Lee
    Sep 8, 2006
  4. Matthew Wilson

    Can I undecorate a function?

    Matthew Wilson, Jan 29, 2007, in forum: Python
    Replies:
    4
    Views:
    287
    Steve Holden
    Jan 29, 2007
  5. Replies:
    10
    Views:
    211
    Xah Lee
    Sep 8, 2006
Loading...

Share This Page