Python：优化大数组间元素出现次数统计的方法

我写了一段脚本，用来统计array_1中各元素在array_2里出现的次数总和，代码如下：

array_1 = [1,2,0,5,7,0]
array_2 = [1,0,1,1,9,6]
# array_2中1出现3次，0出现1次；由于array_1中有两个0，因此累加两次，总和为3+2=5
total_count = 0
for r in array_1:
    total_count = total_count + array_2.count(r)
print("total sum: {0}".format(total_count))

这段脚本处理小数组的时候没问题，但当array_1和array_2的规模达到100万级时，性能就变得很差了。有没有更优的实现方案？

这问题我之前处理大数据量的时候也碰到过！原代码性能拉胯的核心原因是每次调用array_2.count(r)都要遍历整个array_2，如果array_1有100万元素，array_2也有100万，那时间复杂度就是O(n*m)，相当于要做10^12次操作，肯定慢得离谱。

最优的思路是先给array_2做一次预统计，把每个元素的出现次数存到一个字典（或者专门的计数结构）里，之后遍历array_1的时候直接查表就行，这样时间复杂度就降到O(n+m)，百万级数据处理起来毫无压力。

具体实现可以用Python标准库的collections.Counter，它专门用来做元素计数，代码如下：

from collections import Counter

array_1 = [1,2,0,5,7,0]
array_2 = [1,0,1,1,9,6]

# 先统计array_2中所有元素的出现次数，只需要遍历一次array_2
count_map = Counter(array_2)

total_count = 0
for r in array_1:
    # 直接查表，不存在的元素默认返回0，不用额外处理
    total_count += count_map.get(r, 0)

print("total sum: {0}".format(total_count))

如果不想引入标准库，自己用字典实现也很简单：

array_1 = [1,2,0,5,7,0]
array_2 = [1,0,1,1,9,6]

count_map = {}
for num in array_2:
    count_map[num] = count_map.get(num, 0) + 1

total_count = 0
for r in array_1:
    total_count += count_map.get(r, 0)

print("total sum: {0}".format(total_count))

这两种方案的核心都是预统计+查表，把重复遍历array_2的开销砍掉，百万级数据的处理速度会提升好几个数量级。

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