Python sorted排序报函数间不支持比较TypeError问题排查

问题背景 #

完成Codewars平台的Strings mix题目时遇到运行错误，原编写代码如下：

def mix(s1, s2):
    whitelist = set('abcdefghijklmnopqrstuvwxyz')
    out = []
    s1 = ''.join(sorted((c for c in s1 if c in whitelist), key = lambda c: (-s1.count(c), c)))
    s2 = ''.join(sorted((c for c in s2 if c in whitelist), key = lambda c: (-s2.count(c), c)))
    groups = sorted(list(set(s1) | set(s2)), key = lambda c: (-max([s1.count(c), s2.count(c)]), lambda v: 1 if (s1.count(v) > s2.count(v)) else 2, c))
    
    for i in groups:
        if max([s1.count(i), s2.count(i)]) <= 1:
            continue
        if s1.count(i) == s2.count(i):
            out.append('=:' + i * s1.count(i))
            continue
        if s1.count(i) > s2.count(i):
            out.append('1:' + i * s1.count(i))
            continue
        else:
            out.append('2:' + i * s2.count(i))
    
    return '/'.join(out)

代码第6行groups = sorted(...)的设计目标是按照题目规则对不同小写字母排序，为sorted()方法传入lambda生成的三元组排序key，排序优先级从高到低为：

• 取两个字符串中当前字母的最大出现次数，取反实现降序排列
• 若两字符串中当前字母的最大出现次数相同，让s1的结果优先级高于s2
• 若前述条件均相同，按字母顺序升序排列

运行测试用例时抛出如下错误：

Traceback (most recent call last):
  File "/workspace/default/tests.py", line 5, in <module>
    test.assert_equals(mix("Are they here", "yes, they are here"), "2:eeeee/2:yy/=:hh/=:rr")
  File "/workspace/default/solution.py", line 6, in mix
    groups = sorted(list(set(s1) | set(s2)), key = lambda c: (-max([s1.count(c), s2.count(c)]), lambda v: 1 if (s1.count(v) > s2.count(v)) else 2, c))
TypeError: '<' not supported between instances of 'function' and 'function'

错误原因 #

报错核心原因是排序key三元组的第二个元素传入了lambda函数对象，而非实际可比较的排序权重值。
Python对元组做排序比较时，会从第一个元素开始逐位对比：当两个待排序字母的最大出现次数（key第一个元素）相等时，解释器会尝试对比key的第二个元素，但代码中第二个元素是定义的lambda函数本身，Python原生不支持两个函数对象做大小比较，因此抛出类型错误。

除此之外原代码还存在两个问题：

• 排序优先级逻辑不完整：当两个字母在s1、s2中出现次数相等（对应前缀为=:）时，权重应该低于前缀为1:和2:的条目
• 反复调用str.count()统计字符频次，每次调用都会遍历整个字符串，时间复杂度很高

修正方法 #

1. 移除排序key第二个位置嵌套的lambda定义，直接基于当前遍历的字符c计算对应的权重数值：s1频次更高时权重取1，s2频次更高时取2，两边频次相等时取3，数值越小排序越靠前
2. 提前用计数器统计两个字符串的小写字母频次，避免重复遍历字符串

修正后的可运行代码示例：

from collections import Counter
def mix(s1, s2):
    whitelist = set('abcdefghijklmnopqrstuvwxyz')
    # 提前统计频次，过滤非小写字母
    cnt1 = Counter(c for c in s1 if c in whitelist)
    cnt2 = Counter(c for c in s2 if c in whitelist)
    out = []
    # 遍历所有出现过的小写字母
    for c in set(cnt1.keys()).union(cnt2.keys()):
        n1, n2 = cnt1.get(c, 0), cnt2.get(c, 0)
        max_n = max(n1, n2)
        if max_n <= 1:
            continue
        if n1 > n2:
            prefix, weight = '1:', 1
        elif n2 > n1:
            prefix, weight = '2:', 2
        else:
            prefix, weight = '=:', 3
        out.append( ( -max_n, weight, c, prefix + c*max_n ) )
    # 按规则排序后拼接结果
    out.sort()
    return '/'.join(item[3] for item in out)

内容的提问来源于stack exchange，提问作者pitfall24