Description
I had to create a dictionary structure where one value can be referenced by several keys.
For example the keys a
, b
, c
reference the value 1 and d
, e
reference the value 2. If two groups of keys intersect then I want to merge them, for example the group a
, b
and b
, c
should result to a
, b
, c
.
I also need an efficient solution:
- linear time for creation (init) - \$O(n)\$.
- constant time for access (update and get) - \$O(1)\$
- no need for inserting and delete since I have the final list of keys at the init
I'm come from Java world and I'm not totally confortable with the Python philosophy so I think some review could be useful.
Main code
from collections.abc import Mapping
from typing import Iterator, Set, FrozenSet, AbstractSet, ValuesView, Tuple
class MultiKeysDict(Mapping):
"""
Dictionary to manage multiple key to one value.
The keys groupes should be set at the initialization and can't change later.
If two keys groupes share a key so they will reference the same value.
"""
class Value:
"""
Store the value data
"""
def __init__(self, default_value):
self.data = default_value
def __init__(self, grp_keys: Set[FrozenSet], default_value = None):
"""
Create a dictionary based keys groups.
Every group will share the same value. Intersected group will share the same value.
:param grp_keys: The groups of keys.
:param default_value: The default value.
"""
self._storage = dict()
self._values = set()
# Build all keys
reverse_dict = dict() # For groupe merging
for keys in grp_keys:
refs = set()
for key in keys:
if key in self._storage:
refs.add(self._storage[key])
# New group of keys
if not refs:
new_value = MultiKeysDict.Value(default_value)
self._storage.update(dict.fromkeys(keys, new_value))
reverse_dict[new_value] = set(keys)
self._values.add(new_value)
# Extend an existing group of keys
elif len(refs) == 1:
old_value = refs.pop()
self._storage.update(dict.fromkeys(keys, old_value))
reverse_dict[old_value].update(keys)
# Merge several group of keys (troubles start here)
else:
old_value = refs.pop()
keys_to_merge = [key for ref in refs for key in reverse_dict[ref]]
self._storage.update(dict.fromkeys(keys_to_merge, old_value))
reverse_dict[old_value].update(keys_to_merge)
# Remove merged references
for ref in refs:
del reverse_dict[ref]
self._values.discard(ref)
def __getitem__(self, k):
return self._storage[k].data
def __setitem__(self, key, value):
self._storage[key].data = value
def __len__(self) -> int:
return len(self._values)
def __iter__(self) -> Iterator:
return (value.data for value in self._values)
def keys(self) -> AbstractSet:
return self._storage.keys()
def values(self) -> ValuesView:
return [value.data for value in self._values] # Should be ValuesView type?
def items(self) -> AbstractSet[Tuple]:
return {(key, self.__getitem__(key)) for key in self.keys()}
Some tests
import unittest
from tools.multikey_dict import MultiKeysDict
class TestMultiKeyDict(unittest.TestCase):
def test_basic_init(self):
# Expected: [a, b] [c, d] [e, f, g]
d = MultiKeysDict({
frozenset({'a', 'b'}),
frozenset({'c', 'd'}),
frozenset({'e', 'f', 'g'})
})
d['a'] = 42
d['c'] = 'lolilol'
d['f'] = [1, 2, 3]
# [a, b]
self.assertEqual(d['a'], d['b'])
self.assertEqual(d['b'], 42)
# [c, d]
self.assertEqual(d['c'], d['d'])
self.assertEqual(d['d'], 'lolilol')
# [e, f, g]
self.assertIs(d['e'], d['f'])
self.assertIs(d['e'], d['g'])
self.assertEqual(d['f'], [1, 2, 3])
def test_intersection_init(self):
# Expected: [a, b, c] [d, e]
d = MultiKeysDict({
frozenset({'a', 'b'}),
frozenset({'b', 'c'}),
frozenset({'d', 'e'})
})
d['a'] = 1
d['d'] = 2
# [a, b, c]
self.assertEqual(d['b'], 1)
self.assertEqual(d['c'], 1)
self.assertIs(d['a'], d['c'])
# [d, e]
self.assertIs(d['d'], d['e'])
def test_merge_init(self):
# Expected: [a, b, c, d] [e, f]
d = MultiKeysDict({
frozenset({'a', 'b'}),
frozenset({'c', 'd'}),
frozenset({'b', 'c'}),
frozenset({'e', 'f'})
})
d['a'] = 1
# [a, b, c, d]
self.assertEqual(d['a'], 1)
self.assertEqual(d['b'], 1)
self.assertEqual(d['c'], 1)
self.assertEqual(d['d'], 1)
The code seems to work as expected but I'm not sure about my implementation, especially the values()
and items()
part.
__init__
and it looks like it runs in \$O(n^2)\$ time. This is asrefs
worst case can begrp_keys
, meaning that you have both an outer and inner loop looping overgrp_keys
. \$\endgroup\$