came across a description of their
(that is bimap without a 't') .
It seems to be a bi-directional mapping.
In a Python dict, keys map to values. In a bimap, values would also map
to keys. It seems they put keys/values on an equal footing by renaming
them as left and right members, and having methods that work on either
the right to left or the left to right mapping.
I had just re-visited a program of mine that dealt with what I would
consider large sets of values. I was mapping test names to test
coverage where their were tens of trhousands of test names, each of
~100 characters long and for each file, I had many thousands of code
coverage points, which themselves were strings of ~150 characters each.
I new I had to work with a dict mapping test_names to sets of covered
points for each test and do a lot of set arithmatic to rank the tests
in order of contribution to the overall coverage figure, so I decided
to use indices; replacing files by negative numbers and coverage points
by positive numbers. My program works, and is very fast but I note that
I create both a testname2index mapping dict and the inverse
index2testname mapping, (and coverpoint2index and index2coverpoint
mapping dicts).
What I had been constructing, unawares, was a bimap by using two dicts.
I then spent time googling for Python bimaps to no avail, (although I
think there are haskel and Java implementations out there - and Google
'helps' by sugesting you meant bitmap with a 't').
So my questions are:
- Is their a Python bimap implementation out there?
- Would anyone want one? (I already code around its
absense). - What would its methods be?
Methods
On my third question, I guess you could have all the normal methods of
a dict but preceeded by either
left_ or right_
with calling of a method without those prefixes raising an exception,
as it seems important to not favour one mapping direction over another.
This would give:
DICT BIMOD
(LEFT) BIMOD (RIGHT)
clear
left_clear right_clear
copy
left_copy right_copy
fromkeys
left_fromkeys right_fromkeys
get
left_get
right_get
has_key
left_has_key right_has_key
items
left_items right_items
iteritems left_iteritems
right_iteritems
iterkeys
left_iterkeys right_iterkeys
itervalues
left_itervalues right_itervalues
keys
left_keys right_keys
pop
left_pop
right_pop
popitem
left_popitem right_popitem
setdefault
left_setdefault right_setdefault
update
left_update right_update
values
left_values right_values
The above couldn't be extended for indexing however, unless you did
something like:
and bimod_instance..right[rightindex]
but then wouldn't it be better to use the dotted form for all the
methods and have:
bimod_instance.left.haskey # (with a dot after left), ...
I note that their are redundancies above, for example, left_clear ==
right_clear ...
Strewth, I've only scratched the surface :-)
- Paddy.
Search for bijection/surjection/injection instead of "bimap" and you might do better.
ReplyDeleteI've got a dirt-simple Bijection dict subclass at http://www.aminus.net/geniusql/browser/trunk/geniusql/objects.py#L32 -- it only adds a "key_for(value)" method.
You can simplify the methods by adding an intermediate object, like this:
ReplyDeletedict.left.keys() == dict.right.values()
Of course, this only works for dicts where both keys and values are hashable.
Hi Fumanchu, thanks for the terms. A quick wikipedia search and I now know that the three terms relate to a mapping between a functions argument and its result:
ReplyDeleteIn an injection, each input maps to one output, however the output set maybe larger than the set of inputs.
In a surjection, each output maps to one input, however the input set may be larger than the set of outputs.
In a bijection, each input maps to exactly one output.
I can see why they called the datatype a bimap now.
-
Hi Growl, I was slowly getting to that myself with what I said in the third-from-last paragraph, below the table.
-
My search for a Python bimap/bijection map got me a Xah Lee rant, but searching for "bidirectional map" was more interesting, just not in Python.
- Paddy.
After reading your post I decided that might be a fun day project. I'm sure someone else has done this, but I thought I would share my Class with you.
ReplyDeletehttp://trydyingtolive.dynalias.com/code/bidict.txt
@tryDyingToLive,
ReplyDeleteI took a look at your code - Thanks for taking the time and effort to produce it.
I took a look at the example at the head of the file and spotted a problem: a bimap maps members of a left set to a right set, and vice-versa, but an item on the left can appear as an item on the right in the general case.
In my uses so far, I don't think this is the case, but you might conceivably want to do:
BiDict({1:'a',2:'b','c':'c',3:3})
- Paddy.
You can actually do that. Its one of the level's of strictness.
ReplyDeleteb=BiDict({1:'a',2:'b','c':'c',3:3},'bi-dict')
The code is set to the strictest as default. Probably because it was late when I finished.
Have you considered any unabashedly relational solutions?
ReplyDeleteWell, I tend to not grab for a relational DB quickly. How would one help?
ReplyDeleteSo if you delete a key, then does the value go as well ?
ReplyDeleteFor a bimap, it would make sense as by definition, only left/right pairs should exist.
ReplyDeleteMaybe the code for a bimap should stress deletion of left/right pairs.
- Paddy.
This comment has been removed by a blog administrator.
ReplyDeleteThis comment has been removed by a blog administrator.
ReplyDelete