Find duplicates for mixed type values in dictionaries

Question

Following these two SO questions:

1. Find duplicates for mixed type values in dictionaries
2. Group similar dict entries as a tuple of keys

I came to the conclusion that the solution I proposed is mature enough to be reviewed here.

The idea is to find duplicates in a dictionary such as example below, but with extended support for mixed type content (seq/mapping/scalars):

d = collections.defaultdict(set)
[d[k].add(v) for k, v in s]

Here's my solution:

import copy
import collections

def faithfulrepr(ds):
    """Returns a plain-text representation of a mixed seq/mapping/scalar 
    type data structure.

    The datastructure is recursively ordered (ordereddict) then a 
    dataset representation is returned.

    Args:

        ds  Dataset (mixed seq/mapping/scalar data structure)

    Returns:

        Sorted plain-text representation of the input dataset.
    """
    ds = copy.deepcopy(ds)
    if isinstance(ds, collections.Mapping):
        res = collections.OrderedDict()
        for k, v in sorted(ds.items()):
            res[k] = faithfulrepr(v)
        return repr(res)
    if isinstance(ds, list):
        for i, v in enumerate(ds):
            ds[i] = faithfulrepr(v)
        return repr(ds)
    return repr(ds) 


def tupelize_dict(ds):
    """Group identical values of a dictionary under the same key. The keys
    become a tuple of all the duplicate keys.

    Args:

        ds: Input dictionary

    Example::

        ds = {23: 'foo',
              25: 'bar',
              28: 'foo',
              30: 'bar',
              33: 'foo'}

        >>>tupelize_dict(ds)
        {
            (23,28,33): 'foo',
            (25,30): 'bar'
        }
    """
    taxonomy = {}
    binder = collections.defaultdict(list)
    for key, value in ds.items():
        signature = faithfulrepr(value)
        taxonomy[signature] = value
        binder[signature].append(key)
    return {tuple(keys): taxonomy[s] for s, keys in binder.items()}

I am open for any better name for tupelize_dict :)

Answer 1

Your code reads well, and has good documentation. It is pretty pleasant to read.

You could just simplify a bit faithfulrepr by using generator expression and removing the need for the deepcopy:

def faithfulrepr(ds):
    if isinstance(ds, collections.Mapping):
        res = collections.OrderedDict(
            (k, faithfulrepr(v)) for k, v in sorted(ds.items())
        )
    elif isinstance(ds, list):
        res = [faithfulrepr(v) for v in ds]
    else:
        res = ds
    return repr(res)

However this method will fail when fed dictionaries that have variable types as their keys (like {1: 'one', 'two': 2}).

An other take on the problem would involve more computations but can compare elements with the equality operator (which seems to be what you are really interested on). It involves maintaining two lists, one for the list of keys and one for the values, and searching in the list of values if the current one already exist. This is done using index which, unfortunately, is \$O(n)\$ but compares using __eq__:

def tupelize_dict(ds):
    keys, values = [], []
    for key, value in ds.items():
        try:
            index = values.index(value)
        except ValueError:
            values.append(value)
            keys.append([key])
        else:
            keys[index].append(key)
    return dict(zip(map(tuple, keys), values))
    # or the more readable return {tuple(k): v for k, v in zip(keys, values)}