可迭代对象与生成器

可迭代对象和生成器是python的核心卖点之一,这一特性让它看起来像是函数式编程语言,也让他的性能和表现力上了一个层次,同时它让用户可以面向流编程.这个特性的来源应该是古老的Lisp,而受Python影响javascript也在ES6中新增了生成器相关的工具,总而言之这个语法点非常重要.

本节的先验知识有:

协议与接口与抽象基类

可迭代对象,迭代器的范畴

凡是满足Iterable协议的都是可迭代对象.因此所有的容器都是可迭代对象,可迭代对象不管容量的大小,只要每次for循环都可以取出对象即可,因此迭代是数据处理的基石.扫描内存中放不下的数据集时，我们要找到一种惰性获取数据项的方式，即按需一次获取一个数据项.这就是迭代器模式(Iterator pattern).而符合这一特征的数据类型就是Iterator迭代器.Iterator除了有__iter__外还要实现next方法.

生成器

生成器是python中最中要的数据模型之一,由它衍生而来的协程可以看这篇文章了解.

生成器实现需要实现接口__iter__,__next__,send,throw这4个方法,但也有更加简单的方式实现就是使用生成器函数

生成器函数就是带有yield的函数,它停止需要抛出StopIteration异常

最简单的可迭代对象--生成器表达式

列表解析通过一定的操作可以产生一个列表,而如果去掉[],那就是惰性的生成器表达式了

何时使用生成器表达式

根据我的经验,选择使用哪种句法很容易判断--如果生成器表达式要分成多行写,我倾向于定义生成器函数以便提高可读性.此外生成器函数有名称,因此可以重用.

a = (i for i in range(10))

type(a)

generator

for i in a:
    print(i)

iter函数用于创建迭代器

iter函数可以将一个可迭代对象转换为一个迭代器

a = iter([i for i in range(10)])

序列可以迭代的原因在于解释器需要迭代对象时,会自动调用iter.

内置的iter 函数有以下作用:

检查对象是否实现了__iter__ 方法,如果实现了就调用它,获取一个迭代器.
如果没有实现__iter__ 方法,但是实现了__getitem__ 方法,Python会创建一个迭代器,尝试按顺序(从索引0开始)获取元素.
如果尝试失败,Python 抛出TypeError异常,通常会提示'xxx object is not iterable'

当iter有第二个参数的时候,iter的作用是使用常规的函数或任何可调用的对象创建迭代器.这样使用时，

第一个参数必须是可调用的对象,用于不断调用(没有参数),产出各个值
第二个值是哨符,这是个标记值,当可调用的对象返回这个值时,触发迭代器抛出StopIteration异常,而不产出哨符.

from random import randint

b = iter(lambda : randint(1,10),5)

for i in b:
    print(i)

可迭代对象的操作

拆包操作

python3支持可迭代对象的拆包操作,并且可以结合通配符达到一些很酷的效果

_,x,*last=range(10)

last

[2, 3, 4, 5, 6, 7, 8, 9]

排序操作

内置函数sorted(iterable,key,reverse=False,)会新建一个列表作为返回值.这个方法可以接受任何形式的可迭代对象作为参数,而不管sorted接受的是怎样的参数,它最后都会返回一个列表.

其中参数reverse如果被设定为True,被排序的序列里的元素会以降序输出(也就是说把最大值当作最小值来排序).

参数key则为一个只有一个参数的函数,这个函数会被用在序列里的每一个元素上,所产生的结果将是排序算法依赖的对比关键字.比如说,在对一些字符串排序时,可以用key=str.lower来实现忽略大小写的排序,或者是用key=len进行基于字符串长度的排序.这个参数的默认值是恒等函数identity function,也就是默认用元素自己的值来排序

sorted([11,3,4,2,5])

[2, 3, 4, 5, 11]

堆排序

python的标准库heapq提供了将列表转换为堆的算法支持

堆是二叉树,每个父节点具有小于或等于其任何子节点的值.该实现使用数组,对于所有k,从零开始计数元素,

heap [k] <= heap [2 * k 1]和heap [k] <= heap [2 * k 2]为了比较,不存在的元素被认为是无限的.堆的有趣属性是它的最小元素总是根heap[0]. 方法有:

heapq.heappush(heap, item)

向堆中插入元素
heapq.heappop(heap)

从堆中取出最小元素
heapq.heappushpop(heap, item)

插入元素在取出最小元素
heapq.heapify(x)

将一个列表注册为堆
heapq.heapreplace(heap, item)

移除堆中的某个元素
heapq.merge(*iterables, key=None, reverse=False)

将多个排序输入合并到单个排序的输出(例如，从多个日志文件中合并时间戳条目).返回排序值的迭代器
heapq.nlargest(n, iterable, key=None)

