关于Python sorted函数双键排序及实现效率的技术问询

我尝试用以下代码通过sorted函数对文件路径列表排序：

import re
    
# Method 1
get_label = lambda x: re.search('IVsVg_([a-z])([0-9]+).dat', x).groups()
sorted(data2, key = lambda x: (get_label(x)[0], int(get_label(x)[1])))

# Method 2
sorted(data2, key = lambda x: (re.search('IVsVg_([a-z])([0-9]+).dat', x).group(1), int(re.search('IVsVg_([a-z])([0-9]+).dat', x).group(2))))

问题1：sorted函数如何处理双键排序？ #

当仅用单键排序时，列表会出现不符合预期的顺序：

a1, a10, a11, a2, a3

而用双键排序后，能得到正确顺序：

a1, a2, a3, a10, a11

解答： #

sorted的key参数支持元组这类序列作为排序依据，排序时遵循层级比较规则：

1. 优先按元组的第一个元素排序，将第一个元素相同的元素归为同一组；
2. 对每组内的元素，再按元组的第二个元素排序，以此类推。

你遇到的单键问题，是因为直接用字符串作为key时，字符串是按字符逐个ASCII码对比的：'a10'和'a2'比较时，前两位'a'相同，第三位'1'的ASCII码小于'2'，所以'a10'会排在'a2'前面。

而双键排序中，你把key拆成了(字母部分, 整数类型的数字部分)：

• 第一键保证相同字母的元素归为一组；
• 第二键把数字转成整数后比较，整数10必然大于2，所以组内会按数字大小正确排序，最终得到符合预期的顺序。

问题2：两种方法哪种效率更高？lambda函数各被调用多少次？ #

解答： #

方法1的效率明显更高，二者核心差异在于正则表达式的执行次数：

1. lambda的调用次数：sorted对列表中的每个元素，只会调用一次key对应的lambda函数，方法1和方法2的lambda调用次数完全一致，和列表元素数量相等。你朋友说的“方法1调用lambda一次、方法2两次”是误解。
2. 核心差异点：
   • 方法1中，lambda内部仅调用一次get_label(x)，也就是只执行一次re.search匹配，拿到所有分组后再拆分使用，避免了重复匹配；
   • 方法2中，lambda内部连续调用了两次re.search，每次都要重新对同一个字符串执行正则匹配、分组提取，相当于做了一倍的无用功，所以效率更低。

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