V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
RicardoScofileld
V2EX  ›  Python

关于字典遍历的问题

  •  
  •   RicardoScofileld · 2018-05-07 10:06:12 +08:00 · 3258 次点击
    这是一个创建于 2152 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有一个疑惑,字典作为哈希表,从时间复杂度的角度上来说,获取要比遍历速度快的多,但是用 ipython 测试了一下,发现遍历要比获取快是什么原因啊

     def travel():
         for  key in mydict.keys():
            if 99999 == key:
                 return True
     def get():
          if mydict.get(99999):
               return True
               
     %timeit travel
    83.2 ns ± 2.49 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
    
     %timeit get
    87 ns ± 0.485 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
    
    17 条回复    2018-05-10 17:26:02 +08:00
    chisoco
        1
    chisoco  
       2018-05-07 10:28:48 +08:00
    你 mydict 里面的数据是不是 1-99999 顺序存的?
    ipwx
        2
    ipwx  
       2018-05-07 10:35:39 +08:00
    。。。你字典多大?
    am241
        3
    am241  
       2018-05-07 11:20:25 +08:00 via Android
    99999 是不是在 keys 的前部?
    kevindu
        4
    kevindu  
       2018-05-07 13:46:16 +08:00
    可能迭代和查找的实现是一样的吧,都是 lookdict
    hmzt
        5
    hmzt  
       2018-05-07 14:10:24 +08:00
    不该把字典所有值查一遍看总时间么
    sampeng
        6
    sampeng  
       2018-05-07 16:39:40 +08:00
    推测字典就一个 99999.。。
    kevindu
        7
    kevindu  
       2018-05-07 16:57:07 +08:00   ❤️ 2
    %timeit travel()
    %timeit get()

    才是正确的打开方式。。。

    11.6 ms ± 48.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    188 ns ± 5.74 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
    RicardoScofileld
        8
    RicardoScofileld  
    OP
       2018-05-07 19:07:14 +08:00
    @chisoco 直接写了个字典推导式 {x:x for x in range(10000)}
    RicardoScofileld
        9
    RicardoScofileld  
    OP
       2018-05-07 19:08:15 +08:00
    @ipwx {0:0,.......,99999:99999}
    RicardoScofileld
        10
    RicardoScofileld  
    OP
       2018-05-07 19:08:52 +08:00
    @hmzt 已经遍历字典的 key 了呀
    RicardoScofileld
        11
    RicardoScofileld  
    OP
       2018-05-07 19:10:38 +08:00
    @am241 out 了一下 dict.keys(),列表是从 0 到 99999 的
    RicardoScofileld
        12
    RicardoScofileld  
    OP
       2018-05-07 19:13:37 +08:00
    @kevindu 多谢,我说嘛,这不合理啊
    aijam
        13
    aijam  
       2018-05-08 04:45:31 +08:00
    lz 想搞一个大新闻
    RicardoScofileld
        14
    RicardoScofileld  
    OP
       2018-05-08 09:37:28 +08:00
    @kevindu 对了,if ... in 本质也是遍历操作,时间复杂度也是 O(n),我把 travel 改拨了一下,if 9999 in a.keys(),测试了一下,差别还是很小
    yujieyu7
        15
    yujieyu7  
       2018-05-08 12:08:11 +08:00
    遍历要比获取快???手动黑人问号脸
    mayorbryant
        16
    mayorbryant  
       2018-05-09 10:40:10 +08:00
    @RicardoScofileld 字典可以直接判断,不需要 a.keys(), 如果 if 9999 in a.keys() 这是一个列表的 in 判断,应该是 if 9999 in a
    a132811
        17
    a132811  
       2018-05-10 17:26:02 +08:00
    7 楼正解
    @RicardoScofileld 问题的方向错啦
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5766 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 37ms · UTC 01:54 · PVG 09:54 · LAX 18:54 · JFK 21:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.