侧边栏壁纸
博主头像
AI研究僧

hycj89@163.com

  • 累计撰写 1,899 篇文章
  • 累计创建 179 个标签
  • 累计收到 1 条评论
标签搜索

目 录CONTENT

文章目录

使用python从一个列表中寻找不在另一个列表中的数据的方法(高性能)

AI研究僧
2019-04-03 / 0 评论 / 0 点赞 / 354 阅读 / 294 字

假设有以下两个数据集列表

a = list(range(1, 100000))
b = list(range(150000, 50000, -1))

要从a中找到不在b中的数据,常常会想直接遍历两个列表即可

a_alone = []

start = time.time()
for i in a:
    if i not in b:
        a_alone.append(i)
end = time.time()

print(end - start)  # 用时117s

可以看到效率是非常低下的,相当于O(n2)的时间复杂度

利用集合set则能大幅提高性能

a_set = set(a)
b_set = set(b)

start = time.time()
# 求差集得到的是在a里但不在b里的数据集合,a独有
# 如果a,b不是空集合,a-b为空集合,说明a中的数据全部在b中
a_alone = a_set - b_set

end = time.time()

print(end - start)  # 0.003s

效率大幅提升,相当于O(n)的时间复杂度(不清楚python的set实现机制,该处根据java中hashSet实现机制进行的推测)

集合的一些其他操作

# 求并集
c_set = a_set | b_set

# 求交集,结果集如果为空,说明两个集合没有任何数据是相同的
d_set = a_set & b_set
博主关闭了所有页面的评论