Python中有序字典的有序字典

Question

我需要一个字典数据结构，可以存储如下所示的字典：

custom = {1: {'a': np.zeros(10), 'b': np.zeros(100)}, 
          2: {'c': np.zeros(20), 'd': np.zeros(200)}}

但问题是，我的代码中需要多次迭代这个数据结构。每次迭代时，我需要保证迭代顺序的正确性，因为这个复杂数据结构中的所有元素都映射到一个一维数组（如果您愿意，可以理解为串行化），因此顺序很重要。我考虑编写一个有序的有序字典，但我不确定这是否是正确的解决方案，因为似乎我可能选择了错误的数据结构。对于我的情况，什么是最适当的解决方案？

更新：

这是我目前想到的：

class Test(list):

    def __init__(self, *args, **kwargs):

        super(Test, self).__init__(*args, **kwargs)

        for k,v in args[0].items():
            self[k] = OrderedDict(v)

        self.d = -1
        self.iterator = iter(self[-1].keys())
        self.etype = next(self.iterator)
        self.idx = 0


    def __iter__(self):
        return self

    def __next__(self):

        try:
            self.idx += 1
            return self[self.d][self.etype][self.idx-1]

        except IndexError:

            self.etype = next(self.iterator)
            self.idx = 0
            return self[self.d][self.etype][self.idx-1]

    def __call__(self, d):

        self.d = -1 - d
        self.iterator = iter(self[self.d].keys())
        self.etype = next(self.iterator)
        self.idx = 0
        return self


def main(argv=()):

    tst = Test(elements)
    for el in tst:
        print(el)
    # loop over a lower dimension
    for el in tst(-2):
        print(el)

    print(tst)


    return 0

if __name__ == "__main__":
    sys.exit(main())

在这个有序结构中，我可以进行任意次迭代，并且我实现了__call__以便我可以迭代较低的维度。我不喜欢列表中没有较低维度时它不会给我任何错误的事实。我也觉得每次调用return self[self.d][self.etype][self.idx-1]比原始字典迭代效率更低。这是真的吗？我该如何改进？

- aaragon

Answer 1

我认为使用OrderedDict是最好的方法。它们是内置的且相对较快:

custom = OrderedDict([(1, OrderedDict([('a', np.zeros(10)),
                                       ('b', np.zeros(100))])),
                      (2, OrderedDict([('c', np.zeros(20)),
                                       ('d', np.zeros(200))]))])

如果你想轻松地遍历你的数据结构内容，你可以提供一个实用函数来进行操作：

def iter_over_contents(data_structure):
    for delem in data_structure.values():
        for v in delem.values():
            for row in v:
                yield row

请注意，在Python 3.3及以上版本中，允许使用yield from <expression>，可以消除最后的for循环。

def iter_over_contents(data_structure):
    for delem in data_structure.values():
        for v in delem.values():
            yield from v

有了其中一个，您就可以编写类似以下内容的代码：

for elem in iter_over_contents(custom):
    print(elem)

并且隐藏复杂性。

虽然您可以定义自己的类来尝试封装此数据结构，并使用像iter_over_contents()生成器函数作为其__iter__()方法，但这种方法可能会更慢，并且不允许使用两个级别的索引表达式，如以下示例：

custom[1]['b']

使用嵌套字典（或者像我在另一个回答中展示的OrderedDefaultdict）可以实现。

- martineau

Answer 2

这里有另一种选择，使用OrderedDefaultdict来定义你想要的树形数据结构。我正在重复使用我在另一个答案中的定义。

为了使用它，你必须确保条目按照你以后访问它们的顺序被定义。

class OrderedDefaultdict(OrderedDict):
    def __init__(self, *args, **kwargs):
        if not args:
            self.default_factory = None
        else:
            if not (args[0] is None or callable(args[0])):
                raise TypeError('first argument must be callable or None')
            self.default_factory = args[0]
            args = args[1:]
        super(OrderedDefaultdict, self).__init__(*args, **kwargs)

    def __missing__ (self, key):
        if self.default_factory is None:
            raise KeyError(key)
        self[key] = default = self.default_factory()
        return default

    def __reduce__(self):  # optional, for pickle support
        args = (self.default_factory,) if self.default_factory else ()
        return self.__class__, args, None, None, self.iteritems()

