1

我想为我的“玩具”Trie 实现编写一个迭代器。

添加已经像这样工作：

class Trie:
    def __init__(self):
        self.root = dict()
        pass
    def add(self, string, value):
        global nops
        current_dict = self.root
        for letter in string:
           nops += 1
           current_dict = current_dict.setdefault(letter, {})
        current_dict = current_dict.setdefault('value', value)              
        pass

添加的输出如下所示：

trie = Trie()
trie.add("hello",1)
trie.add("world",2)
trie.add("worlds",12)
print trie.root
{'h': {'e': {'l': {'l': {'o': {'value': 1}}}}}, 'w': {'o': {'r': {'l': {'d': {'s': {'value': 12}, 'value': 2}}}}}}

我知道，我需要一个__iter__andnext方法。

def __iter__(self):
    self.root.__iter__()
    pass

 def next(self):
    print self.root.next()

但是AttributeError: 'dict' object has no attribute 'next'。我该怎么做？

[更新] 在完美的世界中，我希望输出是一个包含所有单词/条目及其对应值的字典。

4

2 回答 2

2

你的__iter__特殊方法应该返回一个迭代器；也就是说，您可以调用的类的对象next。玩具迭代器类将类似于：

class MyIterator:
    def __init__(self):
        self.i = 10
    def next(self):
        self.i -= 1
        if self.i == 0:
            raise StopIteration
        else:
            return self.i

除非你有一个自然的对象可以调用，否则制作一个生成器iter通常更容易：__iter__

def __iter__(self):
    for i in range(10)
        yield i

这是您的基于堆栈的生成器迭代器Trie：

    def __iter__(self):
        stack = [('', self.root)]
        while stack:
            prefix, d = stack.pop()
            for k, v in d.items():
                if k == 'value':
                    yield prefix, v
                else:
                    stack.append((prefix + k, v))

您也可以尝试递归编写它，尽管您需要使用itertools.chainor yield from（仅从 Python 3.3 开始）。

于 2012-11-14T16:52:23.360 回答
0

假设我正确理解您在迭代器中寻找的内容，我会按照这些思路做一些事情（注意添加的字段__init__：

class Trie:
    def __init__(self):
        self.root = dict()
        self.stack = ''

    def add(self, string, value):
        """map it to the given value."""
        global nops
        current_dict = self.root
        for letter in string:
           nops += 1
           current_dict = current_dict.setdefault(letter, {})
        current_dict = current_dict.setdefault('value', value)              
        pass

    def __iter__(self, input_dict=None):
        if not input_dict:
            input_dict = self.root

        if 'value' in input_dict:
            yield (self.stack, input_dict['value'])

        keys = [x for x in input_dict.keys() if x != 'value']
        for key in keys:
            self.stack += key
            for item in self.__iter__(input_dict[key]):
                yield item
            self.stack = self.stack[:-1]

那会给你：

trie = Trie()
trie.add("hello", 1)
trie.add("world", 2)
trie.add("worlds", 12)
print trie.root
print [x for x in trie]

# {'h': {'e': {'l': {'l': {'o': {'value': 1}}}}}, 'w': {'o': {'r': {'l': {'d': {'s': {'value': 12}, 'value': 2}}}}}}
# [('hello', 1), ('world', 2), ('worlds', 12)]

因此，可以在没有itertools.chainor的情况下递归地执行此操作yield from。

于 2012-11-14T17:31:50.907 回答