如何优化计算两未排序整数列表跨元素最大最小差值的Python函数性能

现有代码的核心性能瓶颈 #

• 冗余的全排序：原代码为了取首尾元素算最大差，对两个列表做全量排序，但最大差仅需获取两个列表的全局极值，找极值是线性时间复杂度，远低于排序的O(n log n)
• 最小差查找逻辑冗余：原代码排序后仍采用嵌套循环遍历，虽然有提前break，但最坏情况下仍是O(n*m)的比较次数，远高于线性遍历的效率
• 硬编码初始值存在隐患：原代码用固定值10000000、1000000作为初始最小差，一旦列表元素差值超过硬编码阈值会出现计算错误

具体优化方案 #

最大差值计算优化 #

跨列表的最大差值本质就是两个列表所有元素的全局最大值 - 全局最小值，无需排序即可计算：直接取两个列表各自的min、max，全局min是两个列表min的较小值，全局max是两个列表max的较大值，直接相减即可，时间复杂度仅为O(n1 + n2)。

最小差值计算优化 #

最小差值计算需要有序性支撑，因此保留排序步骤，但将原嵌套循环替换为双指针遍历，整体比较次数从O(n*m)降到O(n1 + n2)：

• 排序两个列表后，初始化两个指针分别指向两个有序列表的头部
• 每次计算当前指针指向元素的绝对差，更新全局最小差，若差为0可直接提前返回
• 将指向更小元素的指针向后移动一位（仅更小的元素移动后，才可能和另一个列表的元素更接近）
• 直到任意一个指针遍历完对应列表即可停止

代码规范优化 #

• 将硬编码的初始临时值替换为float('inf')，避免数值范围不够的问题
• 删除原代码中两个列表完全不重叠的冗余分支，该场景会被双指针逻辑自然覆盖

优化后参考代码 #

def max_and_min(seq1, seq2):
    # 计算最大差值：全局极值差，无需排序
    max_diff = max(max(seq1), max(seq2)) - min(min(seq1), min(seq2))
    
    # 计算最小差值：双指针有序遍历
    sort1 = sorted(seq1)
    sort2 = sorted(seq2)
    i = j = 0
    min_diff = float('inf')
    len1, len2 = len(sort1), len(sort2)
    
    while i < len1 and j < len2:
        diff = abs(sort1[i] - sort2[j])
        if diff == 0:
            return (max_diff, 0)
        if diff < min_diff:
            min_diff = diff
        # 移动较小值对应的指针，逼近最小差
        if sort1[i] < sort2[j]:
            i += 1
        else:
            j += 1
    return (max_diff, min_diff)

性能提升说明 #

• 整体时间复杂度从原代码最坏的O(n log n + m log m + n*m)降到O(n log n + m log m + n + m)，在列表长度较大时（比如两个列表各有1e4个元素），运行速度可提升几个数量级
• 去掉了冗余的排序、嵌套循环逻辑，同时修复了硬编码初始值的潜在bug

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