取可迭代对象中最大的n个元素
heapq.nsmallest(n, iterable, key=None)

取可迭代对象中最大的n个元素

import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

heapsort([11,3,4,2,5])

[2, 3, 4, 5, 11]

c = [11,3,4,2,5]

heapq.heapify(c)

[2, 3, 4, 11, 5]

[heapq.heappop(c) for i in range(len(c))]

[2, 3, 4, 5, 11]

排序性能测试

from random import randint,random

a = [randint(1,100) for i in range(50)]

aa = [randint(1,10000) for i in range(5000)]

aaa = [randint(1,1000000) for i in range(5000000)]

b = [random() for i in range(50)]

bb = [random() for i in range(5000)]

bbb = [random() for i in range(5000000)]

%timeit heapsort(a)

15.9 µs ± 229 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit sorted(a)

2.92 µs ± 79.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit heapsort(aa)

2.11 ms ± 19.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit sorted(aa)

877 µs ± 11.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit heapsort(aaa)

13.2 s ± 72 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit sorted(aaa)

3.95 s ± 14.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit heapsort(b)

15.1 µs ± 65.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit sorted(b)

2.78 µs ± 45.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit heapsort(bb)

2.25 ms ± 52.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit sorted(bb)

905 µs ± 4.76 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit heapsort(bbb)

9.84 s ± 524 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit sorted(bbb)

3.38 s ± 61.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

可以看出,堆排序效率并不如自带的排序算法效率高,那么堆有什么作用呢?简单来说就是插入和查找方便,堆会在每次都将数据存入与自己大小匹配的

用bisect来管理已排序的序列

bisect模块的主要作用是管理有序序列.

bisect模块包含两个主要函数bisect 和insort,两个函数都利用二分查找算法来在有序序列中查找或插入元素.

bisect(a, x[, lo[, hi]])

bisect的作用是查找x元素在a序列中的位置.它的表现可以从两个方面来调教:
- 首先可以用它的两个可选参数——lo和hi——来缩小搜寻的范围,lo的默认值是0,hi的默认值是序列的长度,即len()作用于该序列的返回值
- bisect函数其实是bisect_right函数的别名，后者还有个姊妹函数叫bisect_left.的区别在于,bisect_left返回的插入位置是原序列中跟被插入元素相等的元素的位置,也就是新元素会被放置于它相等的元素的前面,而bisect_right返回的则是跟它相等的元素之后的位置.这个细微的差别可能对于整数序列来讲没什么用,但是对于那些值相等但是形式不同的数据类型来讲结果就不一样了.
insort(a, x[, lo[, hi]])

排序很耗时,因此在得到一个有序序列之后,我们最好能够保持它的有序.bisect.insort就是为了这个而存在的.insort(seq, item) 把变量item 插入到序列seq中,并能保持seq的升序顺序.

例子:用bisect来搜索

bisect(haystack, needle)|bisect_left(haystack, needle) 在haystack(干草垛)里搜索needle(针)的位置,该位置满足的条件是:把needle 插入这个位置之后,haystack 还能保持升序.也就是在说这个函数返回的位置前面的值,都小于或等于needle的值.其中haystack必须是一个有序的序列.

你可以先用bisect(haystack, needle) 查找位置index,再用haystack.insert(index,needle)来插入新值.但你也可用insort来一步到位,并且后者的速度更快一些.

import bisect
import sys
HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]
ROW_FMT = '{0:2d} @ {1:2d} {2}{0:<2d}'

def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        position = bisect_fn(HAYSTACK, needle)
        offset = position * ' |'
        print(ROW_FMT.format(needle, position, offset))

bisect_fn = bisect.bisect
print('DEMO:', bisect_fn.__name__)
print('haystack ->', ' '.join('%2d' % n for n in HAYSTACK))
demo(bisect_fn)

DEMO: bisect
haystack ->  1  4  5  6  8 12 15 20 21 23 23 26 29 30
31 @ 14  | | | | | | | | | | | | | |31
30 @ 14  | | | | | | | | | | | | | |30
29 @ 13  | | | | | | | | | | | | |29
23 @ 11  | | | | | | | | | | |23
22 @  9  | | | | | | | | |22
10 @  5  | | | | |10
 8 @  5  | | | | |8 
 5 @  3  | | |5 
 2 @  1  |2 
 1 @  1  |1 
 0 @  0 0

bisect_fn = bisect.bisect_left
print('DEMO:', bisect_fn.__name__)
print('haystack ->', ' '.join('%2d' % n for n in HAYSTACK))
demo(bisect_fn)

