[New-bugs-announce] [issue47157] bijective invertible map

[Jonathan Balloch]

New submission from Jonathan Balloch <jon.balloch at gmail.com>:

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 <report at bugs.python.org>
<https://bugs.python.org/issue47157>
_______________________________________