如何对不同类型的列表进行排序？

Question

我需要使用Python 3对一个列表进行排序。该列表可能包含字符串、整数、浮点数或元组等。

我目前正在尝试正确使用sort函数，并使用key参数，如下所示：

data.sort(key=gen_key)

...

def gen_key(self, value):
        if is_number(value):
            return str(value)

        if isinstance(value, str):
            return value
    return '___' + type(value).__name__

但问题在于数字现在将以自然方式排序。虽然我希望仍将数字和浮点数按照数字和浮点数的方式进行排序，而不是将它们视为字符串。

这种行为是由return str(value)部分引起的。但我不能返回与字符串不同的类型，因为这会引发异常。从Python 3开始，字符串不会像在Python 2中那样与数字一起排序。异常如下：

unordarable types: int() < str()

你有什么建议吗？

- Iwan1993

---

你期望得到什么结果？你希望如何对字符串和元组进行排序？ - jprockbelly

你希望'A'和13按照什么顺序排序呢？你需要定义一个明确的排序规则。一旦完成了这个步骤，你基本上已经完成了。 - Henry Keiter

Answer 1

关键是让你的key函数返回一个元组，其中第一个索引具有可比较的类型保证，后续索引具有不同的类型。

虽然不完全与Python 2相同，但对于特定情况而言，“数字放到前面，其他按类型名称比较”可以通过合理高效的key函数实现。

>>> from numbers import Number
>>> seq = ['Z', 3, 'Y', 1, 'X', 2.5, False, (1, 2), [2, 3], None]
>>> sorted(seq, key=lambda x: (x is not None, '' if isinstance(x, Number) else type(x).__name__, x))
[None, False, 1, 2.5, 3, [2, 3], 'X', 'Y', 'Z', (1, 2)]

在这里，key函数使得key的第一个元素成为一个简单的bool，强制None在所有其他元素之前排序（Py2也是如此），然后通过使用空字符串作为key的第二部分来首先排序所有数值类型，而其他所有类型都使用它们的类型名称进行排序（与Py2一样）。一旦你通过了前两个索引，剩下的都是相同类型，并且应该可以正常比较。

这里的主要缺陷是可比较的非数值类型（如set和frozenset）不能相互比较，它们仅按typename排序（使用异常的自定义键类可以处理这种情况）。

它还无法处理递归的情况；如果序列包含[2, 3]和['a', 'b']，则将出现TypeError，比较2和'a'，但除非使用过于复杂的键类，否则无法处理该问题。

如果这不是一个问题，这是一个运行廉价而相对简单的方法。

与涉及自定义类并定义__lt__以执行比较的解决方案不同，这种方法具有生成内置键的优点，在排序期间最小化执行Python级别代码的效率比较高。

时间记录：

 # Multiply out the sequence so log n factor in n log n work counts for something
 >>> seq = ['Z', 3, 'Y', 1, 'X', 2.5, False, (1, 2), [2, 3], None] * 100

 # Verify equivalence
 >>> sorted(seq, key=Py2Key) == sorted(seq, key=lambda x: (x is not None, '' if isinstance(x, Number) else type(x).__name__, x))
 True

 # Timings in seconds for the fastest time (of 3 trials) to run the sort 1000 times:
 >>> import timeit

 # Py2Key class
 >>> min(timeit.repeat('sorted(seq, key=Py2Key)', 'from __main__ import seq, Py2Key', number=1000))
 5.251885865057375

 >>> min(timeit.repeat('sorted(seq, key=lambda x: (x is not None, "" if isinstance(x, Number) else type(x).__name__, x))', 'from __main__ import seq, Number', number=1000))
 1.9556877178131344

基本上，避免使用Python动态层面的 __lt__ 带来了超过60％的运行时时间缩短。这似乎不是算法改进（一个长度为 100 倍的 seq 具有相同的运行时比率），只是固定开销的减少，但这是一个非常重要的减少。

- ShadowRanger

---

你能否扩展这种方法，使用用户定义的键。例如，可迭代对象可能由字典组成，用户希望按特定字典键进行排序 key=lambda x: x['mykey']，并且与上述相同，与 x[mykey] 相关联的值可能是混合类型的。我想知道你的 lambda 是否可以后置组合。我会尝试一下。 - alancalvitti

看起来没问题：seqd = [{'a':x} for x in seq]。然后是sorted(seqd,key = lambda x: type_markup(x['a']))，其中type_markup是你的lambda函数。 - alancalvitti

Answer 2

最干净的方法是使用一个对象作为排序键，该对象在其比较方法中包含所需的排序行为。Python 排序所需的唯一比较方法是 __lt__()，因此这是相当直接的。

例如，下面是一个类，大致实现了 Python 2 的排序启发式（按值对可比较对象组进行排序）。您当然可以实现任何其他规则。由于排序将为列表中的每个项创建一个这样的对象，因此我通过使用 __slots__ 并将所有类型字符串放入池中，尽可能地减小了每个对象的大小。

from sys import intern

class Py2Key:

    __slots__ = ("value", "typestr")

    def __init__(self, value):
        self.value   = value
        self.typestr = intern(type(value).__name__)

    def __lt__(self, other):
        try:
            return self.value < other.value
        except TypeError:
            return self.typestr < other.typestr

使用方法：

seq = ["Z", 3, "Y", 1, "X", 2.5, False]
sorted(seq, key=Py2Key)
>>> [False, 1, 2.5, 3, 'X', 'Y', 'Z']

不幸的是，在Python 3中实现Python 2的排序行为将比Python 2更慢且更占用内存，尤其是因为我们利用了异常处理。这是否在应用程序中可接受由您决定。

- kindall