Python Generator and Iterator LC 173

Posted on Edited on In Views: Symbols count in article: 1.7k Reading time ≈ 2 mins.

基本知识

Iterable and Iterator

The definition of Iterator: An object representing a stream of data.

  • __next__() is necessary, because it repeated calls to the iterator's __next__().
  • __iter__() is necessary, which returns iterator object itself, because iterator itself needs to be an Iterable. 可以直接return self

The definition of Iterable: An object capable of returning its members one at a time.

  • __iter__() or __getitem__() is necessary to implement Sequence semantics.
  • can be used in for loop.

简单理解：Iterable要有能力产生一个Iterator，Iterator的next要有能力返回下一个iterable里的值。for loop是从Iterable里面拿到一个Iterator，然后对iterator一直请求next，直到StopIteration。

Generator

The definition of Generator: A function returns a generator Iterator.

  • Every time use next() to generator, it will yield the next and label the current frame.

  • It can 'send': g.send(), which allows you to involve the generator.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def gen(num):
        while num > 0:
            tmp = yield num
            if tmp is not None:
                num = tmp
            num -= 1

    g = gen(5)

    first = next(g) # first = g.send(None)
    print(f"first:{first}")
    # >> 5
    print(f"send: {g.send(10)}")
    # >> 9
    for i in g:
        print(i)
    # >> 8, 7, 6, 5, 4, 3, 2, 1

LC-173: Binary Search Tree Iterator

generator solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def __init__(self, root):
    self.last = root
    while self.last and self.last.right:
        self.last = self.last.right
    self.current = None
    self.g = self.iterate(root)

# @return a boolean, whether we have a next smallest number
def hasNext(self):
    return self.current is not self.last

# @return an integer, the next smallest number
def next(self):
    return next(self.g)
    
def iterate(self, node):
    if node is None:
        return
    for x in self.iterate(node.left):
        yield x
    self.current = node
    yield node.val
    for x in self.iterate(node.right):
        yield x

疑问： 为何这里要用next(self.g)，而不是直接self.g？

个人理解： 这里的next非def中的next，而是generator里的__next__()，当把def中的next改为其他名称时，运行结果相同。另外self.g是一个generator，因为iterate用到了yield，直接return self.g是generator，而不是具体数字。

Related Posts