Data-structure for multiway associativity in Python
Steven D'Aprano
steve+comp.lang.python at pearwood.info
Sun Jan 28 19:22:14 EST 2018
On Sun, 28 Jan 2018 14:48:02 -0800, qrious wrote:
> First list = { 1, 2, 3}
> Second list = { 4, 5, 6}
> Third list = { 7, 8, 9}
>
> If I pass 9 as the argument, the return value of the function would be
> {7, 8}.
subsets = [{1, 2, 3}, {4, 5, 6}, {7, 8, 9}]
data = {}
for subset in subsets:
for key in subset:
data[key] = subset
# At this point, your master data looks like this:
#
# {1: {1, 2, 3}, 2: {1, 2, 3}, 3: {1, 2, 3},
# 4: {4, 5, 6}, 5: {4, 5, 6}, 6: {4, 5, 6},
# 7: {7, 8, 9}, 8: {7, 8, 9}, 9: {7, 8, 9}}
#
# but don't worry, that's not three COPIES of each set, just three
# references to the same one: each reference costs only a single
# pointer.
# Find a set associated with a key
subset = data[9] # this is a lightning-fast lookup
# Get the items in the set, excluding the key itself
result = subset - {9}
assert result == {7, 8}
# Add a new data point to that set:
subset.add(10)
data[10] = subset
# Delete a data point:
del subset[9]
del data[9]
If you had started with a concrete example from the start, this would not
have seemed like such a mysterious and difficult problem. Describing it
as "multiway associativity" doesn't really help: as far as I can see,
it's not multiway at all, it is just a straightforward case of one way
associativity between each key and a set of values that contains that key.
Concrete examples are *really* useful for clarifying the requirements.
--
Steve
More information about the Python-list
mailing list