Hash map with multiple keys per value ?

[Chris Stiles]

Hi --

I'm working on something that includes the concept of multiple aliases for a
particular object, where a lookup for any of the aliases has to return all the
others. The hack way of doing this was to have a dictionary where each
entry consisted of a list of all the aliases - with multiple references to the
same list from the various dictionary entries corresponding to each alias.

Is there an easier and cleaner way of doing this ? Is there example code
floating around that I might have a look at ?

 

[snoe]

Are you looking for this type of thing?

class Test:
value = 900

t = Test()
d['1'] = t
d['2'] = t
d['3'] = t

d['3'].value = 800
d['1'].value

 

[Robert Kern]

Hi --

I'm working on something that includes the concept of multiple aliases for a
particular object, where a lookup for any of the aliases has to return all the
others. The hack way of doing this was to have a dictionary where each
entry consisted of a list of all the aliases - with multiple references to the
same list from the various dictionary entries corresponding to each alias.

Is there an easier and cleaner way of doing this ? Is there example code
floating around that I might have a look at ?

It's what everybody else does. You may want to use sets instead of
lists, but otherwise I think your approach is pretty standard.

--
Robert Kern
(e-mail address removed)

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

 

[Chris Stiles]

Are you looking for this type of thing?

class Test:
value = 900

No, what I'm trying to do is this, assume two sets of aliases:

a, b, c, d and e

x, y and z

a returns b c d and e, b returns a c d and e, x returns y and z, y returns x
and z etc.

Where any of the sets of aliases can grow or shrink at any time.

 

[Alex Martelli]

No, what I'm trying to do is this, assume two sets of aliases:

a, b, c, d and e

x, y and z

a returns b c d and e, b returns a c d and e, x returns y and z, y returns x
and z etc.

Where any of the sets of aliases can grow or shrink at any time.

So, it seems a reasonable underlying representation would be a mapping
from item to set of items. Keeping N different sets for a set of N
aliases would appear a bit wasteful of memory (it's hard to say without
knowing usecases and performance desiderata...), so you might have all
aliases map to the same set of aliases and dynamically construct the
required result by subtracting the lookup key itself.

Another design issue is, however, how do you identify, when adding an
alias, what it's an alias of -- from previous posts I'll assume that all
aliases are 'names' for some (hopefully hashable) object, so we'll also
need a mapping from said object back to its set of aliases. Or, would
alias insertion just be of the form "x aliases to y" rather than "x
names object XXX"?

Also not clarified in terms of specs: when an alias is inserted, do you
need to check if it was already an alias for something else (in another
set) and [a] raise an exception or silently remove it from the
previous set? That applies to the "x names object XXX" style but not
necessarily to the "x aliases y" style, unless in the latter case you
want to say "...replacing any previous aliases of x" to change rather
than merge alias-sets. But it would then seem simpler to simply have a
separate removal function "x doesn't alias to anything any longer", to
be optionally called before the insertion method.

So, I think there are enough questions open about the specs to warrant
more exploration. Under some given set of interpretations for the above
open questions, you might have, e.g. (untested code, and no special
attention paid to performance):

class Aliases(object):
def __init__(self):
self.d = {}
def lookup(self, x):
if x in self.d:
return self.d[x]-set([x])
else:
return set()
def alias(self, x, y):
dx = self.d.get(x,set([x]))
dy = self.d.get(y,set([y]))
self.d[x]=self.d[y]=dx+dy
def unalias(self, x):
if x in self.d:
self.d[x].remove(x)
if not self.d[x]: del self.d[x]

Perhaps by working on this concrete example (which likely has bugs,
being untested, and even more likely misinterpret some specs, since I'm
having to guess at quite a few details) you can nail down the exact kind
of API syntax and semantics that you require...? Once the specs are
entirely clear, we might (if needed) worry about efficiency, but that
seems somewhat premature at this stage...


Alex

 

[Bengt Richter]

Hi --

