python - 如何创建带有递归的生成器？

Question

Hacker's Delight 第二版中的算法

移植到Python

一个简单的希尔伯特曲线类。

class Hilbert():

    def __init__(self,order=1):
            
            self.x = -1 
            self.y = 0     
            self._step(0)
            self._hil(0, 1, order)
    
    def _hil(self, dirs, rot, order):
        if (order == 0): 
            return

        dirs += rot
        self._hil(dirs, -rot, (order-1))
        self._step(dirs)
        dirs -= rot
        self._hil(dirs, rot, (order-1))
        self._step(dirs)
        self._hil(dirs, rot, (order-1))
        dirs -= rot
        self._step(dirs)
        self._hil(dirs, -rot, (order-1))
         
        
    def _step(self, dirs):
        dirs %= 4
        
        if dirs == 0:
            self.x += 1
        elif dirs == 1:
            self.y += 1
        elif dirs == 2:
            self.x -= 1
        else:
            self.y -= 1 
        #prints all points 
        #print(self.x,self.y)
        #Could I "iterate" from here.

所以我想要的是每次调用 next() 时都会给出 (x,y) 的东西。我尝试自己这样做，但无法让它发挥作用，所以任何帮助将不胜感激。我需要重写它才能与生成器一起使用吗？ Source

Answer 1

我认为您至少要做的一部分是将 _hil 转换为生成器函数，该函数在每次调用后生成 x, y 对_step？如果是这样，那就很容易了。

最困难的部分是那些递归调用。但这一点也不难。这正是 yield from用于:* 采用一些迭代器(如对生成器函数的递归调用)并生成其每个值。**

然后是简单的部分，即每次调用 _step 之后非递归生成 x, y 对。您可以在每次调用后通过显式的 yield self.x, self.y 来实现这一点。或者您可以更改_step以添加return self.x, self.y，这样您就可以yield self._step(dirs)。但您也可以将 _step 更改为仅迭代一个值的迭代器，然后您也可以yield 它。 (这里没有真正的优势，但我认为值得展示，以便您可以思考它是如何工作的 - 特别是因为您在 _step 中问“我可以从这里迭代吗？”。)

def _hil(self, dirs, rot, order):
    if (order == 0): 
        return

    dirs += rot
    yield from self._hil(dirs, -rot, (order-1))
    yield from self._step(dirs)
    dirs -= rot
    yield from self._hil(dirs, rot, (order-1))
    yield from self._step(dirs)
    yield from self._hil(dirs, rot, (order-1))
    dirs -= rot
    yield from self._step(dirs)
    yield from self._hil(dirs, -rot, (order-1))

def _step(self, dirs):
    # existing code
    yield self.x, self.y

<小时/>

但是现在您已经得到了仅调用 _hil 且对结果不执行任何操作的 __init__。那不是很有用。也许您正在尝试将 Hilbert 类本身转换为迭代器类？

在这种情况下，最简单的事情就是存储生成器迭代器并委托(delegate)给它:

def __init__(self, order=1):
    self.x = -1 
    self.y = 0     
    self._step(0)
    self.iter = self._hil(0, 1, order)

def __iter__(self):
    return self

def __next__(self):
    return next(self.iter)

<小时/>

但是，此时，我不确定为什么您需要将其作为一个类。 x 和 y 实际上并不是对象状态的一部分，它们是生成器状态的一部分，如果您只使用局部变量，Python 会神奇地处理这些状态在 _hil 中(以及在 _step 中传递正常参数和返回值)。唯一的其他状态是 self.iter，它是必需的，因为您正在编写一个类而不是一个函数。

<小时/>

_{* 事实上，事实证明它的好处远不止于此，如 Greg Ewing describes amazingly well ;我们不会有asyncio没有它。但将其添加到语言中的最初原因是“委托(delegate)给子生成器的语法”。}

** 请注意，这仅在您拥有 yield from 时才有效——即 Python 3.3 或更高版本。如果您仍在使用 Python 2.x，并且 yield from 不足以让您升级，您可以模拟它的一些用途 - 包括这个 -将每个产量从鸡蛋更改为鸡蛋中的鸡蛋:产量鸡蛋。它的可读性不会那么好，而且会明显变慢，但它会起作用。