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

Python 下避免 filter, map (reduce) 重复遍历

  •  
  •   mymusise ·
    mymusise · 2017-02-09 01:21:35 +08:00 · 5473 次点击
    这是一个创建于 2852 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Hi 第一次来写东西,大家多多支持 (入题) 最近某天上班路上在微薄看到一哥们写的《在 JavaScript 中实现 LINQ 》看到里面关于 C#的 Linq 在实现 filter 和 map 的时候说道(reduce 已经在 python3 从全局空间去掉了,所以标题里面我加了个括号),如果同时调用类似 filter 和 map 这样的操作去遍历 List 的时候,实际上只遍历了一遍,像下面这样:

    var array = new []{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    var sum = array.Where(n => n % 2 === 0)
               .Select(n => n + 3)
               .Aggregate((sum, n) => sum + n, 0);
    

    然后文章后面提到 JavaScript 中直接调用 filter 和 map 的时候,会重复遍历 Array ,比如像下面代码这样:

    let array = [1, 2, 3, 4]
    let sum = array.filter(n => n % 2 === 0)
                   .map(n => n + 3)
                   .reduce((sum, n) => sum + n, 0)
    

    这样的话会先把 arrayfilter 成[2,4],然后再 map 成[5, 7],然后再 reduce 成 12 ,所以这个过程 array 会被重复遍历。

    好了,下面说下 Python ,看完文章的时候然后我就好奇 Python 里面的 filter 和 map 是不是也是这样,会重复去遍历 List ,于是做了个实验: 像平时我们喜欢的函数式的写法:

    In [1]: numbers = [1,2,3,4,5,6]
    In [2]: list(map(lambda x: x + 1, filter(lambda x: x % 2 == 0, numbers)))
    Out[2]: [3, 5, 7]
    

    为了看清楚是不是重复遍历了 numbers 这个 List ,把 lambda 改写成个普通的 function 打印出来看看

    In [3]: def is_even(number):
       ...:     print('filter')
       ...:     return True if number % 2 == 0 else False
    
    In [4]: def inc(number):
       ...:     print('map')
       ...:     return number + 1
    
    In [5]: list(map(inc, filter(is_even, numbers)))
    filter
    filter
    filter
    filter
    filter
    filter
    map
    map
    map
    Out[6]: [3, 5, 7]
    

    上面可以看到, Python 这样直接调用 filter 和 map 也是会重复遍历 list 的。不过那哥们的文中提到后来能在 JavaScript 实现 Linq ,主要因为 ES6 支持 yield 和 Generator Function ,所以我想 Python 这两个都支持肯定也是可以实现类似 Linq 这样不重复遍历的 Magic 。

    然后,再试了下之前很喜欢的一个函数式库 pyfunctional。这是个很值来安利一波的一个库,用了这个库后,摆脱了原生那种很丑的写法

    # before
    list(map(inc, filter(is_even, numbers)))
    
    # afater
    seq(numbers)\
        .filter(is_even)\
        .map(inc)\
        .to_list()
    

    嗯,很 Js 的写法....

    好,回到正题,如果像上面这样调用 functional 时,发现整个过程只遍历的一次 List

    In [7]: from functional import seq
    In [8]: seq(numbers)\
       ...:     .filter(is_even)\
       ...:     .map(inc)\
       ...:     .to_list()
    filter
    filter
    map
    filter
    filter
    map
    filter
    filter
    map
    Out[8]: [3, 5, 7]
    

    果然是个好货,安利一波

    20 条回复    2017-02-10 06:47:11 +08:00
    skydiver
        1
    skydiver  
       2017-02-09 01:35:57 +08:00 via Android
    有什么区别吗…都是六次 filter 三次 map …只是顺序不一样
    czheo
        2
    czheo  
       2017-02-09 02:21:12 +08:00
    按照你这个说法,我是不是也可以安利一下我的
    https://github.com/czheo/syntax_sugar_python

    ryd994
        3
    ryd994  
       2017-02-09 05:56:49 +08:00   ❤️ 1
    不存在重复遍历, map 的结果是个新 list
    一定要说区别的话在于直接 map 有额外拷贝,是新 list ,内存占用大
    直接计算出最终结果的 list ,如果不需要全部结果的话,这样就浪费了

    用 itertools.map 就没这个问题
    python 里面 iterator 就是用 yield
    ryd994
        4
    ryd994  
       2017-02-09 06:00:00 +08:00
    顺带一提,如果是明确需要所有结果,而且不缺内存的话,一般写法(非 iterator )会快一点。上下文切换也是有成本的,哪有一个函数常驻指令缓存快。
    wjidea
        5
    wjidea  
       2017-02-09 06:00:31 +08:00
    @ryd994 itertools +1
    ryd994
        6
    ryd994  
       2017-02-09 06:03:17 +08:00
    再说明白点:
    numbers = [1,2,3,4,5,6]
    n1 = filter(lambda x: x % 2 == 0, numbers)
    n2 = list(map(lambda x: x + 1, n1))

    三次遍历分别在 numbers, n1, n2 上,不存在重复遍历一个 list 的问题
    kindjeff
        7
    kindjeff  
       2017-02-09 08:28:23 +08:00 via iPhone   ❤️ 1
    Python3 的 map 和 filter 返回的就是迭代器呀。如果你用 Python3 ,结果就是最后输出的那样。
    ChefIsAwesome
        8
    ChefIsAwesome  
       2017-02-09 08:45:24 +08:00 via Android
    这种优化就是把普通 list 变成 lazy 的 list ,然后内部保存了一个 command list 。每次往那个 chain 后头加个 filter , map 之类的方法的时候,往内部的 command list 里加东西。最后对这个 lazy list 取值的时候再去对 list 里的每个 item 执行那个 command list 。本质是个 monad ( linq 就是 monad )。
    从遍历的角度看,虽然 list 只遍历一次。但是那个 command list 每次都要遍历。速度未必比每次遍历都快。
    ik
        9
    ik  
       2017-02-09 08:49:29 +08:00 via iPhone
    翻到最后居然没有二维码,害的再翻回去看一遍😅
    quxw
        10
    quxw  
       2017-02-09 09:08:06 +08:00
    silymore
        11
    silymore  
       2017-02-09 12:03:14 +08:00 via Android
    @ik 我也是进来看二维码的,失策了
    mymusise
        12
    mymusise  
    OP
       2017-02-09 13:03:49 +08:00
    @skydiver 嗯,打印出来的次数是一样,但还是有点不一样。按照之前的理解,如果直接去 filter/map 的话,从输出结果看是先扫了一遍 list , filter 出新的 list ,然后再拿得到新 list 去 map ,不过楼下有哥们说 python3 返回的就是迭代器,试了下好像就没有这个问题了
    mymusise
        13
    mymusise  
    OP
       2017-02-09 13:06:03 +08:00
    @czheo 好东西,学习了,不过刚试了下有个 bug ,提了个 request 。
    miao1007
        14
    miao1007  
       2017-02-09 13:09:33 +08:00 via Android
    这个不就是惰性求值吗,类似 Guava
    mymusise
        15
    mymusise  
    OP
       2017-02-09 13:11:28 +08:00
    @ryd994 嗯,说的对,对比了下 pyfunctional 和直接 filter/map 和非 iterator 写法,耗时的确是 pyfunctional>自带的 filter > 非 iterator 。 @kindjeff 换成 Python3 的确没有这个问题了。
    WangYanjie
        16
    WangYanjie  
       2017-02-09 13:14:15 +08:00
    按我的理解, map, filter, reduce 都是不太推荐的,更好的做法应该是 list comprehensions,
    ```
    [x for x in range(1, 8) if x % 2 != 0]
    ```
    mymusise
        17
    mymusise  
    OP
       2017-02-09 13:17:18 +08:00
    @ChefIsAwesome 恩恩,看了下它的源码的确是维护着 lineage
    mymusise
        18
    mymusise  
    OP
       2017-02-09 13:18:33 +08:00
    @ik @silymore 啊哈,没懂什么意思,暗号么?
    czheo
        19
    czheo  
       2017-02-09 18:17:27 +08:00
    @mymusise 等你发 PR 呢,没收到啊
    ik
        20
    ik  
       2017-02-10 06:47:11 +08:00 via iPhone
    @mymusise 不不不,没有二维码就好,哈哈
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2600 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 21ms · UTC 03:46 · PVG 11:46 · LAX 19:46 · JFK 22:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.