I'm working on something that includes the concept of multiple aliases for a
particular object, where a lookup for any of the aliases has to return all the
others. The hack way of doing this was to have a dictionary where each
entry consisted of a list of all the aliases - with multiple references to the
same list from the various dictionary entries corresponding to each alias.

What about the "particular object" in this? If all the aliases refer to the
"particular object", what does "return all the others" mean? All _what_ "others"?
All refer to the same "particular object". Or do you want the names? If so,
What about the "particular object"? Or do you want a dict back that has all the
other alias names as keys all referring to the "particular object"? E.g.,
... def __getitem__(self, key):
... keyval = dict.__getitem__(self, key)
... return Aliad((k,v) for k,v in self.items() if k!=key and v is keyval)
...

>>> po = 'particular object'
>>> ad = Aliad(x=po, y=po, z=po)
>>> ad {'y': 'particular object', 'x': 'particular object', 'z': 'particular object'}
>>> ad['x'] {'y': 'particular object', 'z': 'particular object'}
>>> ad['y'] {'x': 'particular object', 'z': 'particular object'}
>>> ad['z'] {'y': 'particular object', 'x': 'particular object'}
>>>
>>> po2 = 'alpha'
>>> ad.update(a=po2, b=po2, c=po2, d=po2, e=po2)
>>> ad['x'] {'y': 'particular object', 'z': 'particular object'}
>>> ad['a'] {'c': 'alpha', 'b': 'alpha', 'e': 'alpha', 'd': 'alpha'}
>>> ad['b']

{'a': 'alpha', 'c': 'alpha', 'e': 'alpha', 'd': 'alpha'}

And since an Aliad instance is being returned,

>>> ad['a'] {'c': 'alpha', 'b': 'alpha', 'e': 'alpha', 'd': 'alpha'}
>>> ad['a']['e'] {'c': 'alpha', 'b': 'alpha', 'd': 'alpha'}
>>> ad['a']['e']['b'] {'c': 'alpha', 'd': 'alpha'}
>>> ad['a']['e']['b']['c'] {'d': 'alpha'}
>>> ad['a']['e']['b']['d']

{'c': 'alpha'}

Is there an easier and cleaner way of doing this ? Is there example code
floating around that I might have a look at ?

Please show _any_ example code that does (tested ;-) _exactly_ what you want.
Then we can try for an easier and cleaner way ;-)

Hope the above helps to clarify requirements one way or another ;-)

Regards,
Bengt Richter

 

[Chris Stiles]

Another design issue is, however, how do you identify, when adding an
alias, what it's an alias of -- from previous posts I'll assume that all
aliases are 'names' for some (hopefully hashable) object, so we'll also
need a mapping from said object back to its set of aliases. Or, would
alias insertion just be of the form "x aliases to y" rather than "x
names object XXX"?

In this case, strictly speaking there are no such thing as an 'object XXX',
all the aliases are names for the object, each as important as each other.
That's why I started off wondering whether there was such a thing as a
'multiple-keyed hash table' that would solve this more 'simply' - i.e I didn't
want to write code and then find I should have used "FooFoos multi-dimensional
Hash Matrix of which the hashtable is a degenerate case"

want to say "...replacing any previous aliases of x" to change rather
than merge alias-sets.

Yes, I think the class that does the mapping between aliases would merge alias
sets, if I need to replace aliases from outside I will remove them first.

class Aliases(object):

Okay, I hadn't thought of using sets - and they certainly make sense in this
context, in the absence of something more specialised this pretty much
satisfies my needs.

def alias(self, x, y):
dx = self.d.get(x,set([x]))
dy = self.d.get(y,set([y]))
self.d[x]=self.d[y]=dx+dy

^^^^^^^^^^^^^^^^^^^^^^^^^

Will that end up with two(many) references to the same set? [Though in any
case I would be iterating over all values in the set).

 

[Alex Martelli]

