Sorting

Sorting a sequence with the sort method is very fast for numbers and strings. If you need to perform custom sorting (e.g., a comparison of two objects), you can pass a comparison function to sort. You can also customize sorting for a class by defining a_cmp_method. However, passing a function to sort is faster than implicit use of the_cmp_method. Compare the following two lines:

PointList.sort(Point) # Uses Point._cmp_ implicitly

PointList.sort(Point._cmp_) # Trickier, but faster!

When sorting a list of objects, one trick is to find a "key" that you can sort on. The key values should be an easy-to-sort type (for example, numbers); and they should be mostly unique across list entries. The following function provides an example:

Cross-Reference def SortByKey(List,KeyMaker):

Sort a list. The parameter KeyMaker is a function that returns a key for the list element. The keys are used sort the list

# Replace each element x with (KeyMaker(x),x): TempList=map(lambda x,f=KeyMaker: (f(x),x), List)

# Tuples sorted by comparing just the first elements:

# If the first elements match, the second elements

# are compared; so if KeyMaker(x)—KeyMaker(y), then we

# *will* end up comparing x and y directly. TempList.sort()

# Get rid of the keys - replace (KeyMaker(x),x) with x:

return map(lambda(key,x):x, TempList)

For instance, I wrote code to sort a list of points according to their distance from the origin. Using SortByKey (instead of passing a function to sort) made the code roughly three times faster.

0 0

Post a comment