4.2.隐性序列

\(4.2\)隐性序列\(Implicit\;Sequences\)

一、概述

1.懒惰计算

  一个序列可以在不直接存储在电脑内存的情况下被代表(\(represent\))。这就是说，我们可以创建一个对象，它能够访问序列型数据集(\(sequential\;dataset\))的所有元素，并且不用预先计算存储所有的元素。作为替代，我们只在需要访问某元素的时候进行计算。

  一个简单的例子是序列类型\(range\)。在\(range\)中，当一个元素被要求计算出来时，\(range\)才会着手计算它。因此，我们可以在不消耗大量内存的情况下表示很大区间范围的整数。只有\(range\)的结尾作为\(range\)对象的一部分被存储了：

>>> r = range(10000, 1000000000)
>>> r[45006230]
45016230

  在这个例子中，r[45006230]是通过第一个元素\(10000\)加上索引(\(index\))\(45006230\)计算出来的。这种在需要某个值的时候才计算它的行为被称作懒惰计算(\(lazy\;computation\))。

2.迭代器

  迭代器(iterator)是一个对象，它为底层的序列型数据集提供循序存取。迭代器抽象有两个组成部分：

• 在序列元素中检索下一个元素\(next\) 的机制。
• 发出结束信号：已经到达序列结束处、没有其他元素存在的信号的机制。

  迭代器的有用之处基于底层的一系列信息(\(series\;of\;data\))可能不会在内存中直接被表示。而迭代器提供了一个依次考虑一系列值的机制，而其他未被考虑的值不需要同时存储在内存中，而是在迭代器访问到它的时候才被计算。

  \(range\)之所以可以对元素进行懒惰计算，是因为序列内部的元素形式是统一的，并且任意一个值都可以容易地通过头元素与尾元素计算出来。而迭代器将懒惰计算的适用类型扩大了，因为这些序列类型不需要自己提供一种计算任意值的方法。相反，它们只需要能依次计算出下一个元素\(next\)即可。

二、\(python\)的迭代器

1.迭代器的功能与性质

  \(python\)迭代器包含__next__信息：询问迭代器序列的下一个元素是什么。对__next__的调用会导致迭代器的改变：它更新当前迭代器的位置。\(python\)在迭代器到达序列末端时会产生StopIteration的异常(\(exception\))。

  下面的$ LetterIter$迭代了一系列字母：

class LetterIter:
        """An iterator over letters of the alphabet in ASCII order."""
        def __init__(self, start='a', end='e'):
            self.next_letter = start
            self.end = end
        def __next__(self):
            if self.next_letter == self.end:
                raise StopIteration
            letter = self.next_letter
            self.next_letter = chr(ord(letter)+1)#iterate to the next number
            return letter

  通过这个类，我们可以用__next__方法或next函数来访问字母：

>>> letter_iter = LetterIter()
>>> letter_iter.__next__()
'a'
>>> letter_iter.__next__()
'b'
>>> next(letter_iter)
'c'
>>> letter_iter.__next__()
'd'
>>> letter_iter.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 12, in next
StopIteration

  迭代器是可改变的(\(mutable\))。当迭代器到达序列的末尾时，它就被耗尽了。\(LetterIter\)只能被迭代一次，当它的__next__方法产生StopIteration的异常后，从这以后的所有迭代都会产生这个异常。一般地，迭代器不会重置。当一个新的实例被创建时，一个新的迭代器也被创建了。

  迭代器也可以通过实现一个不产生异常的__next__方法来表示无限序列，例如下面表示正整数序列的迭代器：

class Positives:
        def __init__(self):
            self.next_positive = 1;
        def __next__(self):
            result = self.next_positive
            self.next_positive += 1
            return result
>>> p = Positives()
>>> next(p)
1
>>> next(p)
2
>>> next(p)
3

2.可迭代性

  一个对象是可迭代的(\(iterable\))，当它的iter方法被调用。可迭代值代表数据集合，并且它们提供了产生一个或多个迭代器的固定表达。

  以下面这个代表一系列有序字母序列的类为例。每次当其__iter__方法被调用，一个新的\(LetterIter\)实例就被创建，这允许了对序列内容的有序访问：