In this case, strictly speaking there are no such thing as an 'object XXX',
all the aliases are names for the object, each as important as each other.

Fine, but, quite apart from names, IS there a Python object with a given
identity, of which these aliases are names of? Or is that "object"
something which does NOT exist as a Python object (in which case maybe
calling it an "entity", or some other name that's not used for specific
purposes in Python, might be clearer!)...?

def alias(self, x, y):
dx = self.d.get(x,set([x]))
dy = self.d.get(y,set([y]))
self.d[x]=self.d[y]=dx+dy

^^^^^^^^^^^^^^^^^^^^^^^^^

Will that end up with two(many) references to the same set? [Though in any
case I would be iterating over all values in the set).

Yes, but it's buggy (doesn't modify the self.d[z] entries for all the
z's which aren't either x nor y but alias either of them).


Alex

 

[Tom Anderson]

Is there an easier and cleaner way of doing this ? Is there example
code floating around that I might have a look at ?

I'm not aware of a way which can honestly be called better.

However, i do feel your pain about representing the alias relationships
twice - it feels wrong. Therefore, i offer you an alternative
implementation - represent each set as a linked list, threaded through a
dict by making the value the dict holds under each key point to the next
key in the alias set. Confused? No? You will be ...

class Aliases(object):
def __init__(self, aliases=None):
self.nexts = {}
if (aliases != None):
for key, value in aliases:
self[key] = value
def __setitem__(self, key, value):
if ((value != None) and (value != key)):
self.nexts[key] = self.nexts[value]
self.nexts[value] = key
else:
self.nexts[key] = key
def __getitem__(self, key):
return list(follow(key, self.nexts))
def __delitem__(self, key):
cur = key
while (self.nexts[cur] != key):
cur = self.nexts[cur]
if (cur != key):
self.nexts[cur] = self.nexts[key]
del self.nexts[key]
def canonical(self, key):
canon = key
for cur in follow(key, self.nexts):
if (cur < canon):
canon = cur
return canon
def iscanonical(self, key):
for cur in follow(key, self.nexts):
if (cur < key):
False
return True
def iteraliases(self, key):
cur = self.nexts[key]
while (cur != key):
yield cur
cur = self.nexts[cur]
def __iter__(self):
return iter(self.nexts)
def itersets(self):
for key in self.nexts:
if (not isprimary(key, self.nexts)):
continue
yield [key] + self[key]
def __len__(self):
return len(self.nexts)
def __contains__(self, key):
return key in self.nexts
def __str__(self):
return "<Aliases " + str(list(self.itersets())) + ">"
def __repr__(self):
return "Aliases([" + ", ".join(str((key, self.canonical(key))) for key in sorted(self.nexts.keys())) + "])"

As i'm sure you'll agree, code that combines a complete absence of clarity
with abject lack of runtime efficiency. Oh, and i haven't tested it
properly.

tom

 

[Chris Stiles]

Fine, but, quite apart from names, IS there a Python object with a given
identity, of which these aliases are names of? Or is that "object"
something which does NOT exist as a Python object (in which case maybe
calling it an "entity", or some other name that's not used for specific
purposes in Python, might be clearer!)...?

Yes, definitely entities rather than objects.

 

[Bengt Richter]

Hi --

I'm working on something that includes the concept of multiple aliases for a
particular object, where a lookup for any of the aliases has to return all the
others. The hack way of doing this was to have a dictionary where each
entry consisted of a list of all the aliases - with multiple references to the
same list from the various dictionary entries corresponding to each alias.

Is there an easier and cleaner way of doing this ? Is there example code
floating around that I might have a look at ?

[OT about on-T missing post]
I see my post on google
http://groups.google.com/group/comp.lang.python/msg/7d6056940048f1b6
but I haven't seen it yet on my newsreader. Is it not showing for anyone
else either? I am wondering what's happening. Usually it's only a matter
of minutes, not a day and counting ;-/

Regards,
Bengt Richter