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
lzjun
V2EX  ›  Python

1000000000000000 in range(1000000000000001) 的执行速度为什么这么快

  •  3
     
  •   lzjun ·
    lzjun567 · 2017-01-13 23:35:47 +08:00 · 2562 次点击
    这是一个创建于 2857 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在 Python 中,表达式 1000000000000000 in range(1000000000000001) 的执行速度能有多快?

    判断一个元素 x 是否存在于集合 y 中最简单粗暴地方法就是迭代,每次取出一个值与之比较,如果集合中存在一个值 z 等于 x 就返回 true ,它的时间复杂度是 O(n),使用哈希算法的理论时间复杂度是 O(1),二分查找的时间复杂度是 O(log n),那么 Python 究竟会采用的哪种算法来实现呢?

    先来做个实验:

    #python2
    
    timeit.timeit('1000000000 in range(0,1000000000,10)', number=1)
    5.50357640805305
    
    timeit.timeit('1000000000 in xrange(0,1000000000,10)', number=1)
    2.3025200839183526
    
    # python3
    
    import timeit
    timeit.timeit('1000000000 in range(0,1000000000,10)', number=1)
    4.490355838248402e-06
    

    我们都知道 python2 中的 range 函数返回的是一个列表对象,一次性把所有的元素加载到内存,所以执行第一个表达式的时候,系统会突然感觉非常卡顿,它需要的时间是 5 秒多。

    xrange 和 python3 中的 range 函数类似,都是返回一个迭代器对象,但是它俩的执行结果相差悬殊,让人大跌眼镜。第三个表达式所花的时间接近 0 秒,为何 python2 的 xrange 与 python3 中 range 函数区别这么大?为了弄明白其中的玄机,我们要理解 in 操作是如何执行的。根据 Python 文档 in 的规则:

    如果该类实现了__contains__()方法,那么只要 y.contains(x) 返回 true 那么 x in y 也返回 true ,反之亦然。 没有实现__contains__()方法,但实现了__iter__()方法,那么在迭代过程中如果有某个值 z==x ,就返回 true ,否则就是 false 。 如果以上两个方法都没有实现,就看__getitem__()方法, 如果存在一个索引 i 使得 x==y[i] ,就返回 true ,否则返回 false 。 明白了 in 的规则之后,我们先看看 xrange 提供了哪些方法:

    dir(xrange)
    
    ['__class__','__getitem__', '__hash__', '__init__', 
    '__iter__', '__len__', '__new__', ...]
    

    是的, xrange 函数只实现了 getitem 和 __iter__,判断 x 是 是否在 y 中需要逐个值迭代进行比较,也就是说 xrange 的时间复杂度是 O(n)。

    再来看看 python3 的 range 有哪些方法:

     dir(range)
    ['__class__', '__contains__', '__getitem__', '__iter__',  
    'count', 'index', 'start', 'step', 'stop', ...]
    

    range 提供的属性比 xrange 要多很多,不仅实现了 getitemiter ,还实现了 contains ,所以它会优先调用__contains__方法,此外,它还提供了三个属性 start 、 stop 、 step 。那么究竟为什么它的执行速度会如此之快呢?来看看 contains 方法是如何实现的吧。

    在 Python3 中,__contains__ 并不是逐个值迭代对比,而是采用这样一种逻辑:

    • 首先检查 x 是否 在 start 和 stop 范围之间: start <= x < stop
    • 如果在这个区间范围,那么再根据 step 计算 x 是否刚好落在 xrange 区间中的某个值上,这里用取模的方式来判断:(x - start) % step == 0

    此刻真相大白, xrange 的时间复杂度是 O(1),也就是说不管 xrange(start, stop, step) 中的 stop 值多大,时间复杂度都是一个常量。所以 python3 中的 range 方法不仅可以节省内存,而且执行效率更高,所以不要再纠结学 Python2 还是 Python3 了。

    也可以把它当作一到面试题来问: Python2 中的 xrange 与 python3 中的 range 有什么区别?它不仅可以考察候选者对 Python3 的熟悉程度,而且可以看出候选者对一个知识点的理解深度。

    公众号『一个程序员的微站』分享 Python 干货和有温度的内容

    iamge

    13 条回复    2017-01-17 05:14:57 +08:00
    luxinxin
        1
    luxinxin  
       2017-01-14 00:33:15 +08:00 via Android
    探讨很有意思,但“ python3 中的 range 方法不仅可以节省内存,而且执行效率更高”这个结论似乎不是很直接啊,只有在 in 这个例子里有用吧?
    Yinz
        2
    Yinz  
       2017-01-14 00:41:51 +08:00
    一下子好像想不出判断一个常数是否在一个 range 里的用处啊。。。不知哪位能赐教一下?
    skywatcher
        3
    skywatcher  
       2017-01-14 00:46:48 +08:00
    蛮有意思的
    latyas
        4
    latyas  
       2017-01-14 01:22:06 +08:00
    http://gist.github.com/ly0/f7c4a8a1e40555ac7684e5b68b8cc59d

    路过,附上 Python3.6 里 range 的 contains 方法的实现片段, btw python2.7 里没有实现 contains
    ericls
        5
    ericls  
       2017-01-14 07:25:56 +08:00   ❤️ 1
    把这种问题当成面试题是有多疯。。。
    HGladIator
        6
    HGladIator  
       2017-01-14 10:00:35 +08:00 via iPhone
    立马就关注了,喜欢这样深入的姿势
    lzjun
        7
    lzjun  
    OP
       2017-01-14 11:33:52 +08:00 via iPhone
    @luxinxin 节省内存是 range 返回的是一个迭代器的特性带来的优势
    lzjun
        8
    lzjun  
    OP
       2017-01-14 11:43:53 +08:00
    @latyas python2 中没有__contain__方法的这个问题其实很早就在 python 社区提出来了,不过最终他还是没有并入到 python2 中,而是直接集成到 python3 中去了

    http://bugs.python.org/issue1766304
    glogo
        9
    glogo  
       2017-01-14 14:08:59 +08:00
    编译成字节码看,然后对照 Python 源码去理解,是个比较好的办法吧?
    latyas
        10
    latyas  
       2017-01-15 04:04:13 +08:00
    @lzjun 没有办法,官方也不可能在一个即将要死的版本上添加新 feature ,无论从意义上还是从版本的兼容上。
    latyas
        11
    latyas  
       2017-01-15 04:07:59 +08:00
    @ericls 这种题当面试题的公司基本可以转身就走了,真想折磨人 python 能问的问题可多了(越甜的糖越有毒), cpython 的实现不好的地方也有太多,比如最近 3.6 的 dict 重新实现,如果这个 range 的问题能算面试题的话,是不是所有的 PEP 都可以随机抽出来做面试题呢?仅个人意见,不代表真实情况。
    lzjun
        12
    lzjun  
    OP
       2017-01-16 11:17:23 +08:00
    @latyas 纯粹作为开放式的话题吧,不能说这个答不出来就直接否定你,只是说答好了可以加分,答不好也没太大关系
    latyas
        13
    latyas  
       2017-01-17 05:14:57 +08:00
    @lzjun 这种有标准正确答案的问题不算是开放性的问题吧,对面试的效应姑且不谈,只是个人认为问这种问题面试官有 zb 的嫌疑,当然,这不是什么高端 b (为了避免误会,这么说没有刻意针对你和你的主题的意思啊。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2530 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 05:55 · PVG 13:55 · LAX 21:55 · JFK 00:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.