0

I have come to a need to represent a one to one relationship in python.

The easiest thing to do is have a list of tuples. [(thing_one, thing_two]. But this would get you O(N) translation/deletion/insertion time. Not ideal.

Next you could use two dictionaries one_to_two, two_to_one. This would get you O(1) translation/insertion/deletion. But its easy to forget to update one without the other and you are doubling the amount of memory you now need to represent this relationship. You could wrap this in a class to enforce the bijection, but you still don't solve the information duplication.

Is there a good way to represent a relationship like this? Preferably with O(1) ops and no data duplication? Maybe a python module that handles this for you?

Mitch
  • 3,342
  • 2
  • 21
  • 31
  • I'm pretty sure your two requirements are incompatible. If you want O(1) lookups in two directions, you need two lookup tables. Which requirement is more important? – Samwise Jun 02 '20 at 15:59
  • If there isnt a nice python package/clever representation the O(1) two dict approach is what I would go with. – Mitch Jun 02 '20 at 16:00
  • `pip install bidict` seems to be exactly what I am looking for @Samwise, thanks – Mitch Jun 02 '20 at 16:03
  • Be aware that bidict will require duplication (which you'll need anyway), as it's implemented with two dicts in the background. But I strongly recommend going with it anyway - the duplication cost is negligible. – MatsLindh Jun 02 '20 at 16:06

0 Answers0