class Letters:
        def __init__(self, start='a', end='e'):
            self.start = start
            self.end = end
        def __iter__(self):
            return LetterIter(self.start, self.end)

  在下面的表达式中，两个源自同一个可迭代序列的迭代器独立地产生各自的单词序列：

>>> b_to_k = Letters('b', 'k')
>>> first_iterator = b_to_k.__iter__()
>>> next(first_iterator)
'b'
>>> next(first_iterator)
'c'
>>> second_iterator = iter(b_to_k)
>>> second_iterator.__next__()
'b'
>>> first_iterator.__next__()
'd'
>>> first_iterator.__next__()
'e'
>>> second_iterator.__next__()
'c'
>>> second_iterator.__next__()
'd'

3.\(for\)语句

  \(for\)语句对迭代器进行操作。可迭代对象可以作为\(for\)语句<expression>结构的值：

for <name> in <expression>:
    <suite>

  为了执行\(for\)语句，\(python\)会计算<expression>，它提供一个可迭代的值。然后，__iter__方法在该值上调用，直到异常被提出。这个过程中，\(python\)将迭代器产生的结果与<name>绑定，然后执行<suite>：

>>> counts = [1, 2, 3]
>>> for item in counts:
        print(item)
1
2
3

  通过先前对迭代器的讲解，我们可以用\(while\)语句实现该\(for\)语句：

items = counts.__iter__()
try:
    while True:
        item = items.__next__()
        print(item)
except StopIteration:
    pass
1
2
3

三、生成器与yield语句

1.引入

  当我们在处理复杂序列、并且需要在计算过程中保存__next__的位置时，单独依靠迭代器显得难以为继。生成器(\(genarator\))允许我们利用\(python\)的特性定义更为复杂的迭代器。

2.生成器与yield语句的声明与执行

  生成器是由被称为生成器函数(\(genarator\;function\))的特殊类函数(\(class\;of\;function\))返回的迭代器。生成器函数与一般函数的区别在于：生成器函数通过yield语句返回元素而不是return语句。

  生成器并不用对象的属性来跟踪序列的过程。相反，他控制生成器函数的执行过程，这个函数会在生成器调用__next__方法后一直运行直到下个yield被执行。\(Letter\)迭代器可以利用生成器更加紧凑地实现：

def letters_generator():
        current = 'a'
        while current <= 'd':
            yield current
            current = chr(ord(current)+1)

>>> for letter in letters_generator():
        print(letter)
a
b
c
d

  尽管我们没有直接地定义__iter__与__next__方法，程序中的yield语句表明我们在定义一个生成器函数。当被调用，生成器函数不会返回一个特定的生成值(\(yielded\;value\))，而是一个生成器(迭代器的一种)，生成器自己会返回生成值。生成器对象有__iter__和__next__方法。

  第一次__next__被调用时，程序执行<body>内语句，即letters_generator，直到遇到yield语句。然后，它暂停执行并返回\(current\)的值。yield语句并不会破坏新创建的环境，它会保存这个环境留着之后计算使用。当__next__被再次调用时，程序从之前停下来的地方开始执行。在对__next__的后续调用中，letters_generator作用域中的\(current\)值和其他绑定名称被保存下来：

>>> letters = letters_generator()
>>> type(letters)
<class 'generator'>
>>> letters.__next__()
'a'
>>> letters.__next__()
'b'
>>> letters.__next__()
'c'
>>> letters.__next__()
'd'
>>> letters.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

3.利用yield语句创建可迭代对象

  在\(python\)中，迭代器只会对底层序列的元素进行一次传递，当这次传递结束后，再次调用__next__方法，迭代器将一直产生StopIteration异常。而许多程序需要多次迭代元素，例如我们想要枚举一个列表的所有\(pair\)：

def all_pairs(s):
        for item1 in s:
            for item2 in s:
                yield (item1, item2)

>>> list(all_pairs([1, 2, 3]))
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

  序列本身不是迭代器，而是可迭代对象。当序列的__iter__方法被调用后，序列会返回一个新的迭代器实例。如果一个可迭代对象在每次调用__iter__后都会返回一个新的新的迭代器实例，它就可以被多次迭代。

  可以通过实现一个可迭代接口来定义新的可迭代类，例如下面\(LettersWithYield\)类就在每次调用__iter__后返回一个新的迭代器：

