ActiveState Code

Recipe 52230: Fast sort the list of objects by object's attribute

Fast sorting the list of objects by object's attribute using the "Schwartzian transform". Since this recipe uses _only_ builtins and doesn't use explicit looping, this is quite fast. Besides, it doesn't use any Python 2.0-specific features (such as zip() or list comprehensions) so can be used for Python 1.5.2/1.6 as well.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def sort_by_attr(seq, attr):
    """Sort the sequence of objects by object's attribute

    Arguments:
    seq  - the list or any sequence (including immutable one) of objects to sort.
    attr - the name of attribute to sort by

    Returns:
    the sorted list of objects.
    """
    import operator

    # Use the "Schwartzian transform"
    # Create the auxiliary list of tuples where every i-th tuple has form
    # (seq[i].attr, i, seq[i]) and sort it. The second item of tuple is needed not
    # only to provide stable sorting, but mainly to eliminate comparison of objects
    # (which can be expensive or prohibited) in case of equal attribute values.
    intermed = map(None, map(getattr, seq, (attr,)*len(seq)), xrange(len(seq)), seq)
    intermed.sort()
    return map(operator.getitem, intermed, (-1,) * len(intermed))

def sort_by_attr_inplace(lst, attr):
    """Inplace sort the list of objects by object's attribute
    """
    lst[:] = sort_by_attr(lst, attr)

Comments

  1. 1. At 8:47 p.m. on 5 jul 2001, Nick Perkins said:

    Using list comprehensions: Original version uses map(None,...

    def sort_by_attr(seq, attr):
    intermed = map(None, map(getattr, seq, (attr,)*len(seq)), xrange(len(seq)), seq)
    intermed.sort()
    return map(operator.getitem, intermed, (-1,) * len(intermed))

    This one uses list comprehensions instead..

    def sort_by_attr2(seq,attr):
    intermed = [ (getattr(seq[i],attr), i, seq[i]) for i in xrange(len(seq)) ]
    intermed.sort()
    return [ tup[-1] for tup in intermed ]

Sign in to comment