如何对具有两个关键字的列表进行排序,但其中一个按相反顺序排序?

69
我在想,对于一个包含元组的列表,如何用Pythonic的方式按照两个键进行排序,其中一个(且仅一个)键的排序是反向的,另一个键则是不区分大小写。 更具体地说,我有一个包含元组的列表,例如:
myList = [(ele1A, ele2A),(ele1B, ele2B),(ele1C, ele2C)]
我可以使用以下代码按两个键排序:
sortedList = sorted(myList, key = lambda y: (y[0].lower(), y[1]))

我可以使用以下方式以相反的顺序排序

sortedList = sorted(myList, key = lambda y: (y[0].lower(), y[1]), reverse = True)

但如果使用两个键进行排序,则会按相反的顺序排序。


1
特殊情况(所有键都应按相同顺序排序)是python-通过多个属性对列表进行排序?-堆栈溢出 - 尽管它还有一些评论解释如何按不同的顺序排序。 - user202729
8个回答

70

当我们需要按照两个限制条件对列表进行排序时,将使用两个键:一个按升序排列,另一个按降序排列,在同一列表或任何列表中。

在您的示例中,

sortedList = sorted(myList, key = lambda y: (y[0].lower(), y[1]))

你只能用一种顺序对整个列表进行排序。

您可以尝试这些,并检查发生了什么:

sortedList = sorted(myList, key = lambda y: (y[0].lower(), -y[1]))
sortedList = sorted(myList, key = lambda y: (-y[0].lower(), y[1]))
sortedList = sorted(myList, key = lambda y: (-y[0].lower(), -y[1]))

12
这只适用于数字列表?原帖作者没有说明元素的类型。 - chrisinmtown
3
@black-panda 给出的回答适用于所有数据类型,包括可比较的对象类型,并且是一个更好的回答。 - Colin 't Hart
1
太聪明了,谢谢。 - David

61
你可以创建一个反转器类并使用它来装饰所需的键。该类可用于反转任何可比较的字段。
class reversor:
    def __init__(self, obj):
        self.obj = obj

    def __eq__(self, other):
        return other.obj == self.obj

    def __lt__(self, other):
        return other.obj < self.obj

使用方法如下:

sortedList = sorted(myList, key=lambda y: (y[0].lower(), reversor(y[1])))

10
这个解决方案可用于字符串或其他对象。它比被标记为最佳解决方案的那个更加简洁。 - Tim Givois
最好使用functools.total_ordering进行装饰:https://docs.python.org/3/library/functools.html#functools.total_ordering - kaya3
4
在使用Python中的sorted函数时,将总排序作为键参数是不必要的。你只需要使用==和<运算符即可。 - black panda
绝对是最好的答案。对于新手来说,如果你正在处理字典列表,请使用y[<key>]。对于对象列表,请使用y.<property> - Timothy C. Quinn
2
None周围的所有繁琐操作是怎么回事?似乎在这种方法中根本不应该处理它。 - juanpa.arrivillaga
显示剩余2条评论

6
使用Python 3时,@KellyBundy做出了一个很好的观察:当前python文档中列出的多重排序方法非常快,并且可以用于实现具有离散排序的多列排序。这是一个NoneType安全版本:
students = [
     {'idx': 0, 'name': 'john', 'grade': 'A', 'attend': 100}
    ,{'idx': 1, 'name': 'jane', 'grade': 'B', 'attend': 80}
    ,{'idx': 2, 'name': 'dave', 'grade': 'B', 'attend': 85}
    ,{'idx': 3, 'name': 'stu' , 'grade': None, 'attend': 85}
]

def key_grade(student):
    grade = student['grade']
    return grade is None, grade
def key_attend(student):
    attend = student['attend']
    return attend is None, attend
students_sorted = sorted(students, key=key_attend)
students_sorted.sort(key=key_grade, reverse=True)

注意:

  • <variable> 的值为 None,检查是一种防御性检查,以使搜索不会在 None 值上失败
  • 虽然这做了多次排序调用,但它是最快的多重排序方法!

我创建了一个名为 multisort 的新 Python 项目,其中包含三种方法:

方法 描述 注释 速度
multisort 简单的一行代码,设计来自于multisortpython文档中的示例 速度是其中最快的,但是最可配置和易于阅读。 0.0035
cmp_func 在模型java.util.Comparator中进行多列排序 速度合理 0.0138
reversor 反转器的实现 - 参见Black Panda的答案 方法相当慢 0.0370

参考资料:

方法 速度
KellyBundy的Multisort 0.0005
pandas 0.0079

注意:速度是针对具有4列的1000行运行10次的平均值。

来自multisort示例:

from multisort import multisort
rows_sorted = multisort(rows_dict, [
        ('grade', True, lambda s:None if s is None else s.upper()),
        'attend',
], reverse=True)

然而,对于从Java转入的开发者来说,这里有一个类似于Python 3中使用的java.util.Comparator的例子:

