Sorting A Nested Ordereddict By Key, Recursively

Say orig is an OrderedDict which contains normal string:string key value pairs, but sometimes the value could be another, nested OrderedDict. I want to sort orig by key, alphabetic

Solution 1:

EDIT: for python 3.6+, @pelson's answer is better

something like:

defsortOD(od):
    res = OrderedDict()
    for k, v insorted(od.items()):
        ifisinstance(v, dict):
            res[k] = sortOD(v)
        else:
            res[k] = v
    return res

Solution 2:

@acushner's solution can now be simplified in python3.6+ as dictionaries now preserve their insertion order.

Given we can now use the standard dictionary, the code now looks like:

deforder_dict(dictionary):
    result = {}
    for k, v insorted(dictionary.items()):
        ifisinstance(v, dict):
            result[k] = order_dict(v)
        else:
            result[k] = v
    return result

Because we can use standard dictionaries, we can also use standard dictionary comprehensions, so the code boils down to:

deforder_dict(dictionary):
    return {k: order_dict(v) ifisinstance(v, dict) else v
            for k, v insorted(dictionary.items())}

See also https://mail.python.org/pipermail/python-dev/2016-September/146327.html for detail on python's ordered dictionary implementation. Also, the pronouncement that this will be a language feature as of python 3.7: https://mail.python.org/pipermail/python-dev/2017-December/151283.html

Solution 3:

I faced a very similar issue with getting a stable object so I could get a stable hash, except I had objects with a mix of lists and dictionaries, so I had to sort all the dictionaries, depth first, and then sort the lists. This extends @acushner's answer:

defdeep_sort(obj):
    ifisinstance(obj, dict):
        obj = OrderedDict(sorted(obj.items()))
        for k, v in obj.items():
            ifisinstance(v, dict) orisinstance(v, list):
                obj[k] = deep_sort(v)

    ifisinstance(obj, list):
        for i, v inenumerate(obj):
            ifisinstance(v, dict) orisinstance(v, list):
                obj[i] = deep_sort(v)
        obj = sorted(obj, key=lambda x: json.dumps(x))

    return obj

As a side point, if you find yourself with classes in your objects that you need to sort, you can jsonpickle.dumps() them, then json.loads() them, then deep_sort() them. If it matters, then you can always json.dumps() and jsonpickle.loads() to get back to where you started, except sorted (well, only sorted in Python 3.6+). For cases of a stable hash, that wouldn't be necessary though.

Solution 4:

Very similar to @acushner's solution, but class-based:

from collections import OrderedDict


classSortedDict(OrderedDict):

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

        for key, value insorted(kwargs.items()):
            ifisinstance(value, dict):
                self[key] = SortedDict(**value)
            else:
                self[key] = value

Usage:

sorted_dict = SortedDict(**unsorted_dict)

Solution 5:

A combination of @pelson's answer and @cjbarth's answer, with key and reverse parameters:

defdeep_sorted(obj, *, key=None, reverse=False):
    ifisinstance(obj, dict):
        return {k: deep_sorted(v, key=key, reverse=reverse) for k, v insorted(obj.items(), key=key, reverse=reverse)}
    ifisinstance(obj, list):
        return [deep_sorted(v, key=key, reverse=reverse) for i, v insorted(enumerate(obj), key=key, reverse=reverse)]
    return obj