DEMO: bisect_left
haystack ->  1  4  5  6  8 12 15 20 21 23 23 26 29 30
31 @ 14  | | | | | | | | | | | | | |31
30 @ 13  | | | | | | | | | | | | |30
29 @ 12  | | | | | | | | | | | |29
23 @  9  | | | | | | | | |23
22 @  9  | | | | | | | | |22
10 @  5  | | | | |10
 8 @  4  | | | |8 
 5 @  2  | |5 
 2 @  1  |2 
 1 @  0 1 
 0 @  0 0

例:用bisect.insort插入新元素

import bisect
import random
SIZE=7
random.seed(1729)
my_list = []
for i in range(SIZE):
    new_item = random.randrange(SIZE*2)
    bisect.insort(my_list, new_item)
    print('%2d ->' % new_item, my_list)

10 -> [10]
 0 -> [0, 10]
 6 -> [0, 6, 10]
 8 -> [0, 6, 8, 10]
 7 -> [0, 6, 7, 8, 10]
 2 -> [0, 2, 6, 7, 8, 10]
10 -> [0, 2, 6, 7, 8, 10, 10]

内置的可迭代对象

可迭代对象作为python最中要的特性之一,已经被很多语言借鉴吸收,比如javascript在ES6标准中实现了生成器.

python3有大量的内置可迭代对象

`range(start,end,step)`

生成整数等差数列对象

[i for i in range(1,10,3)]

[1, 4, 7]

更多的可迭代对象可以则包括在标准库itertools中

`itertools.count(start,step)`

生成无穷等差数列

from itertools import count

gen = count(1,0.5)

for i in range(5):
    print(next(gen))

1
1.5
2.0
2.5
3.0

`itertools.cycle(it)`

从it 中产出各个元素,存储各个元素的副本,然后按顺序重复不断地产出各个元素

from itertools import cycle

gen = cycle([1,2,3])

for i in range(5):
    print(next(gen))

`itertools.repeat(item, [times])`

重复不断地产出指定的元素，除非提供times，指定次数

from itertools import repeat

gen = repeat(1)

for i in range(5):
    print(next(gen))

`itertools.permutations(it,out_len=None)`

把out_len 个it 产出的元素排列在一起,然后产出这些排列;out_len 的默认值等于len(list(it))

from itertools import permutations

gen = permutations([1,2,3],2)

for i in gen:
    print(i)