from multisort import cmp_func

def cmp_student(a,b):
    k='grade'; va=a[k]; vb=b[k]
    if va != vb:
        if va is None: return -1
        if vb is None: return 1
        return -1 if va > vb else 1
    k='attend'; va=a[k]; vb=b[k]; 
    if va != vb:
        return -1 if va < vb else 1
    return 0

students_sorted = sorted(students, key=cmp_func(cmp_student))

我刚刚尝试了实际的多种排序方法,它比你的方法(使用你项目中的代码构建“students”)快约4.6倍。链接 - Kelly Bundy
@KellyBundy - 很有趣,我会以这种方法为思路进行一些测试。你能在multisort仓库中提出一个问题,并附上你的测试代码吗?非常感谢。 - Timothy C. Quinn
使用不同的密钥,速度提高了5.7倍。 - Kelly Bundy
6.5倍的速度 :-). 我也尝试了这个优化方法,但实际上它使速度更慢了。 - Kelly Bundy
哦,我刚看到在存储库中提出问题的请求。现在不太想这样做。请随意使用我的代码自行解决问题/按照您的需求使用。 - Kelly Bundy
显示剩余6条评论

4
有时候,使用比较函数是很少有替代选择的。在Python 2.4引入了sortedcmp参数,但在Python 3中被删除,而更高效的key函数则被取代。在Python 3.2中,functools库中添加了cmp_to_key函数;它通过将对象包装在一个基于cmp函数的比较函数上的对象中来创建原始对象的键。(您可以在排序指南结尾处看到cmp_to_key函数的简单定义)
在您的情况下,由于小写操作相对较昂贵,您可能需要组合使用:
class case_insensitive_and_2nd_reversed:
    def __init__(self, obj, *args):
        self.first = obj[0].lower()
        self.second = obj[1]
    def __lt__(self, other):
        return self.first < other.first or self.first == other.first and other.second < self.second
    def __gt__(self, other):
        return self.first > other.first or self.first == other.first and other.second > self.second
    def __le__(self, other):
        return self.first < other.first or self.first == other.first and other.second <= self.second
    def __ge__(self, other):
        return self.first > other.first or self.first == other.first and other.second >= self.second
    def __eq__(self, other):
        return self.first == other.first and self.second == other.second
    def __ne__(self, other):
        return self.first != other.first and self.second != other.second

sortedList = sorted(myList, key = case_insensitive_and_2nd_reversed)

4

方法一

一个简单的解决方案,但可能不是最有效的方法是进行两次排序:第一次使用第二个元素进行排序,第二次使用第一个元素进行排序:

sortedList = sorted(sorted(myList, key=lambda (a,b):b, reverse=True), key=lambda(a,b):a)

或者分解:
tempList = sorted(myList, key=lambda (a,b):b, reverse=True)
sortedList = sorted(tempList, key=lambda(a,b):a))

方法二

如果您的元素是数字,您可以稍微作弊一下:

sorted(myList, key=lambda(a,b):(a,1.0/b))

第三种方法

我建议不采用这种方法,因为这样做很混乱,在Python 3 中没有cmp关键字。

另一种方法是在比较元素时交换它们:

def compare_func(x, y):
    tup1 = (x[0], y[1])
    tup2 = (x[1], y[0])
    if tup1 == tup2:
        return 0
    elif tup1 > tup2:
        return 1
    else:
        return -1

sortedList = sorted(myList, cmp=compare_func)

或者使用lambda避免编写函数:

sortedList = sorted(
    myList,
    cmp=lambda (a1, b1), (a2, b2): 0 if (a1, b2) == (a2, b1) else 1 if (a1, b2) > (a2, b1) else -1
    )

2
方法2对零不起作用;它会引发ZeroDivisionError。我想你应该指的是-b - wjandrea

1
也许是优雅但不高效的方法:

reverse_key = functools.cmp_to_key(lambda a, b: (a < b) - (a > b))
sortedList = sorted(myList, key = lambda y: (reverse_key(y[0].lower()), y[1]))

1

基础理论

以下内容适用于内置的sorted函数和列表的.sort方法。

通常,用于排序的key函数可以简单地生成一个元组,其中每个元素对应于我们想要用于排序的“键”之一。这些元组将按字典顺序排序, 因此这会产生所需的结果-元素根据第一个键结果排序,平局由第二个键等解决。

同时,用于排序的reverse关键字参数可以指定应以相反的顺序进行排序。它相当于正常排序,然后翻转结果,但更有效率。

然而,这个reverse设置适用于整个排序。它不允许先按一个键升序排列,然后按另一个键降序排列,反之亦然。

示例设置

可以对包含任何类型对象的列表进行排序,而不仅仅是嵌套的列表/元组;并且可以编写处理这些对象的键函数,以任何方式处理这些对象 - 例如,根据特定属性的值对类的实例进行排序。为了清晰起见(即为了使用属性名称),我将设置一个简单的namedtuple并演示对实例列表进行排序的技巧。

