作者：小小明

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/is-subsequence

要解决这个问题，常规算法是贪心算法。我们维护两个指针指向两个字符串的开头，然后对第二个字符串一路扫过去，如果某个字符和第一个指针指的一样，那么就把第一个指针前进一步。第一个指针移出第一个序列最后一个元素的时候，返回 True，否则返回 False。

不过，这个算法正常写的话，写下来怎么也得八行左右：

def is_subsequence(s: str, t: str) -> bool:
    n, m = len(s), len(t)
    i = j = 0
    while i < n and j < m:
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == n

print(is_subsequence("ace", "abcde"))
print(is_subsequence("aec", "abcde"))

但如果我们使用迭代器和生成器，代码量将大幅度减少：

def is_subsequence(s: str, t: str) -> bool:
    t = iter(t)
    return all(i in t for i in s)
 
print(is_subsequence("ace", "abcde"))
print(is_subsequence("aec", "abcde"))

而且运行结果正确与上面一样，都是：

True
False

但如果你对python的生成器运行机制不太了解，一定会看的一脸懵逼。

不过不用担心，我今天分享的主题便是python的迭代器和生成器剖析。

迭代器和可迭代对象

在 Python 中一切皆对象，对象的抽象就是类，而对象的集合就是容器。

列表（list: [0, 1, 2]），元组（tuple: (0, 1, 2)），字典（dict: {0:0, 1:1, 2:2}），集合（set: set([0, 1, 2])）都是容器。对于容器，可以认为是多个元素在一起的单元；而不同容器的区别，正是在于内部数据结构的实现方法。

所有的容器都是可迭代对象（iterable）：

from collections.abc import Iterable
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(f'{param}是否为可迭代对象? ', isinstance(param, Iterable))

运行结果：

1234是否为可迭代对象?  False
1234是否为可迭代对象?  True
[1, 2, 3, 4]是否为可迭代对象?  True
{1, 2, 3, 4}是否为可迭代对象?  True
{1: 1, 2: 2, 3: 3, 4: 4}是否为可迭代对象?  True
(1, 2, 3, 4)是否为可迭代对象?  True

可以看到所有的集合容器都是可迭代对象（iterable），字符串也是可迭代对象，唯有单个数字不是可迭代对象。

而可迭代对象，可以通过 iter() 函数返回一个迭代器，当然迭代器本身也属于可迭代对象：

