1

Hacker's Delight 2nd Edition 中的算法

移植到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) 的东西。我自己尝试过这样做，但无法使其正常工作，因此将不胜感激。我是否必须重写它才能使用生成器？ 资源

4

1 回答 1

1

我认为您尝试做的至少一部分是_hil变成一个生成器函数，它x, y在每次调用_step? 如果是这样，那很容易。

困难的部分是那些递归调用。但这一点都不难。这正是yield from它的用途：* 采用一些迭代器（如对生成器函数的递归调用）并产生它的每个值。**

然后是简单的部分，x, y每次调用_step. 您可以yield self.x, self.y在每次通话后显式执行此操作。或者你可以改_step加一个return self.x, self.y，这样就可以了yield self._step(dirs)。但是你也可以改成_step只迭代一个值的迭代器，然后你也可以yield from。（这里没有真正的优势，但我认为它值得展示，这样你就可以思考它是如何工作的——特别是因为你问“我可以从这里迭代吗？”在_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

但是现在你已经得到了它__init__，它只是调用_hil并且对结果不做任何事情。这不是很有用。也许您正试图将Hilbert类本身变成一个迭代器类？

在这种情况下，最简单的做法是存储生成器迭代器并委托给它：

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 所描述的那样，它的好处远不止于此；我们不会asyncio没有它。但是将它添加到语言中的最初原因是“委托给子生成器的语法”。

** 请注意，这仅在您拥有 yield from- 即 Python 3.3 或更高版本时才有效。如果您仍在使用 Python 2.x，并且yield from还不足以让您升级，您可以通过将 every更改yield from eggs为for egg in eggs: yield egg. 它不会那么可读，并且会明显变慢，但它会起作用。

于 2014-11-21T01:53:55.923 回答