GeekTop
  • 首页
  • 关于

GeekTop

不止代码

Python 中的set, list 和 dict

Python 中的set, list 和 dict

2018年12月18日 Alex Comments 0 Comment

分析对比一下这几种数据结构查找的时间复杂度,原因是最近面试了几个人,有些开发经验,但是都没有回答的很好。

这里写一段代码对比一下:

In [1]: l = list(range(100000))

In [2]: s = set(range(100000))

In [3]: d = dict(zip(range(100000), range(100000)))

In [4]: %timeit 99999 in l
1.06 ms ± 9.94 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [5]: %timeit 99999 in s
46.4 ns ± 0.255 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [6]: %timeit d.get(99999)
115 ns ± 0.937 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

1ms = 1000000ns,可以看出,列表和集合字典的查找时间绝对不在一个量级上,特别是在数据量很大的情况下。由于在 Python 中 set 和 dict 都是通过 hash 的方式实现的,所以查找的时间复杂度是 O(1),而字典的时间复杂度则是 O(n)。


编程

Post navigation

NEXT
我的 2018
PREVIOUS
写优雅的代码:异常处理

发表回复 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注

最近文章

  • 姥姥
  • 设计一个可扩展的用户模型
  • 使用 Apple 的 Keychain 保存 SSH 的 passphase
  • 解决 ABA 问题
  • 关于 macOS 上面部分 emoji 无法显示的问题
  • 这些年我技术栈的变化
  • 搬瓦工、狗云、hostodo、oracle对比测试
  • Google Drive 无法上传文件
  • 使用 socks5 代理 git ssh 协议
  • 到底要不要“润”
  • 可复用的代码
  • 关于疫情的一点点反思
  • 我的风控策略(投资篇)
  • 我的风控策略(生活篇)
  • Spring Boot是如何处理异常的
  • 编码与解码
  • 基于统计的图像目标检索
  • 有限状态机和状态模式
  • API安全设计
  • 用户密码的存储策略

近期评论

  • ǝɔɐǝԀʎzɐɹϽ发表在《可复用的代码》
  • Alex发表在《可复用的代码》
  • ǝɔɐǝԀʎzɐɹϽ发表在《到底要不要“润”》
  • ǝɔɐǝԀʎzɐɹϽ发表在《可复用的代码》
  • ǝɔɐǝԀʎzɐɹϽ发表在《我的风控策略(生活篇)》
  • ǝɔɐǝԀʎzɐɹϽ发表在《如何写出简洁优雅的代码》
  • 张志亮发表在《如何写出简洁优雅的代码》

分类

  • AI (2)
  • Java应用安全之道 (1)
    • 加密与解密 (1)
  • Odoo (2)
  • Python (1)
  • 图像处理 (1)
  • 年鉴 (1)
  • 数据库 (10)
  • 编程 (14)
    • Spring (1)
  • 读书笔记 (2)
  • 运维 (5)
  • 随笔 (10)

归档

  • 2023年1月 (2)
  • 2022年8月 (1)
  • 2022年7月 (4)
  • 2022年6月 (2)
  • 2022年5月 (2)
  • 2022年4月 (3)
  • 2021年10月 (1)
  • 2021年7月 (1)
  • 2021年5月 (1)
  • 2020年11月 (1)
  • 2020年7月 (1)
  • 2020年3月 (2)
  • 2020年2月 (1)
  • 2019年1月 (1)
  • 2018年12月 (2)
  • 2018年11月 (2)
  • 2017年4月 (1)
  • 2016年11月 (1)
  • 2016年9月 (1)
  • 2016年7月 (1)
  • 2016年5月 (3)
  • 2016年4月 (2)
  • 2016年3月 (1)
  • 2016年2月 (2)
  • 2015年12月 (1)
  • 2015年11月 (2)
  • 2015年8月 (1)
  • 2015年4月 (1)
  • 2015年3月 (1)

标签

Database devops Java MySQL PostgreSQL Python shell Spring SpringBoot Spring Security 安全 年鉴 总结 编程 随笔
© 2015-2023   Geektop.net All Rights Reserved.