[Python知识库]Python算法 快速找到单一元素——分析算法效率

需求

给定数组vec，元素个数为（2n+1）（n为正整数）。其中，n个数据出现了两次，有一个出现了一次，把这个出现一次的数记为k，举例如下：

[0,0,1,1,2,2,3] => k=3
[1,2,3,1,4,2,3] => k=4
[9,6,3,3,9,9,6,8,8] => k=9

求函数f(vec)=k

生成随机数据用来测试

import random

def get_data(num, single):
	ret = []
	for i in range(0, num):
		ret.append(i)
		ret.append(i)
	ret.append(single)
	random.shuffle(ret)
	return ret

记录时间装饰器

import time

def test(fun):
	def real(*args, **kwargs):
		b = time.time()
		fun(*args, **kwargs)
		e = time.time()
		print(e-b)
	return real

实现1

普普通通地实现，正常思路：出现一次就加进另一个列表，再出现一次就尝试删除，若不存在就添加进去，最终应该只剩下一个元素（新列表里）

@test
def solution1(lst):
	another = [] # 临时列表,增减都在里面
	for i in lst:
		try:
			del another[another.index(i)]
		except:
			another.append(i)
	return another[0]

测试数据规模：（50000个数据，13478出现了奇数次）

data = get_data(50000, 13478)
print(solution1(data))

多次测试取平均值，大约是12~13s的样子。

分析时间消耗

空间消耗还好，这次主要看效率。
首先是try-except结构需要很大的时间开销，其间解释器内部进行了巨大地操作。
然后影响更大的是index方法，它会从头遍历越来越大的列表并定位（这也是为什么总规模扩大一倍时间却扩大很多的原因）。随着元素的增加，如果没有及时出现对子把它消除，列表会越来越大，索引需要遍历过的就越来越长，时间消耗越来越多。
最后，del和append都有一定的消耗。

改进

避免如上所述的大型时间消耗，更改思路如下：
先把列表排序，那么出现偶数次的数肯定在一起，就像这样：

[1,2,3,1,2,3,4] => [1,1,2,2,3,3,4]

这么说,只需要判断lst[n]是否等于lst[n+1](n=2k,k∈Z)
于是生成一个0,2,4,6,8,…的生成器(range函数即可，把setp改成2)，把i带进去比较上述二式值。

@test
def solution1_better(lst):
	lst.sort()
	for i in range(0, len(lst), 2):
		try:
			if lst[i] != lst [i+1]:
				return lst[i]
		except:
			return lst[i]

值得关注的点在于，这里还是要用循环里的try-except，因为如果范围给的是500，要找的数是499，i+1的索引就会越界。但是相比之下无关紧要，except的检查相关大段消耗只会在try失败的时候触发，在虚拟机内部是不需要每次循环都回溯栈、各种校验的。
测试，平均0.025s，只用了solution1时间的1.9‰，可见大幅提高。

最终算法——实现2

在lst的范围足够大的时候，上述算法都无法应对——第一种时间复杂度几何增长，第二种线性增长，都不是很理想。
下面介绍重点：位运算法。利用异或（XOR）运算的周期性，两次连续XOR同一个数，值不变，即

a ^ b = c
c ^ b = a

这个性质正好用在这个算法中。出现两次连续异或就能抵消，而且位运算不管在哪种语言里都是最快速的解决方案。

@test
def solution2(lst):
	result = 0
	for i in lst:
		result ^= i
	return result

相比之下很短小，但十分有用。
测试结果表明，当数据集跟如上两种算法相当时，或者说完全一样，solution2几乎不耗时（e-b -> 0）当然结果一定正确且能满足各种特殊情况。

加大规模，将solution1_better与solution2控制变量比较(solution1原算法太慢了无意义)。测试代码段如下：

data = get_data(1e6, 1e6-19)

print(solution1_better(data))
print(solution2(data))

目标数用最大值减去较小值是为了避免solution1_better算法过早结束,它是顺向遍历。

多次测量下，前者平均1.56s，后者稳定在0.14s，相差近十倍。

总结

二进制位运算在相同处理器的执行下效率是最高的，使用最少的时钟周期。所以在需要大规模运算的高效算法，又对时间要求特别紧张的时候，善于运用位运算能达到极佳的效果。

源码已上传至gitee