(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

`itertools.combinations(it,out_len)`

把it 产出的out_len 个元素组合在一起,然后产出

from itertools import combinations

gen = combinations([1,2,3],2)

for i in gen:
    print(i)

(1, 2)
(1, 3)
(2, 3)

`itertools.combinations_with_replacement(it, out_len)`

把it产出的out_len个元素组合在一起,然后产出,包含相同元素的组合

from itertools import combinations_with_replacement

gen = combinations_with_replacement([1,2,3],2)

for i in gen:
    print(i)

(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 3)
(3, 3)

内置的的迭代器函数

迭代器函数是用来处理迭代器的函数,主要功能包括

过滤迭代器--用于从迭代器中剔除部分元素
映射迭代器--用于对迭代器中的元素做同样的处理
合并迭代器--用于合并多个可迭代对象从而生成一个新迭代器对象
重排迭代器--用于重新排列元素

过滤迭代器

filter(predicate, it)

把it 中的各个元素传给predicate,如果predicate(item)返回真值,那么产出对应的元素;如果predicate 是None,那么只产出真值元素
itertools.compress(it, selector_it)

并行处理两个可迭代的对象;如果selector_it中的元素是真值,产出it中对应的元素
itertools.dropwhile(predicate, it)

处理it，跳过predicate 的计算结果为真值的元素,然后产出剩下的各个元素(不再进一步检查)
itertools.filterfalse(predicate, it)

与filter 函数的作用类似,不过predicate的逻辑是相反的--predicate 返回假值时产出对应的元素
itertools.islice(it, stop) 或islice(it,start, stop, step=1)

产出it的切片,作用类似于s[:stop] 或s[start:stop:step],不过it可以是任何可迭代的对象,而且这个函数实现的是惰性操作
itertools takewhile(predicate, it)

predicate 返回真值时产出对应的元素,然后立即停止,不再继续检查

映射迭代器

enumerate(iterable, start=0)

产出由两个元素组成的元组,结构是(index, item),其中index 从start 开始计数,item 则从iterable 中获取
map(func, it1, [it2, ..., itN])

把it中的各个元素传给func,产出结果;如果传入N 个可迭代的对象,那么func 必须能接受N 个参数,而且要并行处理各个可迭代的对象
itertools.accumulate(it, [func])

产出累积的总和;如果提供了func,那么把前两个元素传给它,然后把计算结果和下一个元素传给它,以此类推，最后产出结果
itertools.starmap(func, it)

把it中的各个元素传给func,产出结果;输入的可迭代对象应该产出可迭代的元素iit,然后以func(*iit) 这种形式调用func

合并迭代器

zip(it1, ..., itN)

并行从输入的各个可迭代对象中获取元素,产出由N个元素组成的元组,只要有一个可迭代的对象到头了,就默默地停止
itertools.chain(it1, ..., itN)

先产出it1中的所有元素,然后产出it2中的所有元素,以此类推,无缝连接在一起
itertools.chain.from_iterable(it)

产出it 生成的各个可迭代对象中的元素,一个接一个,无缝连接在一起;it 应该产出可迭代的元素,例如可迭代的对象列表
itertools.product(it1, ...,itN, repeat=1)

计算笛卡儿积:从输入的各个可迭代对象中获取元素,合并成由N个元素组成的元组,与嵌套的for循环效果一样;repeat指明重复处理多少次输入的可迭代对象
itertools zip_longest(it1, ...,itN, fillvalue=None)

并行从输入的各个可迭代对象中获取元素,产出由N个元素组成的元组,等到最长的可迭代对象到头后才停止,空缺的值使用fillvalue填充

重排迭代器

itertools.groupby(it,key=None)

产出由两个元素组成的元素,形式为(key, group),其中key是分组标准,group 是生成器,用于产出分组里的元素
itertools.tee(it, n=2)

产出一个由n个生成器组成的元组,每个生成器用于单独产出输入的可迭代对象中的元素

可迭代的归约函数

所谓归约函数指接受一个可迭代的对象,然后返回单个结果的函数.python内置了许多这种函数

all(it)

it 中的所有元素都为真值时返回True,否则返回False;all([]) 返回True
sum(it, start=0)

it 中所有元素的总和,如果提供可选的start,会把它加上(计算浮点数的加法时,可以使用math.fsum函数提高精度)
any(it)

只要it中有元素为真值就返回True,否则返回False;any([]) 返回False
max(it, [key=,][default=])

返回it中值最大的元素;key 是排序函数,与sorted函数中的一样;如果可迭代的对象为空,返回default
min(it, [key=,][default=])

返回it中值最小的元素;key 是排序函数,与sorted 函数中的一样;如果可迭代的对象为空,返回default
functools reduce(func, it,[initial])

把前两个元素传给func,然后把计算结果和第三个元素传给func,以此类推,返回最后的结果;如果提供了initial,把它当作第一个元素传入

`*`第三方可迭代对象对应工具

python的可迭代对象很多时候还是无法满足我们的需求,比如序列按长度拆分,比如构造窗口等等,我们可以使用more-itertools这个库来实现这些更高级的需求.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

可迭代对象与生成器.md

可迭代对象与生成器.md

可迭代对象与生成器

可迭代对象,迭代器的范畴

生成器

最简单的可迭代对象--生成器表达式

何时使用生成器表达式

iter函数用于创建迭代器

可迭代对象的操作

拆包操作

排序操作

堆排序

排序性能测试

用bisect来管理已排序的序列

例子:用bisect来搜索

例:用bisect.insort插入新元素

内置的可迭代对象

`range(start,end,step)`

`itertools.count(start,step)`

`itertools.cycle(it)`

`itertools.repeat(item, [times])`

`itertools.permutations(it,out_len=None)`

`itertools.combinations(it,out_len)`

`itertools.combinations_with_replacement(it, out_len)`

内置的的迭代器函数

过滤迭代器

映射迭代器

合并迭代器

重排迭代器

可迭代的归约函数

`*`第三方可迭代对象对应工具

Files

可迭代对象与生成器.md

Latest commit

History

可迭代对象与生成器.md

File metadata and controls

可迭代对象与生成器

可迭代对象,迭代器的范畴

生成器

最简单的可迭代对象--生成器表达式

何时使用生成器表达式

iter函数 用于创建迭代器

可迭代对象的操作

拆包操作

排序操作

堆排序

排序性能测试

用bisect来管理已排序的序列

例子:用bisect来搜索

例:用bisect.insort插入新元素

内置的可迭代对象

range(start,end,step)

itertools.count(start,step)

itertools.cycle(it)

itertools.repeat(item, [times])

itertools.permutations(it,out_len=None)

itertools.combinations(it,out_len)

itertools.combinations_with_replacement(it, out_len)

内置的的迭代器函数

过滤迭代器

映射迭代器

合并迭代器

重排迭代器

可迭代的归约函数

*第三方可迭代对象对应工具

iter函数用于创建迭代器

`range(start,end,step)`

`itertools.count(start,step)`

`itertools.cycle(it)`

`itertools.repeat(item, [times])`

`itertools.permutations(it,out_len=None)`

`itertools.combinations(it,out_len)`

`itertools.combinations_with_replacement(it, out_len)`

`*`第三方可迭代对象对应工具