<jupyter_start><jupyter_text>[5.2 隐式序列](http://www-inst.eecs.berkeley.edu/~cs61a/sp12/book/streams.htmlimplicit-sequences)序列可以使用一种程序结构来表示，它不将每个元素显式储存在内存中，这是高效处理有序数据的核心概念。为了将这个概念用于实践，我们需要构造对象来提供序列中所有元素的访问，但是不要事先把所有元素计算出来并储存。这个概念的一个简单示例就是第二章出现的`range`序列类型。`range`表示连续有界的整数序列。但是，它的每个元素并不显式在内存中表示，当元素从`range`中获取时，才被计算出来。所以，我们可以表示非常大的整数范围。只有范围的结束位置才被储存为`range`对象的一部分，元素都被凭空计算出来。<jupyter_code>r = range(10000, 1000000000)
r[45006230]<jupyter_output><empty_output><jupyter_text>这个例子中，当构造范围示例时，并不是这个范围内的所有 999,990,000 个整数都被储存。反之，范围对象将第一个元素 10,000 与下标相加 45,006,230 来产生第 45,016,230 个元素。计算所求的元素值并不从现有的表示中获取，这是惰性计算的一个例子。计算机科学将惰性作为一种重要的计算工具加以赞扬。迭代器是提供底层有序数据集的有序访问的对象。迭代器在许多编程语言中都是内建对象，包括 Python。迭代器抽象拥有两个组成部分：一种获取底层元素序列的下一个元素的机制，以及一种标识元素序列已经到达末尾，没有更多剩余元素的机制。在带有内建对象系统的编程语言中，这个抽象通常相当于可以由类实现的特定接口。Python 的迭代器接口会在下一节中描述。迭代器的实用性来源于一个事实，底层数据序列并不能显式在内存中表达。迭代器提供了一种机制，可以依次计算序列中的每个值，但是所有元素不需要连续储存。反之，当下个元素从迭代器获取的时候，这个元素会按照请求计算，而不是从现有的内存来源中获取。范围可以惰性计算序列中的元素，因为序列的表示是统一的，并且任何元素都可以轻易从范围的起始和结束位置计算出来。迭代器支持更广泛的底层有序数据集的惰性生成，因为它们不需要提供底层序列任意元素的访问途径。反之，它们仅仅需要按照顺序，在每次其它元素被请求的时候，计算出序列的下一个元素。虽然不像序列可访问任意元素那样灵活（叫做随机访问），有序数据序列的顺序访问对于数据处理应用来说已经足够了。 5.2.1 Python 迭代器Python 迭代器接口包含两个消息。`__next__`消息向迭代器获取所表示的底层序列的下一个元素。为了对`__next__`方法调用做出回应，迭代器可以执行任何计算来获取或计算底层数据序列的下一个元素。`__next__`的调用让迭代器产生变化：它们向前移动迭代器的位置。所以多次调用`__next__`会有序返回底层序列的元素。在`__next__`的调用过程中，Python 通过`StopIteration`异常，来表示底层数据序列已经到达末尾。下面的`Letters`类迭代了从`a`到`d`字母的底层序列。成员变量`current`储存了序列中的当前字母。`__next__`方法返回这个字母，并且使用它来计算`current`的新值。<jupyter_code>class Letters(object):
    def __init__(self):
        self.current = 'a'
    def __next__(self):
        if self.current > 'd':
            raise StopIteration
        result = self.current
        self.current = chr(ord(result)+1)
        return result
    def __iter__(self):
        return self<jupyter_output><empty_output><jupyter_text>`__iter__`消息是 Python 迭代器所需的第二个消息。它只是简单返回迭代器，它对于提供迭代器和序列的通用接口很有用，在下一节会描述。使用这个类，我们就可以访问序列中的字母：<jupyter_code>letters = Letters()
letters.__next__()
letters.__next__()
letters.__next__()
letters.__next__()
letters.__next__()<jupyter_output><empty_output><jupyter_text>`Letters`示例只能迭代一次。一旦`__next__()`方法产生了`StopIteration`异常，它就从此之后一直这样了。除非创建新的实例，否则没有办法来重置它。迭代器也允许我们表示无限序列，通过实现永远不会产生`StopIteration`异常的`__next__`方法。例如，下面展示的`Positives`类迭代了正整数的无限序列：<jupyter_code>class Positives(object):
    def __init__(self):
        self.current = 0;
    def __next__(self):
        result = self.current
        self.current += 1
        return result
    def __iter__(self):
        return self<jupyter_output><empty_output><jupyter_text>5.2.2 `for`语句Python 中，序列可以通过实现`__iter__`消息用于迭代。如果一个对象表示有序数据，它可以在`for`语句中用作可迭代对象，通过回应`__iter__`消息来返回迭代器。这个迭代器应拥有`__next__()`方法，依次返回序列中的每个元素，最后到达序列末尾时产生`StopIteration`异常。<jupyter_code>counts = [1, 2, 3]
for item in counts:
    print(item)<jupyter_output>1
2
3<jupyter_text>在上面的实例中，`counts`列表返回了迭代器，作为`__iter__()`方法调用的回应。`for`语句之后反复调用迭代器的`__next__()`方法，并且每次都将返回值赋给`item`。这个过程一直持续，直到迭代器产生了`StopIteration`异常，这时`for`语句就终止了。使用我们关于迭代器的知识，我们可以拿`while`、赋值和`try`语句实现`for`语句的求值规则：<jupyter_code>i = counts.__iter__()
try:
    while True:
        item = i.__next__()
        print(item)
except StopIteration:
     pass<jupyter_output>1
2
3<jupyter_text>在上面，调用`counts`的`__iter__`方法所返回的迭代器绑定到了名称`i`上面，便于依次获取每个元素。`StopIteration`异常的处理子句不做任何事情，但是这个异常的处理提供了退出`while`循环的控制机制。 5.2.3 生成器和`yield`语句上面的`Letters`和`Positives`对象需要我们引入一种新的字段，`self.current`，来跟踪序列的处理过程。在上面所示的简单序列中，这可以轻易实现。但对于复杂序列，`__next__()`很难在计算中节省空间。生成器允许我们通过利用 Python 解释器的特性定义更复杂的迭代。生成器是由一类特殊函数，叫做生成器函数返回的迭代器。生成器函数不同于普通的函数，因为它不在函数体中包含`return`语句，而是使用`yield`语句来返回序列中的元素。生成器不使用任何对象属性来跟踪序列的处理过程。它们控制生成器函数的执行，每次`__next__`方法调用时，它们执行到下一个`yield`语句。`Letters`迭代可以使用生成器函数实现得更加简洁。<jupyter_code>def letters_generator():
    current = 'a'
    while current <= 'd':
        yield current
        current = chr(ord(current)+1)
for letter in letters_generator():
    print(letter)<jupyter_output>a
b
c
d<jupyter_text>即使我们永不显式定义`__iter__()`或`__next__()`方法，Python 会理解当我们使用`yield`语句时，我们打算定义生成器函数。调用时，生成器函数并不返回特定的产出值，而是返回一个生成器（一种迭代器），它自己就可以返回产出的值。生成器对象拥有`__iter__`和`__next__`方法，每个对`__next__`的调用都会从上次停留的地方继续执行生成器函数，直到另一个`yield`语句执行的地方。`__next__`第一次调用时，程序从`letters_generator`的函数体一直执行到进入`yield`语句。之后，它暂停并返回`current`值。`yield`语句并不破坏新创建的环境，而是为之后的使用保留了它。当`__next__`再次调用时，执行在它停留的地方恢复。`letters_generator`作用域中`current`和任何所绑定名称的值都会在随后的`__next__`调用中保留。我们可以通过手动调用`__next__()`来遍历生成器：<jupyter_code>letters = letters_generator()
type(letters)
letters.__next__()
letters.__next__()
letters.__next__()
letters.__next__()
letters.__next__()<jupyter_output><empty_output><jupyter_text>在第一次`__next__()`调用之前，生成器并不会开始执行任何生成器函数体中的语句。 5.2.4 可迭代对象Python 中，迭代只会遍历一次底层序列的元素。在遍历之后，迭代器在`__next__()`调用时会产生`StopIteration`异常。许多应用需要迭代多次元素。例如，我们需要对一个列表迭代多次来枚举所有的元素偶对：<jupyter_code>def all_pairs(s):
    for item1 in s:
        for item2 in s:
            yield (item1, item2)
list(all_pairs([1, 2, 3]))<jupyter_output><empty_output><jupyter_text>序列本身不是迭代器，但是它是可迭代对象。Python 的可迭代接口只包含一个消息，`__iter__`，返回一个迭代器。Python 中内建的序列类型在`__iter__`方法调用时，返回迭代器的新实例。如果一个可迭代对象在每次调用`__iter__`时返回了迭代器的新实例，那么它就能被迭代多次。新的可迭代类可以通过实现可迭代接口来定义。例如，下面的可迭代对象`LetterIterable`类在每次调用`__iter__`时返回新的迭代器来迭代字母。<jupyter_code>class LetterIterable(object):
    def __iter__(self):
        current = 'a'
        while current <= 'd':
            yield current
            current = chr(ord(current)+1)<jupyter_output><empty_output><jupyter_text>`__iter__`方法是个生成器函数，它返回一个生成器对象，产出从`'a'`到`'d'`的字母。`Letters`迭代器对象在单次迭代之后就被“用完”了，但是`LetterIterable`对象可被迭代多次。所以，`LetterIterable`示例可以用于`all_pairs`的参数。<jupyter_code>letters = LetterIterable()
all_pairs(letters).__next__()<jupyter_output><empty_output><jupyter_text>5.2.5 流流提供了一种隐式表示有序数据的最终方式。流是惰性计算的递归列表。就像第三章的`Rlist`类那样，`Stream`实例可以响应对其第一个元素和剩余部分的获取请求。同样，`Stream`的剩余部分还是`Stream`。然而不像`RList`，流的剩余部分只在查找时被计算，而不是事先存储。也就是说流的剩余部分是惰性计算的。为了完成这个惰性求值，流会储存计算剩余部分的函数。无论这个函数在什么时候调用，它的返回值都作为流的一部分，储存在叫做`_rest`的属性中。下划线表示它不应直接访问。可访问的属性`rest`是个方法，它返回流的剩余部分，并在必要时计算它。使用这个设计，流可以储存计算剩余部分的方式，而不用总是显式储存它们。<jupyter_code>class Stream(object):
    """A lazily computed recursive list."""
    def __init__(self, first, compute_rest, empty=False):
        self.first = first
        self._compute_rest = compute_rest
        self.empty = empty
        self._rest = None
        self._computed = False
    @property
    def rest(self):
        """Return the rest of the stream, computing it if necessary."""
        assert not self.empty, 'Empty streams have no rest.'
        if not self._computed:
            self._rest = self._compute_rest()
            self._computed = True
        return self._rest
    def __repr__(self):
        if self.empty:
            return '<empty stream>'
        return 'Stream({0}, <compute_rest>)'.format(repr(self.first))
Stream.empty = Stream(None, None, True)<jupyter_output><empty_output><jupyter_text>递归列表可使用嵌套表达式来定义。例如，我们可以创建`RList`，来表达`1`和`5`的序列，像下面这样：<jupyter_code>class Rlist(object):
    """A recursive list consisting of a first element and the rest."""
    class EmptyList(object):
        def __len__(self):
            return 0
    empty = EmptyList()
    def __init__(self, first, rest=empty):
        self.first = first
        self.rest = rest
    def __repr__(self):
        args = repr(self.first)
        if self.rest is not Rlist.empty:
            args += ', {0}'.format(repr(self.rest))
        return 'Rlist({0})'.format(args)
    def __len__(self):
        return 1 + len(self.rest)
    def __getitem__(self, i):
        if i == 0:
            return self.first
        return self.rest[i-1]
r = Rlist(1, Rlist(2+3, Rlist.empty))<jupyter_output><empty_output><jupyter_text>与之类似，我们可以创建一个`Stream`来表示相同序列。`Stream`在请求剩余部分之前，并不会实际计算下一个元素`5`。<jupyter_code>s = Stream(1, lambda: Stream(2+3, lambda: Stream.empty))<jupyter_output><empty_output><jupyter_text>这里，`1`是流的第一个元素，后面的`lambda`表达式是用于计算流的剩余部分的函数。被计算的流的第二个元素又是一个返回空流的函数。访问递归列表`r`和流`s`中的元素拥有相似的过程。但是，`5`储存在了`r`之中，而对于`s`来说，它在首次被请求时通过加法来按要求计算。<jupyter_code>r.first
s.first
r.rest.first
s.rest.first
r.rest
s.rest
def make_integer_stream(first=1):
    def compute_rest():
        return make_integer_stream(first+1)
    return Stream(first, compute_rest)
ints = make_integer_stream()
ints
ints.first<jupyter_output><empty_output><jupyter_text>当`make_integer_stream`首次被调用时，它返回了一个流，流的`first`是序列中第一个整数（默认为`1`）。但是，`make_integer_stream`实际是递归的，因为这个流的`compute_rest`以自增的参数再次调用了`make_integer_stream`。这会让`make_integer_stream`变成递归的，同时也是惰性的。<jupyter_code>ints.first
ints.rest.first
ints.rest.rest<jupyter_output><empty_output><jupyter_text>无论何时请求整数流的`rest`，都仅仅递归调用`make_integer_stream`。操作序列的相同高阶函数 -- `map`和`filter` -- 同样可应用于流，虽然它们的实现必须修改来惰性调用它们的参数函数。`map_stream`在一个流上映射函数，这会产生一个新的流。局部定义的`compute_rest`函数确保了无论什么时候`rest`被计算出来，这个函数都会在流的剩余部分上映射。<jupyter_code>def map_stream(fn, s):
    if s.empty:
        return s
    def compute_rest():
        return map_stream(fn, s.rest)
    return Stream(fn(s.first), compute_rest)<jupyter_output><empty_output><jupyter_text>流可以通过定义`compute_rest`函数来过滤，这个函数在流的剩余部分上调用过滤器函数。如果过滤器函数拒绝了流的第一个元素，剩余部分会立即计算出来。因为`filter_stream`是递归的，剩余部分可能会多次计算直到找到了有效的`first`元素。<jupyter_code>def filter_stream(fn, s):
    if s.empty:
        return s
    def compute_rest():
        return filter_stream(fn, s.rest)
    if fn(s.first):
        return Stream(s.first, compute_rest)
    return compute_rest()<jupyter_output><empty_output><jupyter_text>`map_stream`和`filter_stream`展示了流式处理的常见模式：无论流的剩余部分何时被计算，局部定义的`compute_rest`函数都会对流的剩余部分递归调用某个处理函数。为了观察流的内容，我们需要将其截断为有限长度，并转换为 Python `list`。<jupyter_code>def truncate_stream(s, k):
    if s.empty or k == 0:
        return Stream.empty
    def compute_rest():
        return truncate_stream(s.rest, k-1)
    return Stream(s.first, compute_rest)
def stream_to_list(s):
    r = []
    while not s.empty:
        r.append(s.first)
        s = s.rest
    return r<jupyter_output><empty_output><jupyter_text>这些便利的函数允许我们验证`map_stream`的实现，使用一个非常简单的例子，从`3`到`7`的整数平方。<jupyter_code>s = make_integer_stream(3)
s
m = map_stream(lambda x: x*x, s)

m
stream_to_list(truncate_stream(m, 5))<jupyter_output><empty_output><jupyter_text>我们可以使用我们的`filter_stream`函数来定义素数流，使用埃拉托斯特尼筛法（sieve of Eratosthenes），它对整数流进行过滤，移除第一个元素的所有倍数数值。通过成功过滤出每个素数，所有合数都从流中移除了。<jupyter_code>def primes(pos_stream):
        def not_divible(x):
            return x % pos_stream.first != 0
        def compute_rest():
            return primes(filter_stream(not_divible, pos_stream.rest))
        return Stream(pos_stream.first, compute_rest)<jupyter_output><empty_output><jupyter_text>通过截断`primes`流，我们可以枚举素数的任意前缀：<jupyter_code>p1 = primes(make_integer_stream(2))
stream_to_list(truncate_stream(p1, 7))<jupyter_output><empty_output><jupyter_text>流和迭代器不同，因为它们可以多次传递给纯函数，并且每次都产生相同的值。素数流并没有在转换为列表之后“用完”。也就是说，在将流的前缀转换为列表之后，`p1`的第一个元素仍旧是`2`。<jupyter_code>p1.first<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12209737827715356, 'fraction_numerical': 0.012172284644194757, 'mean_word_length': 7.32501948558067, 'pattern_counts': {'":': 0, '<': 94, '<?xml version=': 0, '>': 93, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '23', 'dir': 'jupyter-structured-clean-dedup', 'id': '628055', 'license': 'MIT', 'n_tokens_mistral': 6211, 'n_tokens_neox': 6681, 'n_words': 400, 'path': 'Chapter 5/Section 5.2.ipynb', 'repo_name': 'allenwoods/sicp-jupyter', 'size': '10680'}