Schwartzian transform for tuple in list

[Matt Nordhoff]

Chris Rebert wrote:
> On Wed, Sep 24, 2008 at 2:02 PM, David Di Biase <dave.dibiase at gmail.com> wrote:
>> Hi,
>>
>> I have a rather large list structure with tuples contained in them (it's
>> part of a specification I received) looks like so:
>> [(x1,y1,r1,d1),(x2,y2,r2,d2)...]
>>
>> The list can range from about 800-1500 tuples in size and I'm currently
>> sorting it with this:
>>
>> a_list.sort(lambda a, b: cmp(b[3], a[3]))
> 
> You'd probably be better off using the 'key' keyword argument to
> .sort(), which is made for the Schwartzian Transform:
> 
> a_list.sort(key=lambda x: x[3])
> 
> This sorts the list items by the value produced by the key function
> for each item. It's also (IIRC) faster than using a comparison
> function like you're currently doing.
> 
> Regards,
> Chris

Yes, using 'key' is faster than 'cmp'.

If you have Python 2.4 or newer, it would also be slightly faster to use
operator.itemgetter() instead of a lambda:

>>> import operator
>>> a_list.sort(key=operator.itemgetter(3))

>> I'm actually sorting it by the last value in the tuple (d2). I have been
>> researching more efficient sorting algorithms and came across Schwartzian
>> transform via these links:
>>
>> http://www.biais.org/blog/index.php/2007/01/28/23-python-sorting-efficiency
>> http://dev.fyicenter.com/Interview-Questions/Python/Can_you_do_a_Schwartzian_Transform_in_Python_.html
>>
>> I get what's happening (sorta...errr...lol)  but I'm not sure if it is more
>> efficient in my scenario, if it is then I have no idea how to implement it
>> properly :-/
>>
>> Would be great if a true expert would offer a suggestion for me...
>>
>> Thanks!
>>
>> David
--