递归地按照键排序嵌套的OrderedDict

Question

假设有一个叫 orig 的 OrderedDict，里面存的是普通的字符串和字符串的键值对，但有时候它的值可能是另一个嵌套的 OrderedDict。

我想按照键的字母顺序（从小到大）对 orig 进行排序，并且要做到 递归 排序，也就是说如果里面还有嵌套的字典，也要一并排序。

规则：

• 假设键的字符串是不可预测的
• 假设嵌套可以无限进行，比如第1层到第50层的值都可以是字符串、OrderedDict等。

需要对 sorted 算法进行一些帮助：

import string
from random import choice


orig = OrderedDict((
    ('a', choice(string.digits)),
    ('b', choice(string.digits)),
    ('c', choice(string.digits)),
    ('special', OrderedDict((
        ('a', choice(string.digits)),
        ('b', choice(string.digits)),
        ('c', choice(string.digits)),
    )))
))

sorted_copy = OrderedDict(sorted(orig.iteritems(), ...))

self.assertEqual(orig, sorted_copy)

Answer 1

这是结合了@pelson的回答和@cjbarth的回答，并且加入了key和reverse这两个参数的内容：

def deep_sorted(obj, *, key=None, reverse=False):
    if isinstance(obj, dict):
        return {k: deep_sorted(v, key=key, reverse=reverse) for k, v in sorted(obj.items(), key=key, reverse=reverse)}
    if isinstance(obj, list):
        return [deep_sorted(v, key=key, reverse=reverse) for i, v in sorted(enumerate(obj), key=key, reverse=reverse)]
    return obj

Answer 2

这个方法跟@acushner的解决方案很像，不过是基于类的方式：

from collections import OrderedDict


class SortedDict(OrderedDict):

    def __init__(self, **kwargs):
        super(SortedDict, self).__init__()

        for key, value in sorted(kwargs.items()):
            if isinstance(value, dict):
                self[key] = SortedDict(**value)
            else:
                self[key] = value

用法：

sorted_dict = SortedDict(**unsorted_dict)

Answer 3

我遇到过一个很类似的问题，就是想要得到一个稳定的对象，以便能得到一个稳定的哈希值。不过我的对象里有混合的列表和字典，所以我需要先对所有的字典进行深度排序，然后再对列表进行排序。这是对@acushner的回答的补充：

def deep_sort(obj):
    if isinstance(obj, dict):
        obj = OrderedDict(sorted(obj.items()))
        for k, v in obj.items():
            if isinstance(v, dict) or isinstance(v, list):
                obj[k] = deep_sort(v)

    if isinstance(obj, list):
        for i, v in enumerate(obj):
            if isinstance(v, dict) or isinstance(v, list):
                obj[i] = deep_sort(v)
        obj = sorted(obj, key=lambda x: json.dumps(x))

    return obj

另外，如果你在对象中有需要排序的类，可以先用jsonpickle.dumps()把它们转换成字符串，然后再用json.loads()把它们变回对象，接着用deep_sort()进行排序。如果需要的话，你还可以用json.dumps()和jsonpickle.loads()把它们变回原来的样子，只不过是排序过的（不过这只有在Python 3.6及以上版本有效）。不过对于需要稳定哈希的情况，这一步其实并不是必须的。

Answer 4

编辑：对于Python 3.6及以上版本，@pelson的回答更好

大概是这样的：

def sortOD(od):
    res = OrderedDict()
    for k, v in sorted(od.items()):
        if isinstance(v, dict):
            res[k] = sortOD(v)
        else:
            res[k] = v
    return res

Answer 5

@acushner 的解决方案现在可以在 Python 3.6 及以上版本中简化，因为字典现在会保持插入的顺序。

既然我们可以使用标准字典，代码现在看起来像这样：

def order_dict(dictionary):
    result = {}
    for k, v in sorted(dictionary.items()):
        if isinstance(v, dict):
            result[k] = order_dict(v)
        else:
            result[k] = v
    return result

因为我们可以使用标准字典，所以也可以使用标准的字典推导式，这样代码就简化为：

def order_dict(dictionary):
    return {k: order_dict(v) if isinstance(v, dict) else v
            for k, v in sorted(dictionary.items())}

想了解更多关于 Python 有序字典实现的细节，可以查看这个链接：https://mail.python.org/pipermail/python-dev/2016-September/146327.html。另外，关于这个特性将在 Python 3.7 中成为语言特性的声明，可以参考这个链接：https://mail.python.org/pipermail/python-dev/2017-December/151283.html