在第一次接触Python的时候,可能写过类似for i in [2, 3, 5, 7, 11, 13]: print(i) 这样的语句。for in 语句理解起来很直观形象
但是,Python在处理for in 语句的时候具体发生了什么呢?什么样的对象可以被for in 来枚举呢?
接下来深入到Python的容器类型实现底层中,了解一种叫做迭代器和生成器的东西
一、容器、可迭代对象和迭代器
容器这个概念非常好理解,在Python中一切皆对象,对象的抽象就是类,而对象的集合就是容器
列表(list: [0, 1, 2]),元组(tuple: (0, 1, 2)),字典(dict: {0:0, 1:1, 2:2}),集合(set: set([0, 1, 2]))都是容器 对于容器,可以直观地想象成多个元素在一起的单元,而不同容器的区别在于内部数据结构的实现方法。然后,可以针对不同场景选择不同时间和空间复杂度的容器
所有的容器都是可迭代的(iterable) 这里的迭代和枚举不完全一样,迭代可以想象成是去买苹果,卖家并不告诉你他有多少库存。这样,每次都需要告诉卖家你要一个苹果,然后卖家采取行为: 要么给你拿一个苹果,要么告诉你苹果已经卖完了。而你并不需要知道卖家在仓库是怎么摆放苹果的
严谨地说,迭代器(iterator)提供了一个next 的方法 调用这个方法后,要么得到这个容器的下一个对象,要么得到一个StopIteration 的错误(苹果卖完了)。不需要像列表一样指定元素的索引,因为字典和集合这样的容器并没有索引一说 比如,字典采用哈希表实现,那么只需要知道next 函数可以不重复不遗漏地一个一个拿到所有元素即可
而可迭代对象,通过iter() 函数返回一个迭代器,再通过next() 函数就可以实现遍历 for in 语句将这个过程隐式化,所以只需要知道它大概做了什么就行了
看下面这段代码,主要展示怎么判断一个对象是否可迭代。当然,这还有另一种做法是isinstance(obj, Iterable)
def is_iterable(param):
try:
iter(param)
return True
except TypeError:
return False
params = [
1234,
'1234',
[1, 2, 3, 4],
set([1, 2, 3, 4]),
{1:1, 2:2, 3:3, 4:4},
(1, 2, 3, 4)
]
for param in params:
print('{} is iterable? {}'.format(param, is_iterable(param)))
1234 is iterable? False
1234 is iterable? True
[1, 2, 3, 4] is iterable? True
{1, 2, 3, 4} is iterable? True
{1: 1, 2: 2, 3: 3, 4: 4} is iterable? True
(1, 2, 3, 4) is iterable? True
通过这段代码可以知道,给出的类型中除了数字1234之外,其它的数据类型都是可迭代的
二、生成器是什么
很多人对生成器这个概念会比较陌生,因为生成器在很多常用语言中并没有相对应的模型,只需要记着一点:生成器是懒人版本的迭代器
在迭代器中,如果想要枚举它的元素,这些元素需要事先生成。这里,先看下面这个简单的样例:
import os
import psutil
def show_memory_info(hint):
pid = os.getpid()
p = psutil.Process(pid)
info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print('{} memory used: {} MB'.format(hint, memory))
def test_iterator():
show_memory_info('initing iterator')
list_1 = [i for i in range(100000000)]
show_memory_info('after iterator initiated')
print(sum(list_1))
show_memory_info('after sum called')
def test_generator():
show_memory_info('initing generator')
list_2 = (i for i in range(100000000))
show_memory_info('after generator initiated')
print(sum(list_2))
show_memory_info('after sum called')
%time test_iterator()
%time test_generator()
initing iterator memory used: 48.9765625 MB
after iterator initiated memory used: 3920.30078125 MB
4999999950000000
after sum called memory used: 3920.3046875 MB
Wall time: 17 s
initing generator memory used: 50.359375 MB
after generator initiated memory used: 50.359375 MB
4999999950000000
after sum called memory used: 50.109375 MB
Wall time: 12.5 s
声明一个迭代器很简单,[i for i in range(100000000)] 可以生成一个包含一亿元素的列表。每个元素在生成后都会保存到内存中,通过代码可以看到它们占用巨量的内存,内存不够的话就会出现OOM错误
不过,并不需要在内存中同时保存这么多东西,比如对元素求和只需要知道每个元素在相加的那一刻是多少就行了,用完就即可扔掉
于是,生成器的概念应运而生。在调用next() 函数的时候,才会生成下一个变量 生成器在Python的写法是用小括号括起来(i for i in range(100000000)) ,即初始化了一个生成器
这样一来,可以清晰地看到生成器并不会像迭代器一样占用大量内存,只有在被使用的时候才会调用。而且生成器在初始化的时候并不需要运行一次生成操作,相比于test_iterator() 、test_generator() 函数节省了一次生成一亿个元素的过程,因此耗时明显比迭代器短
到这里,可能说生成器不过如此嘛,不就是多占一些内存和计算资源嘛,多出点钱就是了呗。不过,先看一个自定义的生成器
三、生成器的新花样
数学中有一个恒等式(1 + 2 + 3 + ... + n)^2 = 1^3 + 2^3 + 3^3 + ... + n^3 ,接下来验证一下这个公式的正确性,看看实现的代码
def generator(k):
i = 1
while True:
yield i ** k
i += 1
gen_1 = generator(1)
gen_3 = generator(3)
print(gen_1)
print(gen_3)
def get_sum(n):
sum_1, sum_3 = 0, 0
for i in range(n):
next_1 = next(gen_1)
next_3 = next(gen_3)
print('next_1 = {}, next_3 = {}'.format(next_1, next_3))
sum_1 += next_1
sum_3 += next_3
print(sum_1 * sum_1, sum_3)
get_sum(8)
<generator object generator at 0x000001E70651C4F8>
<generator object generator at 0x000001E70651C390>
next_1 = 1, next_3 = 1
next_1 = 2, next_3 = 8
next_1 = 3, next_3 = 27
next_1 = 4, next_3 = 64
next_1 = 5, next_3 = 125
next_1 = 6, next_3 = 216
next_1 = 7, next_3 = 343
next_1 = 8, next_3 = 512
1296 1296
这段代码中,首先注意一下generator()这个函数,它返回了一个生成器
接下来的 yield 是魔术的关键,可以理解为函数运行到这一行的时候,程序会从这里暂停然后跳出,不过跳到哪里呢?答案是next() 函数。那么i ** k 是干什么的呢?它其实成了next() 函数的返回值
这样,每次next(gen) 函数被调用的时候,暂停的程序就又复活了,从 yield 这里向下继续执行,同时注意局部变量i并没有被清除掉,而是会继续累加。可以看到next_1从1变到8,next_3从1变到512
可以发现,这个生成器可以一直进行下去!没错,事实上迭代器是一个有限集合,生成器则可以成为一个无限集。只管调用next(),生成器根据运算会自动生成新的元素然后返回
再来看一个问题:给定一个list和一个指定数字,求这个数字在list中的位置
下面这段代码应该不陌生,也就是常规做法,枚举每个元素和它的index,判断后加入result,最后返回
def index_normal(L, target):
result = []
for i, num in enumerate(L):
if num == target:
result.append(i)
return result
print(index_normal([1, 6, 2, 4, 5, 2, 8, 6, 3, 2], 2))
[2, 5, 9]
那么使用迭代器可以怎么做呢?看下面的代码
def index_generator(L, target):
for i, num in enumerate(L):
if num == target:
yield i
print(list(index_generator([1, 6, 2, 4, 5, 2, 8, 6, 3, 2], 2)))
[2, 5, 9]
可以看到明显的区别,唯一需要强调的是index_generator 会返回一个Generator 对象,需要使用list 转换为列表后,才能用print 输出
|