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

[mymusise]

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]

果然是个好货，安利一波

[skydiver]

有什么区别吗…都是六次 filter 三次 map …只是顺序不一样

[czheo]

按照你这个说法，我是不是也可以安利一下我的
https://github.com/czheo/syntax_sugar_python

[ryd994]

不存在重复遍历， map 的结果是个新 list
一定要说区别的话在于直接 map 有额外拷贝，是新 list ，内存占用大
直接计算出最终结果的 list ，如果不需要全部结果的话，这样就浪费了

用 itertools.map 就没这个问题
python 里面 iterator 就是用 yield

[ryd994]

顺带一提，如果是明确需要所有结果，而且不缺内存的话，一般写法（非 iterator ）会快一点。上下文切换也是有成本的，哪有一个函数常驻指令缓存快。

[wjidea]

@ryd994 itertools +1

[ryd994]

再说明白点：
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]

Python3 的 map 和 filter 返回的就是迭代器呀。如果你用 Python3 ，结果就是最后输出的那样。

[ChefIsAwesome]

这种优化就是把普通 list 变成 lazy 的 list ，然后内部保存了一个 command list 。每次往那个 chain 后头加个 filter ， map 之类的方法的时候，往内部的 command list 里加东西。最后对这个 lazy list 取值的时候再去对 list 里的每个 item 执行那个 command list 。本质是个 monad （ linq 就是 monad ）。
从遍历的角度看，虽然 list 只遍历一次。但是那个 command list 每次都要遍历。速度未必比每次遍历都快。

[ik]

翻到最后居然没有二维码，害的再翻回去看一遍😅

[quxw]

@kindjeff @ChefIsAwesome 说的对

[silymore]

@ik 我也是进来看二维码的，失策了

[mymusise]

@skydiver 嗯，打印出来的次数是一样，但还是有点不一样。按照之前的理解，如果直接去 filter/map 的话，从输出结果看是先扫了一遍 list ， filter 出新的 list ，然后再拿得到新 list 去 map ，不过楼下有哥们说 python3 返回的就是迭代器，试了下好像就没有这个问题了

[mymusise]

@czheo 好东西，学习了，不过刚试了下有个 bug ，提了个 request 。

[miao1007]

这个不就是惰性求值吗，类似 Guava

[mymusise]

@ryd994 嗯，说的对，对比了下 pyfunctional 和直接 filter/map 和非 iterator 写法，耗时的确是 pyfunctional>自带的 filter > 非 iterator 。 @kindjeff 换成 Python3 的确没有这个问题了。

[WangYanjie]

按我的理解， map, filter, reduce 都是不太推荐的，更好的做法应该是 list comprehensions,
```
[x for x in range(1, 8) if x % 2 != 0]
```

[mymusise]

@ChefIsAwesome 恩恩，看了下它的源码的确是维护着 lineage

[mymusise]

@ik @silymore 啊哈，没懂什么意思，暗号么？

[czheo]

@mymusise 等你发 PR 呢，没收到啊

[ik]

@mymusise 不不不，没有二维码就好，哈哈