-- Zoom.Quiet [2004-08-11 16:51:29]

# 通过两个字段来排序

2.5 Sorting by One Field, Then by Another 通过两个字段来排序

Credit: José Sebrosa

## 问题 Problem

You need to sort a list by more than one field of each item.

## 解决 Solution

Passing a comparison function to a list's sort method is slow for lists of substantial size, but it can still be quite handy when you need to sort lists that are reasonably small. In particular, it offers a rather natural idiom to sort by more than one field:

```   1 import string
2
3 star_list = ['Elizabeth Taylor', 'Bette Davis', 'Hugh Grant', 'C. Grant']
4
5 star_list.sort(lambda x,y: (
6    cmp(string.split(x)[-1], string.split(y)[-1]) or  # Sort by last name...
7    cmp(x, y)))                                       # ...then by first name
8
9 print "Sorted list of stars:"
10 for name in star_list:
11     print name
```

## 讨论 Discussion

This recipe uses the properties of the cmp built-in function and the or operator to produce a compact idiom for sorting a list over more than one field of each item.

cmp(X, Y) returns false (0) when X and Y compare equal, so only in these cases does or let the next call to cmp happen. To reverse the sorting order, simply swap X and Y as arguments to cmp.

The fundamental idea of this recipe can also be used if another sorting criterion is associated with the elements of the list. We simply build an auxiliary list of tuples to pack the sorting criterion together with the main elements, then sort and unpack the result. This is more akin to the DSU idiom:

```   1 def sorting_criterion_1(data):
2     return string.split(data)[-1]   # This is again the last name
3
4 def sorting_criterion_2(data):
5     return len(data)                # This is some fancy sorting criterion
6
7 # Pack an auxiliary list:
8 aux_list = map(lambda x: (x,
9                           sorting_criterion_1(x),
10                           sorting_criterion_2(x)),
11                star_list)
12
13 # Sort:
14 aux_list.sort(lambda x,y: (
15    cmp(x[1], y[1])  or       # Sort by criteria 1 (last name)...
16    cmp(y[2], x[2])  or       # ...then by criteria 2 (in reverse order)...
17    cmp(x, y)))               # ...then by the value in the main list
18
19 # Unpack the resulting list:
20 star_list = map(lambda x: x[0], aux_list)
21
22 print "Another sorted list of stars:"
23 for name in star_list:
24     print name
```

Of course, once we're doing decorating, sorting, and undecorating, it may be worth taking a little extra trouble to be able to call the sort step without a comparison function (the DSU idiom), which will speed up the whole thing quite a bit for lists of substantial size. After all, packing the fields to be compared in the right order in each decorated tuple and plucking out the right field again in the undecorate step is pretty simple:

```   1 # Pack a better-ordered auxiliary list:
2 aux_list = map(lambda x: (sorting_criterion_1(x),
3                           sorting_criterion_2(x),
4                           x),
5                star_list)
6
7 # Sort in a much simpler and faster way:
8 aux_list.sort(  )
9
10 # Unpack the resulting list:
11 star_list = map(lambda x: x[-1], aux_list)
```

However, this doesn't deal with the reverse order, which you can easily obtain when passing a comparison function to sort by just switching arguments to cmp. To use DSU instead, you need to pack a suitably altered value of the criterion field. For a numeric field, changing the sign is fine. In this example, the sorting_criterion_2 that needs reverse sorting is indeed a number, so our task is easy:

```   1 # Pack a better-ordered auxiliary list yielding the desired order:
2 aux_list = map(lambda x: (sorting_criterion_1(x),
3                           -sorting_criterion_2(x),
4                           x),
5                star_list)
```

For reverse sorting on a string field with DSU, you need a string-translation operation that maps each chr(x) into chr(255-x)梠r an even wider translation table for Unicode strings. It is a bit of a bother, but you only have to write it once. For example, for plain old strings:

```   1 import string
2 all_characters = string.maketrans('','')
3 all_characters_list = list(all_characters)
4 all_characters_list.reverse(  )
5 rev_characters = ''.join(all_characters_list)
6 rev_trans = string.maketrans(all_characters, rev_characters)
```

Now, if we want to reverse the first sorting criterion: 现在，如果我们想反转第一个排序的标准：

```   1 # Pack a better-ordered and corrected auxiliary list:
2 aux_list = map(lambda x: (string.translate(sorting_criterion_1(x), rev_trans),
3                           sorting_criterion_2(x),
4                           x),
5                star_list)
6
7 # Sort in a much simpler and faster way AND get just the desired result:
8 aux_list.sort(  )
9
10 # Unpack the resulting list:
11 star_list = map(lambda x: x[-1], aux_list)
```

The Reference Manual section on sequences, and the subsection on mutable sequences (such as lists).

PyCkBk-2-5 (last edited 2009-12-25 07:14:03 by localhost)

• Page.execute = 6.218s
• getACL = 0.839s
• init = 0.026s