The proper idiom for sorting objects in a list by an arbitrary property

maxm maxm at normik.dk
Tue Sep 11 16:43:35 CEST 2001


> And well indeed you do -- the decorate-sort-undecorate idiom
> that you use is invariably best.

I found a paper by Guido, after writing the sort routine. It seems that he
came to practically the same solution.

I wrote a few solutions, and it seems that Guidos is slightly faster than my
original method.:

regards Max M

Well it doesn't seem as important as what's happening in New York and
Washington right now. So I think I will go home. :-(

----------------------------------------------------------------------------


def sort(objects, sortAttrib):
    # makes a list of tuples ('value of sortatrib', 'index')
    sortValues = [(getattr(objects[i], sortAttrib), i)
                  for i in range(len(objects))]
    sortValues.sort(), # Sorts by first value in tuple
    return [objects[sortTuple[1]] for sortTuple in sortValues]



def sort2(objects, sortAttrib):

    global _sortBy
    _sortBy = sortAttrib

    def sortByParam(val1, val2):
        global _sortAttrib
        attrib1 = getattr(val1, _sortBy)
        attrib2 = getattr(val2, _sortBy)
        if  attrib1 < attrib2:
            return -1
        elif attrib1 > attrib2:
            return 1
        return 0

    objects.sort(sortByParam)
    return objects



def sort3(objects, sortAttrib):
    nlist = map(lambda object, sortAttrib=sortAttrib:
                (getattr(object, sortAttrib), object), objects)
    nlist.sort()
    return map(lambda (key, object): object, nlist)



class my:
    def __init__(self, id, title):
        self.id    = id
        self.title = title



import time, random



for n in [100, 1000, 10000, 20000, 30000, 100000]: #

    # Make shure they sort the same list
    theList = [my(random.random(), 'xxx') for i in range(n)]

    print n, 'objects in list'
    start1 = time.time()
    sort(theList[:], 'id')
    end1 = time.time()
    print 'test1: ', end1-start1

    start2 = time.time()
    sort2(theList[:], 'id')
    end2 = time.time()
    print 'test2: ', end2-start2

    start3 = time.time()
    sort3(theList[:], 'id')
    end3 = time.time()
    print 'test3: ', end3-start3

    print ''



----------------------------------------------------------------------------



100 objects in list
test1:  0.00999999046326
test2:  0.0
test3:  0.0

1000 objects in list
test1:  0.0600000619888
test2:  0.0699999332428
test3:  0.0199999809265

10000 objects in list
test1:  1.09200000763
test2:  1.07099997997
test3:  0.480999946594

20000 objects in list
test1:  0.901000022888
test2:  2.28299999237
test3:  0.72100007534

30000 objects in list
test1:  1.44200003147
test2:  3.56499993801
test3:  1.38199996948

100000 objects in list
test1:  5.96799993515
test2:  13.6000000238
test3:  4.78700006008





More information about the Python-list mailing list