Python判断列表A存在元素小于列表B元素的更优写法及一行实现

给定两个存储整数的列表A和B，判断规则为：若列表A中至少存在一个元素小于列表B中至少一个元素则返回True，否则返回False。

运行示例 #

>>> A = [1,4]
>>> B = [0,2]
>>> compare_lists(A, B) # True 因为A中的1小于B中的2

>>> A = [2,4]
>>> B = [0,2]
>>> compare_lists(A, B) # False 因为A中所有元素都大于等于B中所有元素

原始实现 #

最直接的双重循环实现如下：

def compare_lists(a, b):
    for i in a:
        for j in b:
            if i < j:
                return True
    return False

1. 完全等价原始逻辑的写法 #

用Python内置的any()函数配合生成器表达式即可实现和原始实现完全一致的短路逻辑，代码如下：

def compare_lists(a, b):
    return any(i < j for i in a for j in b)

• 说明：any()会迭代生成器的结果，只要遇到第一个为True的结果就立刻返回，和原始双重循环的提前返回逻辑完全一致，没有额外性能损耗。

2. 性能优化版写法 #

实际上原始双重循环的性能还有很大优化空间，我们可以通过比对两个列表的极值直接得到结果，时间复杂度从O(n*m)降低到O(n+m)，一行实现如下：

def compare_lists(a, b):
    return min(a) < max(b)

• 说明：逻辑依据是只要A的最小元素小于B的最大元素，就必然存在至少一个A的元素小于至少一个B的元素；反之如果A的最小元素都大于等于B的最大元素，那么所有A元素都大于等于所有B元素，完全符合题目要求的判断规则。

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