[Python-Dev] Another case for frozendict

[bjourne]

https://mail.python.org/pipermail/python-dev/2014-July/135469.html

[dalke]

I don't understand how that use case leads to a need for a frozendict.

The use case is to get the unique dictionaries from a list of dictiories

    >>> res = [db.cases.remove({'_id': doc['_id']}) for doc in fives]
    >>> res[0]
    {'n': 1, 'err': None, 'ok': 1.0}
    >>> res[1]
    {'n': 1, 'err': None, 'ok': 1.0}
    >>> set(map(frozendict, res))

Won't that fail if the res[] elements themselves happen to contain dictionaries, as in:

    {'n': 1, 'err': None, 'ok': 1.0, 'extra': {'a': 1, 'b': 2}}

That is, hash of the 'extra' value will fail, because dictionaries are unhashable, therefore a frozendict of the above can't have a good hash.

I say "good hash" because it's possible to define a dictionary hash based only on the keys, but in this use case all of the entries have the same keys, so are in the same position in the hash table, causing frozendict operations to switch from amortized O(1) to O(n) operations.

[bjourne → dalke]

Correct. But the idea is probably that the dicts in the frozendicts themselves should be frozendicts.

[dalke → bjourne]

Certainly. The question is really who is in charge of carrying out the "should". Currently it's the programmer, who needs to write an adapater. That adapter needs to know to convert any mutable values (dict, list, set, etc) to immutable form (frozendict, tuple, frozenset, etc.)

I personally think the use case is better handled with the unique_everseen in https://docs.python.org/2/library/itertools.html :

    uniq_res = unique_everseen(res, lambda d: sorted(d.items()))