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]
果然是个好货,安利一波
1
skydiver 2017-02-09 01:35:57 +08:00 via Android
有什么区别吗…都是六次 filter 三次 map …只是顺序不一样
|
2
czheo 2017-02-09 02:21:12 +08:00
|
3
ryd994 2017-02-09 05:56:49 +08:00 1
不存在重复遍历, map 的结果是个新 list
一定要说区别的话在于直接 map 有额外拷贝,是新 list ,内存占用大 直接计算出最终结果的 list ,如果不需要全部结果的话,这样就浪费了 用 itertools.map 就没这个问题 python 里面 iterator 就是用 yield |
4
ryd994 2017-02-09 06:00:00 +08:00
顺带一提,如果是明确需要所有结果,而且不缺内存的话,一般写法(非 iterator )会快一点。上下文切换也是有成本的,哪有一个函数常驻指令缓存快。
|
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 的问题 |
7
kindjeff 2017-02-09 08:28:23 +08:00 via iPhone 1
Python3 的 map 和 filter 返回的就是迭代器呀。如果你用 Python3 ,结果就是最后输出的那样。
|
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 每次都要遍历。速度未必比每次遍历都快。 |
9
ik 2017-02-09 08:49:29 +08:00 via iPhone
翻到最后居然没有二维码,害的再翻回去看一遍😅
|
10
quxw 2017-02-09 09:08:06 +08:00
@kindjeff @ChefIsAwesome 说的对
|
12
mymusise OP @skydiver 嗯,打印出来的次数是一样,但还是有点不一样。按照之前的理解,如果直接去 filter/map 的话,从输出结果看是先扫了一遍 list , filter 出新的 list ,然后再拿得到新 list 去 map ,不过楼下有哥们说 python3 返回的就是迭代器,试了下好像就没有这个问题了
|
14
miao1007 2017-02-09 13:09:33 +08:00 via Android
这个不就是惰性求值吗,类似 Guava
|
15
mymusise OP |
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] ``` |
17
mymusise OP @ChefIsAwesome 恩恩,看了下它的源码的确是维护着 lineage
|