How to turn a list of dicts into deterministic order?

Question

I have an arbitrary (JSON-serializeable) structure which contains lists of dicts which I don't know anything about in advance (e.g.size or keys).

Is there a way to bring this list of dicts into a deterministic order (in order to compare them)?

I could think of turning a list of dicts into a list of 2-tuples which I can compare but I'm looking for a 'pythonic' solution..

Please note: I don't want to sort a list of dicts by any key I have to know in advance but I want to sort generic (JSON-serializeable) lists of dicts.

Another note: I don't just want to compare the dicts but I want to be able to serialize them. So I'm looking for a function reorder which makes sure

json.dumps(reorder([{'a': 1}, {'b': 2}])) == json.dumps(reorder([{'b': 2}, {'a': 1}]))

What's unpythonic about converting a dict to a list of 2-tuples? Sounds like a good approach to me. Depending on your anticipated data you might want to do it recursively. — mkrieger1, Feb 19 '20 at 16:29
Does this answer your question? [Comparing Python dictionaries and nested dictionaries](https://stackoverflow.com/questions/27265939/comparing-python-dictionaries-and-nested-dictionaries) — mkrieger1, Feb 19 '20 at 16:30
what about [`OrderedDict`](https://docs.python.org/3/library/collections.html#ordereddict-objects) (instead of 2-tuples)? — hiro protagonist, Feb 19 '20 at 16:34
@hiroprotagonist: In 3.6+, the `dict` will already be insertion-ordered, you only need `OrderedDict` if you *want* order-sensitive comparisons and/or the ability to rearrange the order. That said, they seem to want the `list` in a deterministic order, not the `dict`s, so it's all kind of irrelevant; making the `dict` comparisons order-sensitive wouldn't help. — ShadowRanger, Feb 19 '20 at 16:45
@ShadowRanger thanks, i am aware of the `dict` features (in the different versions) of python. just thought that may be sth to look into. but now re-reading the requirement you are right... — hiro protagonist, Feb 19 '20 at 16:47
Problem is that `OrderedDict` is indeed ordered but not sorted. So if you can't make sure the dicts are being composed in exactly the same way they still might be ordered differently despite they have the same content. E.g. `[{'a': 1}, {'b': 2}]` should be serialized the same way as `[{'b': 2}, {'a': 1}]`. — frans, Feb 19 '20 at 20:49

score 0 · Answer 1 · answered Feb 20 '20 at 07:39

A reorder() function as mentioned in the question could be implemented like this:

def reorder(data):
    def comparable(uncomparable):
        if isinstance(uncomparable, dict):
            return tuple((k, comparable(v)) for k, v in uncomparable.items())
        if isinstance(uncomparable, (list, tuple)):
            return tuple(comparable(d) for d in uncomparable)
        return data
    if isinstance(data, (list, tuple)):
        return sorted([reorder(d) for d in data], key=lambda e: comparable(e))
    if isinstance(data, dict):
        return {k: reorder(v) for k, v in data.items()}
    return data

Note that this function implicitly converts tuple to list which results in the same outcome when serialized to JSON.

How to turn a list of dicts into deterministic order?

1 Answers1