CODEWITHSUNDEEP
pythondictionarypython-2.7composite-key
inspectorG4dget
inspectorG4dget

Reputation: 114025

Composite keys in dictionaries

I am maintaining a dictionary that keeps track of the similarities between pairs of objects.
For example, this dictionary could look like this:

similarities = {
 p1: {p2: v12, p3:v13, p4:v14},
 p2: {p1: v21, p3:v23, p4:v24},
 p3: {p1: v31, p2:v32, p4:v34},
 p4: {p1: v41, p2:v42, p4:v43}
}

Note, that the similarity measurement is symmetric. Therefore, similarities[p1][p2] is the same as similarities[p2][p1] i.e. v12 == v21.

Sometimes, I'll need to eliminate p2 from similarities[p1]; and in doing so, I'll need to remove p1 and p2 from all the inner dictionaries in similarities as well.
This is tedious and inefficient.

So instead of maintaining a symmetric dictionary, is there a way to maintain a dictionary with a composite key so that I can lookup similarities[p1,p2]?

I can't really use a tuple since (p1, p2) != (p2, p1) and I can't know a priori how to order the tuple.

A frozenset is the only other container that I can think of, but that won't cut it since there may still be other keys in similarities that contain either p1 or p2 as a component. So what container could I use to solve this issue?

Technical info:

Thank you

Upvotes: 4

Views: 6236

Answers (3)

Blckknght
Blckknght

Reputation: 104762

I think using frozenset is the only logical solution. You can find keys that match just one of the values using a comprehension with a set intersection test:

def remove_ab(ab, similarities):
    return {k:v for k, v in similarities.items() if not ab & k}

similarities = {frozenset({1, 2}): "v12",
                frozenset({1, 3}): "v13",
                frozenset({2, 3}): "v23",
                frozenset({3, 4}): "v34"}

similarities = remove_ab(frozenset({1, 2}), similarities
print(similarities) # output is {frozenset({3, 4}): 'v34'}

Upvotes: 1

Danica
Danica

Reputation: 28846

I'd probably just use a frozenset, assuming the objects are hashable.

Alternatively, if they have any well-defined and consistent order on them, you could keep them in a tuple sorted by said order. You could write a little dict subclass to do that for you transparently if you wanted.

Or, you could do something like this:

class SymmetricDict(dict):
    def __getitem__(self, key):
        if key in self:
            return dict.__getitem__(self, key)
        a, b = key
        return dict.__getitem__(self, (b, a))

and similarly for __setitem__.

Upvotes: 2

Chris Johnson
Chris Johnson

Reputation: 21996

If the p_ objects are of a type that supports sorting, could you use a tuple with the two elements always in lo --> hi order?

Upvotes: 0

Related Questions