Tree = lambda: OrderedDefaultdict(Tree)

custom = Tree()
custom[1]['a'] = np.zeros(10)
custom[1]['b'] = np.zeros(100)
custom[2]['c'] = np.zeros(20)
custom[2]['d'] = np.zeros(200)

我不确定我理解你的后续问题。如果数据结构仅限于两个级别，您可以使用嵌套的for循环按照定义的顺序迭代其元素。例如：

for key1, subtree in custom.items():
    for key2, elem in subtree.items():
        print('custom[{!r}][{!r}]: {}'.format(key1, key2, elem))

（在 Python 2 中，您需要使用 iteritems() 而不是 items()。）

- martineau

---

我的意思是仅使用一个循环遍历整个数据结构会很好。我试图通过覆盖__iter__和__next__方法来实现这一点，但我失败了。我还想问你能否解释一下你写的代码，因为对我来说那是相当高级的Python。 - aaragon

我的答案中的代码是在Python中实现autovivification的一个示例，它是从链接的维基百科文章中的Python代码衍生而来（该文章还包含一些其他参考资料）。 - martineau

我想要的是您所提出的数据结构，但是除了像您在答案末尾展示的那样使用两个循环迭代字典元素之外，我希望用户输入for i in custom:，并且由于您正在使用有序字典，因此遍历字典时顺序始终相同。 您认为通过重写__iter__和next()可以实现这一点吗？ - aaragon

是的，就像那样。那么您建议我从您的类继承还是使用聚合？我确实想要遍历字典的值，但在内部，我希望值与字典一起被排序。因此，如果我理解正确，我将创建另一个类，在该类中，我将您的数据结构作为变量，并实现__iter__和next（）方法进行迭代，这正确吗？ - aaragon

我认为最好将其表示为“具有”而不是“是”关系——因此尝试使用对象组合（而不是聚合），而不是继承。但由于多级索引的存在可能难以实现。不过，除此之外，你似乎理解了我的建议。 - martineau

Answer 3

你可以只使用一个字典列表吗？

custom = [{'a': np.zeros(10), 'b': np.zeros(100)},
          {'c': np.zeros(20), 'd': np.zeros(200)}]

如果外部字典是您需要的唯一按正确顺序排列的字典，则此方法可行。您仍然可以使用custom[0]或custom[1]访问内部字典（注意，现在索引从0开始）。

如果没有使用所有索引，则可以执行以下操作：

custom = [None] * maxLength   # maximum dict size you expect

custom[1] = {'a': np.zeros(10), 'b': np.zeros(100)}
custom[2] = {'c': np.zeros(20), 'd': np.zeros(200)}

- Lisa

---

我不能使用这个，因为1可能存在也可能不存在，同样的情况也适用于0和2。 - aaragon

啊，好的，所以你实际上需要外部 dict 中的键 - 没关系，抱歉误解了！ - Lisa

@aargon 我编辑了答案，保留了作为你外层“dict”键的索引，并将所有不可用的元素设置为“None”。 - Lisa

你的解决方案仍未排序，例如循环custom[1]可以获取a然后是b的元素，而在另一次迭代中，则是b然后是a的元素。这可以通过使用OrderedDict来解决，但问题仍然存在：是否有更好的方法来处理这个问题？ - aaragon

Answer 4

当你首先对键进行排序时，可以在迭代时修复它们的顺序：

for key in sorted(custom.keys()):
    print(key, custom[key])

如果您想减少sorted()调用次数，您可能希望将键存储在额外的列表中，该列表将作为您的迭代顺序：

ordered_keys = sorted(custom.keys())
for key in ordered_keys:
    print(key, custom[key])

你应该准备好对数据结构进行尽可能多的迭代。

- jbndlr

---

我在这个数据结构上进行了许多次迭代。 - aaragon

该结构在整个应用程序中被迭代多次，我想做的是提供一种更用户友好的方法来输入 for k,v in custom.items(): for i,r in enumerate(v): # etc.。 - aaragon

嗯，这似乎是一个完全不同的问题。 - jbndlr

确实是这样，请看这里，但我必须仔细考虑，因此我首先选择正确的数据结构。 - aaragon