#create an iterable object
class LettersWithYield:
        def __init__(self, start='a', end='e'):
            self.start = start
            self.end = end
        def __iter__(self):
            next_letter = self.start
            while next_letter < self.end:
                yield next_letter
                next_letter = chr(ord(next_letter)+1)

  该类的__iter__方法是一个生成器函数，它返回一个生成器对象，这个生成器对象生成从a到d的序列后停下。每次我们调用这个方法，一个新的生成器会开始对序列型数据的新的传递：

>>> letters = LettersWithYield()
>>> list(all_pairs(letters))[:5]
[('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a')]

四、流

1.流的概念

  流(\(stream\))提供了隐性表示序列型数据的另一种方法。流是懒惰计算的递归列表(\(recusive\;list\))，与链表结构类似。但与链表不同，流的\(rest\)部分只有在被调用的时候才会被计算。

2.流的实现与调用

  为了实现懒惰计算的操作，流会存储一个计算\(rest\)部分的函数。当这个函数被调用时，它的返回值作为流的属性_rest存储在流的一部分，名称前面的下划线说明它不应该被直接访问。而可访问的rest属性是一个返回流的\(rest\)部分的属性方法。流的基本设计如下：

class Stream:
        """A lazily computed recursive list."""
        class empty(object):
            def __repr__(self):
                return 'Stream.empty'
        empty = empty()
        def __init__(self, first, compute_rest=lambda: empty):
            assert callable(compute_rest), 'compute_rest must be callable.'
            self.first = first
            self._compute_rest = compute_rest
        @property
        def rest(self):
            """Return the rest of the stream, computing it if necessary."""
            if self._compute_rest is not None:
                self._rest = self._compute_rest()
                self._compute_rest = None
            return self._rest
        def __repr__(self):
            return 'Stream({0}, <...>)'.format(repr(self.first))

  流可以像链表一样利用嵌套表达式创建。为了实现懒惰计算，我们采用匿名函数的方法：

s = Stream(1, lambda: Stream(2+3, lambda: Stream(9)))

  这里的\(lambda\)表达式返回计算流剩余部分的方法。可以通过下面的操作访问流中的元素：

>>> r.first
1
>>> s.first
1
>>> r.rest.first
5
>>> s.rest.first
5
>>> r.rest
Rlist(5, Rlist(9))
>>> s.rest
Stream(5, <...>)
#the fact that it will return the empty stream are undiscovered

  当一个\(stream\)实例被创建时，self._rest是\(None\)，这表明实例的\(rest\)部分尚未被计算；当rest属性通过点表达式被访问后，rest的属性方法被调用，触发了self._rest = self._compute_rest()的计算。

  compute_rest函数的关键属性是：它不接受参数，并且返回\(stream\)或\(stream.empty\)。

  懒惰计算允许我们用流表示无限的序列型数据集。例如，可以用以下语句表示正整数集：

def integer_stream(first):
    def compute_rest():
        return integer_stream(first+1)
    return Stream(first, compute_rest)

>>> positives = integer_stream(1)
>>> positives
Stream(1, <...>)
>>> positives.first
1

3.利用流实现序列基本操作

  上述利用高阶函数改变\(compute_rest\)函数的方法可以用于其他序列操作：

  \(a.\)\(map\)映射

def map_stream(fn, s):
        if s is Stream.empty:
            return s
        def compute_rest():
            return map_stream(fn, s.rest)
        return Stream(fn(s.first), compute_rest)

  \(b.\)筛选指定元素

def filter_stream(fn, s):
        if s is Stream.empty:
            return s
        def compute_rest():
            return filter_stream(fn, s.rest)
        if fn(s.first):
            return Stream(s.first, compute_rest)
        else:
            return compute_rest()

  \(c.\)筛选前\(k\)个元素

def first_k_as_list(s, k):
        first_k = []
        while s is not Stream.empty and k > 0:
            first_k.append(s.first)
            s, k = s.rest, k-1
        return first_k

>>> s = integer_stream(3)
>>> s
Stream(3, <...>)
>>> m = map_stream(lambda x: x*x, s)
>>> m
Stream(9, <...>)
>>> first_k_as_list(m, 5)
[9, 16, 25, 36, 49]

  正如链表提供的简单的数据抽象的实现，流也提供了一个简单的函数化递归数据结构，通过高阶函数实现懒惰计算。