检查列表中的所有元素是否相同

小编典典

检查列表中的所有元素是否相同

algorithm

我需要以下功能：

输入：alist

输出：

True 如果输入列表中的所有元素使用标准相等运算符求值彼此相等；
False 除此以外。

性能：当然，我不希望产生任何不必要的开销。

我认为最好：

遍历列表
比较相邻元素
和AND所有结果布尔值

但是我不确定最Pythonic的方法是什么。

缺少短路功能只会对较长的输入（超过50个元素）产生不利影响，而早期输入中的元素不相等。如果这种情况经常发生（频率取决于列表的长度），则需要短路。最好的短路算法似乎是@KennyTM
checkEqual1。但是，它为此付出了巨大的代价：

性能几乎是同类产品的20倍
入围名单的性能提高了2.5倍

如果没有出现早期输入不相等的长输入（或发生的次数很少），则不需要短路。然后，到目前为止最快的是@Ivo van der Wijk解决方案。

阅读 253

2020-07-28

共1个答案

小编典典

通用方法：

def checkEqual1(iterator):
    iterator = iter(iterator)
    try:
        first = next(iterator)
    except StopIteration:
        return True
    return all(first == rest for rest in iterator)

单线：

def checkEqual2(iterator):
   return len(set(iterator)) <= 1

也是单线的：

def checkEqual3(lst):
   return lst[1:] == lst[:-1]

这三个版本之间的区别在于：

在checkEqual2内容中必须是可哈希的。
checkEqual1并且checkEqual2可以使用任何迭代器，但checkEqual3必须接受序列输入，通常是列表或元组之类的具体容器。
checkEqual1 发现差异后立即停止。
由于checkEqual1包含更多的Python代码，因此当许多项目在开始时相等时效率较低。
由于checkEqual2和checkEqual3始终执行O（N）的复制操作，他们将需要更长的时间，如果你的大部分投入将返回FALSE。
对于checkEqual2，checkEqual3很难适应从a == b到的比较a is b。

timeit 结果，对于Python 2.7和（仅s1，s4，s7，s9应该返回True）

s1 = [1] * 5000
s2 = [1] * 4999 + [2]
s3 = [2] + [1]*4999
s4 = [set([9])] * 5000
s5 = [set([9])] * 4999 + [set([10])]
s6 = [set([10])] + [set([9])] * 4999
s7 = [1,1]
s8 = [1,2]
s9 = []

我们得到

      | checkEqual1 | checkEqual2 | checkEqual3  | checkEqualIvo | checkEqual6502 |
|-----|-------------|-------------|--------------|---------------|----------------|
| s1  | 1.19   msec | 348    usec | 183     usec | 51.6    usec  | 121     usec   |
| s2  | 1.17   msec | 376    usec | 185     usec | 50.9    usec  | 118     usec   |
| s3  | 4.17   usec | 348    usec | 120     usec | 264     usec  | 61.3    usec   |
|     |             |             |              |               |                |
| s4  | 1.73   msec |             | 182     usec | 50.5    usec  | 121     usec   |
| s5  | 1.71   msec |             | 181     usec | 50.6    usec  | 125     usec   |
| s6  | 4.29   usec |             | 122     usec | 423     usec  | 61.1    usec   |
|     |             |             |              |               |                |
| s7  | 3.1    usec | 1.4    usec | 1.24    usec | 0.932   usec  | 1.92    usec   |
| s8  | 4.07   usec | 1.54   usec | 1.28    usec | 0.997   usec  | 1.79    usec   |
| s9  | 5.91   usec | 1.25   usec | 0.749   usec | 0.407   usec  | 0.386   usec   |

注意：

# http://stackoverflow.com/q/3844948/
def checkEqualIvo(lst):
    return not lst or lst.count(lst[0]) == len(lst)

# http://stackoverflow.com/q/3844931/
def checkEqual6502(lst):
    return not lst or [lst[0]]*len(lst) == lst

2020-07-28