from collections import namedtuple
datum = namedtuple('datum', 'id age first last')
data = [
    datum(1, 23, 'Foo', 'Bar'),
    datum(2, 42, 'Baz', 'Quux'),
    # etc.
]

特殊情况:按两个数字键排序

为了模拟反向排序,只需取一个数值的负值。因此:

# sort ascending by id, then descending by age
data.sort(key=lambda d: (d.id, -d.age))
# equivalent, but more complex:
data.sort(key=lambda d: (-d.id, d.age), reverse=True)

特殊情况:按最多一个非数字键排序

如果只有一个非数字键,则选择是否使用reverse可以避免仅数字键可以以这种方式取反的问题:

# sort ascending by first name, then descending by id
data.sort(key=lambda d: (d.first, -d.id))
# sort ascending by age, then descending by last name
# since the name can't be negated, `reverse` is needed;
# this implies in turn that the age values should be negated.
data.sort(key=lambda d: (-d.age, d.last), reverse=True)

使用包装类来取反值

一个更通用的方法是创建一个包装类negated,语义为negated(x) < negated(y)当且仅当x >= y。这是在black panda的回答中采用的方法。因此:

class negated: # name changed; otherwise the same
    def __init__(self, obj):
        self.obj = obj

    def __eq__(self, other):
        return other.obj == self.obj

    def __lt__(self, other):
        return other.obj < self.obj

# Sort descending by last name, then ascending by first name.
data.sort(lambda d: (negated(d.last), d.first))

更为复杂:适应函数而非值

假设存在某个现有的关键函数 my_key,我们想要按其结果降序排序,然后按其他某个关键字升序排序。我们可以像这样调整它,而不是重写 my_key

def negated_result(func):
    return lambda x: negated(func(x))

# Which now allows:
data.sort(lambda d: (negated_result(my_key)(d), d.id))

negated_result 接受一个函数并返回一个函数,因此它也可以用作装饰器。

如果一切都失败了:按键重复排序

由于 Python 的内置排序是稳定的保证,我们可以简单地按第二个键排序,然后按第一个键排序:

# Sort "by my_key descending, then id ascending", by doing the steps
# the other way around.
data.sort(lambda d: d.id)
data.sort(my_key, reverse=True)

这个想法是在应用主排序的同时保留子排序。但是要记住以相反的顺序执行这个操作有点棘手,因此可能需要一个包装函数。例如:

# Use the `operator` module to avoid writing lambdas for simple accesses.
# This is not much simpler, but arguably more explicit.
from operator import attrgetter

# Give the sort orderings nicer names.
# See: https://dev59.com/4Y3da4cB1Zd3GeqPwC7-
from enum import Flag

class SortOrder(Flag):
    DESCENDING = True
    ASCENDING = False

def multi_sort(a_list, *specs):
    '''Sort by multiple, optionally reversed keys.
    specs -> a sequence of (func, bool) tuples.
             Each tuple specifies a key func to use for sorting,
             and whether or not to reverse the sort.'''
    for key, reverse in reversed(specs):
        # The enum value must be converted explicitly to work.
        a_list.sort(key=key, reverse=bool(reverse))

# Now the same sort looks like:
multi_sort(
    data, 
    (my_key, SortOrder.DESCENDING),
    (attrgetter('id'), SortOrder.ASCENDING)
)

我不理解 negated_result 的意义所在。为什么不直接这样做 data.sort(lambda d: (negated(my_key(d)), d.id)) - wjandrea
“这相当于正常排序,然后反转结果”,这是不正确的;这样做不会稳定,实际上会颠倒结果。例如,L = [1, 0, 1.0]sorted(L, reverse=True)[1, 1.0, 0],而 sorted(L)[::-1][1.0, 1, 0] - wjandrea
为了反转结果并保持稳定性,在排序之前您需要先反转输入。 - wjandrea
@wjandrea,全文都有很好的观点。我看到了一些其他的错别字,我会把这个问题加入到我的待办事项清单中去。 - Karl Knechtel

0

至少在我的情况下,我可以简单地调用X.sort()两次,参数不同,一次是反向排序,另一次不是。我只需要注意排序的优先级 - 将优先级较高的排序放在最后。

例如,我有一个字符串列表,我想按长度从长到短排序,如果字符串长度相同,则按字母顺序排序。
这可以翻译为:

lst = ["Bbbb", "Aaaa", "Ddd", "Cc"]
lst.sort()  # no extra arguments necessary for alphabetical sorting
# lst = ["Aaaa", "Bbbb", "Cc", "Ddd"]
lst.sort(key=len, reverse=True) # sort by length, which is higher priority, so last
# lst = ["Aaaa", "Bbbb", "Ddd", "Cc"]

一般来说,这是可能的,因为内置排序的稳定性得到了保证。 - Karl Knechtel

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接