from collections.abc import Iterable, Iterator
params = [
    '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:
    param = iter(param)
    print("----------")
    print(f'{param}是否为可迭代对象? ', isinstance(param, Iterable))
    print(f'{param}是否为迭代器对象? ', isinstance(param, Iterator))

运行结果：

----------
<str_iterator object at 0x0000000005B3FD30>是否为可迭代对象?  True
<str_iterator object at 0x0000000005B3FD30>是否为迭代器对象?  True
----------
<list_iterator object at 0x0000000004C786D8>是否为可迭代对象?  True
<list_iterator object at 0x0000000004C786D8>是否为迭代器对象?  True
----------
<set_iterator object at 0x0000000005B5E048>是否为可迭代对象?  True
<set_iterator object at 0x0000000005B5E048>是否为迭代器对象?  True
----------
<dict_keyiterator object at 0x0000000005B37228>是否为可迭代对象?  True
<dict_keyiterator object at 0x0000000005B37228>是否为迭代器对象?  True
----------
<tuple_iterator object at 0x0000000004C786D8>是否为可迭代对象?  True
<tuple_iterator object at 0x0000000004C786D8>是否为迭代器对象?  True

这意味着迭代器本身也可以获取它自己的迭代器，例如：

for i in iter(l):
    print(i, end=",")
print()
for i in iter(iter(l)):
    print(i, end=",")

运行结果：

1,2,3,4,
1,2,3,4,

迭代器（iterator）提供了一个 __next__的方法。调用这个方法后，你要么得到这个容器的下一个对象，要么得到一个 StopIteration 的错误：

l = [1, 2, 3, 4]
l = iter(l)
while True:
    print(l.__next__())

结果：

1
2
3
4
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-16-e106f3a7bd73> in <module>()
      2 l = iter(l)
      3 while True:
----> 4     print(l.__next__())

StopIteration: 

当然上面的l.__next__()应该改写成next(l)，next()方法的本质就是调用目标对象的__next__()方法。

实际上for循环：

l = [1, 2, 3, 4]
for i in l:
    print(i)

的本质等价于：

l = [1, 2, 3, 4]
l_iter = iter(l)
while True:
    try:
        i = next(l_iter)
    except StopIteration:
        break
    print(i)

for in 语句将这个过程隐式化了。

列表生成式与列表生成器

列表生成式即List Comprehensions，是Python内置的非常简单却强大的可以用来创建list的生成式。

print([x * x for x in range(1, 11)])
print([x * x for x in range(1, 11) if x % 2 == 0])

#还可以使用两层循环，可以生成全排列：
print([m + n for m in 'ABC' for n in 'XYZ'])
print([str(x)+str(y) for x in range(1,6) for y in range(11,16)])

#for循环其实可以同时使用两个甚至多个变量，比如dict的items()可以同时迭代key和value：
d = {'x': 'A', 'y': 'B', 'z': 'C' }
print([k + '=' + v for k, v in d.items()])

结果：

[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
[4, 16, 36, 64, 100]
['AX', 'AY', 'AZ', 'BX', 'BY', 'BZ', 'CX', 'CY', 'CZ']
['111', '112', '113', '114', '115', '211', '212', '213', '214', '215', '311', '312', '313', '314', '315', '411', '412', '413', '414', '415', '511', '512', '513', '514', '515']
['x=A', 'y=B', 'z=C']

通过列表生成式，我们可以直接创建一个列表。但是，受到内存限制，列表容量肯定是有限的。而且，创建一个包含100万个元素的列表，不仅占用很大的存储空间，如果我们仅仅需要访问前面几个元素，那后面绝大多数元素占用的空间都白白浪费了。

所以，如果列表元素可以按照某种算法推算出来，那我们是否可以在循环的过程中不断推算出后续的元素呢？这样就不必创建完整的list，从而节省大量的空间。在Python中，这种一边循环一边计算的机制，称为生成器：generator。

只要把一个列表生成式的[]改成()，就创建了一个generator：

g = (x * x for x in range(10))

generator保存的是算法，每次调用next(g)，就计算出g的下一个元素的值，直到计算到最后一个元素，没有更多的元素时，抛出StopIteration的错误。

用一个示例，感受一下生成器相对生成式的优势，首先创建一个查看当前内存情况的方法：

import os
import psutil

# 显示当前 python 程序占用的内存大小
def show_memory_info(hint):
    pid = os.getpid()
    p = psutil.Process(pid)

    info = p.memory_full_info()
    memory = info.uss / 1024. / 1024
    print(f'{hint}内存使用: {memory} MB')

测试一下列表生成式：

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')

%time test_iterator()

结果：

initing iterator内存使用: 48.69140625 MB
after iterator initiated内存使用: 3936.2890625 MB
4999999950000000
after sum called内存使用: 3936.29296875 MB
Wall time: 9.39 s

测试一下列表生成器：

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_generator()

结果：

initing generator内存使用: 48.8515625 MB
after generator initiated内存使用: 48.85546875 MB
4999999950000000
after sum called内存使用: 49.11328125 MB
Wall time: 7.95 s

声明一个迭代器很简单，[i for i in range(100000000)]就可以生成一个包含一亿元素的列表。每个元素在生成后都会保存到内存中，你通过上面的代码可以看到，它们占用了巨量的内存，内存不够的话就会出现 OOM 错误。

不过，我们并不需要在内存中同时保存这么多东西，比如对元素求和，我们只需要知道每个元素在相加的那一刻是多少就行了，用完就可以扔掉了。

函数生成器(generator)

如果推算的算法比较复杂，用类似列表生成式的for循环无法实现的时候，还可以用函数来实现。

比如，著名的斐波拉契数列（Fibonacci），除第一个和第二个数外，任意一个数都可由前两个数相加得到：

1, 1, 2, 3, 5, 8, 13, 21, 34, …

斐波拉契数列用列表生成式写不出来，但是用函数把它打印出来却很容易：

def fib(max):
    n, a, b = 0, 0, 1
    while n < max:
        print(b)
        a, b = b, a + b
        n = n + 1

fib(6)

打印结果：

1
1
2
3
5
8

上面的函数和生成器(generator)仅一步之遥，只要把print(b)改为yield b，fib函数就会变成生成器(generator)：

def fib(max):
    n, a, b = 0, 0, 1
    while n < max:
        yield b
        a, b = b, a + b
        n = n + 1

这就是除了列表生成器以外定义generator的另一种方法。

如果一个函数定义中包含yield关键字，那么这个函数就不再是一个普通函数，而是一个generator：

fib(6)

结果：

<generator object fib at 0x0000000005F04A98>

在前面的列表生成器中我已经讲过，对于生成器可以使用for循环进行遍历：

for i in fib(6):
    print(i)

打印结果：

1
1
2
3
5
8

这里，最难理解的就是generator和函数的执行流程不一样。函数是顺序执行，遇到return语句或者最后一行函数语句就返回。而变成generator的函数，在每次调用next()的时候执行，遇到yield语句返回，再次执行时从上次返回的yield语句处继续执行。

举个简单的例子，定义一个generator，依次返回数字1，3，5：

def odd():
    print('step 1')
    yield 1
    print('step 2')
    yield(3)
    print('step 3')
    yield(5)

调用该generator时，首先要生成一个generator对象，然后用next()函数不断获得下一个返回值：

o = odd()
while True:
    print(next(o))

结果：

step 1
1
step 2
3
step 3
5
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-7-554c5fb505f8> in <module>()
      1 o = odd()
      2 while True:
----> 3     print(next(o))

StopIteration: 

可以看到，odd不是普通函数，而是generator，在执行过程中，遇到yield就中断，下次又继续执行。执行3次yield后，已经没有yield可以执行了，所以，第4次调用next()就抛出StopIteration异常。

对于函数生成器(generator)来说，遇到return语句就是结束generator的指令（函数体最后一行语句其实隐式执行了return None），for循环随之结束。

迭代器和生成器的关系

其实生成器就是一种特殊的迭代器，而迭代器包括了生成器并不等价于生成器，它们都可以通过next()方法不断的获取下一个对象，都具备记忆已经读取的位置的特点。

例如：

l = [1, 2, 3, 4]
l_iter = iter(l)

完成可以理解为产生了一个列表生成器：

l = [1, 2, 3, 4]
l_iter = (i for i in l)

也可以理解成产生了一个函数生成器：

l = [1, 2, 3, 4]

def func_generator(l):
    for i in l:
        yield i

l_iter = func_generator(l)

利用生成器判断子序列详解

有了前面的基础知识，相信文章开头的代码还稍微有点眉目了。现在我们再回到文章开头的代码，详细分析一下：

def is_subsequence(s: str, t: str) -> bool:
    t = iter(t)
    return all(i in t for i in s)
 
print(is_subsequence("ace", "abcde"))
print(is_subsequence("aec", "abcde"))

首先t = iter(t)我们可以理解为产生了一个生成器：

t = (i for i in t)

而i in t基本上等价于：

while True:
    val = next(t)
    if val == i:
        yield True

测试一下：

t = "abcde"
t = (i for i in t)
print('a' in t)
print('c' in t)
print(next(t))

结果：

True
True
d

可以看到最后一行直接返回了匹配到c的下一个值’d’。

这样我们再测试：

t = "abcde"
t = (i for i in t)
print('a' in t)
print('c' in t)
print('b' in t)

结果：

True
True
False

于是就可以顺利的使用生成器计算子序列的每个元素是否满足条件：

t = iter("abcde")
[i in t for i in "aec"]

结果：

[True, True, False]

而all()函数即可判断是否全部都满足条件：

print(all([True, True, False]), all([True, True, True]))

结果：

False True

而上述代码all(i in t for i in s)没有申明all([i in t for i in s])列表生成式形式则代表是对一个列表生成器进行all运算。

总结

于是到此，我们就很优雅地解决了这道题。不过一定要注意，实际工作中尽量不要用这种技巧，因为你的领导和同事有可能并不知道生成器的用法，你即使写了详细的注释他们也难以理解，不如用常规方法解决比较好！经过今天的学习，希望你已经在生成器这个技术知识点上比其他人更加熟练了。

今天本文分享了容器、可迭代对象、迭代器和生成器四种不同的对象：

• 容器是可迭代对象，可迭代对象调用 iter() 函数可以得到一个迭代器。
• 迭代器可以通过 next() 函数来得到下一个元素，从而支持遍历。
• 生成器是一种特殊的迭代器（迭代器却不见得是生成器）。