New submission from Jonathan Balloch :
It would be powerful to have a native implementation of a bijective map (e.g. a
dictionary that hashed only one-to-one, but as a result either the "key" or the
"value" could do lookup in O(1) time with the only overhead being the
additional memory overhead of O(2N) as many references.
Calling the object type "bimap", this could be easily implemented by simply
having a call to bimap.inverse[value]=key, where the 'inverse' keyword is a
reference table to the value-->key references.
This is an important enhancement because currently the most efficient way to
implement this is python is to, either: (1) make a custom object type that
keeps two dictionaries, one that maps v->k and one that maps k->v, which takes
twice as much memory, or (2) an object that has a custom "inverse" lookup call,
which will be slower than O(1). In both cases there is no implicit enforcement
of values being unique (necessary for a bijection).
This should be added to the `collections` library as it will fit well along
side other unique hashed collections such as "OrderedDict"
This will be beneficial to the community because transformations between
semantic spaces (e.g. things that cannot be done in NumPy or similar) could be
much more efficient and have cleaner, easier to read code if bijection maps
were native and used one structure instead of two dictionaries.
--
components: Interpreter Core
messages: 416304
nosy: jon.balloch
priority: normal
severity: normal
status: open
title: bijective invertible map
type: enhancement
versions: Python 3.11
___
Python tracker
<https://bugs.python.org/issue47157>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
