reverse dict lookup & Relation class

[Aaron Brady]

Hi, this is a continuation of something that comes up now and again
about reverse lookups on dictionaries, as well as a follow-up to my
pursuit of a Relation class from earlier.

For a reverse lookup, you just need two lookups.
name= {}
phone= {}
name[ '555-963' ]= 'Joan'
phone[ 'Joan' ]= '555-963'

Though maybe the keys in 'name' should be names, instead of the values
in it. The variable name doesn't clarify that. (What is more natural
to you in reading code? Is one obviously wrong?)

phone[ '555-963' ]= 'Joan'
name[ 'Joan' ]= '555-963'

To provide for non-unique fields, the structure becomes kind of
complicated.

phone[ '555-963' ]= 'Joan'
phone[ '555-964' ]= 'Joan'
name[ 'Joan' ]= [ '555-963', '555-964' ]

For uniform access, 'phone' can be a dict of strings to lists too.

phone[ '555-963' ]= [ 'Joan' ]
phone[ '555-964' ]= [ 'Joan' ]

To add a third field, the structure becomes again more complicated.
Either define a unique key:

phone[ '555-963' ]= [ object1 ]
phone[ '555-964' ]= [ object2 ]
name[ 'Joan' ]= [ object1, object2 ]
hourstocall= {}
hourstocall[ '9a-5p' ]= [ object1 ]
hourstocall[ '5p-11p' ]= [ object2 ]
records= {}
records[ object1 ]= ( 'Joan', '555-963', '9a-5p' )
records[ object2 ]= ( 'Joan', '555-964', '5p-11p' )

Or, and this is the interesting part, use the ('identificationally')
same tuples in both mappings, since the object is only mentioned, not
used.

phone[ '555-963' ]= [ ( 'Joan', '555-963', '9a-5p' ) ]
phone[ '555-964' ]= [ ( 'Joan', '555-964', '5p-11p' ) ]
name[ 'Joan' ]= [ ( 'Joan', '555-963', '9a-5p' ), ( 'Joan', '555-964',
'5p-11p' ) ]
hourstocall[ '9a-5p' ]= [ ( 'Joan', '555-963', '9a-5p' ) ]
hourstocall[ '5p-11p' ]= [ ( 'Joan', '555-964', '5p-11p' ) ]

What's the best way to construct this class? Or, do you have an
argument that it could not be simpler than using a relational db?
Brainstorming, not flamestorming.

 

[Chris Rebert]

Hi, this is a continuation of something that comes up now and again
about reverse lookups on dictionaries, as well as a follow-up to my
pursuit of a Relation class from earlier.

For a reverse lookup, you just need two lookups.
name= {}
phone= {}
name[ '555-963' ]= 'Joan'
phone[ 'Joan' ]= '555-963'

Though maybe the keys in 'name' should be names, instead of the values
in it. The variable name doesn't clarify that. (What is more natural
to you in reading code? Is one obviously wrong?)

phone[ '555-963' ]= 'Joan'
name[ 'Joan' ]= '555-963'

To provide for non-unique fields, the structure becomes kind of
complicated.

phone[ '555-963' ]= 'Joan'
phone[ '555-964' ]= 'Joan'
name[ 'Joan' ]= [ '555-963', '555-964' ]

For uniform access, 'phone' can be a dict of strings to lists too.

phone[ '555-963' ]= [ 'Joan' ]
phone[ '555-964' ]= [ 'Joan' ]

To add a third field, the structure becomes again more complicated.
Either define a unique key:

phone[ '555-963' ]= [ object1 ]
phone[ '555-964' ]= [ object2 ]
name[ 'Joan' ]= [ object1, object2 ]
hourstocall= {}
hourstocall[ '9a-5p' ]= [ object1 ]
hourstocall[ '5p-11p' ]= [ object2 ]
records= {}
records[ object1 ]= ( 'Joan', '555-963', '9a-5p' )
records[ object2 ]= ( 'Joan', '555-964', '5p-11p' )

Or, and this is the interesting part, use the ('identificationally')
same tuples in both mappings, since the object is only mentioned, not
used.

phone[ '555-963' ]= [ ( 'Joan', '555-963', '9a-5p' ) ]
phone[ '555-964' ]= [ ( 'Joan', '555-964', '5p-11p' ) ]
name[ 'Joan' ]= [ ( 'Joan', '555-963', '9a-5p' ), ( 'Joan', '555-964',
'5p-11p' ) ]
hourstocall[ '9a-5p' ]= [ ( 'Joan', '555-963', '9a-5p' ) ]
hourstocall[ '5p-11p' ]= [ ( 'Joan', '555-964', '5p-11p' ) ]

What's the best way to construct this class? Or, do you have an
argument that it could not be simpler than using a relational db?
Brainstorming, not flamestorming.

Once you get beyond a main dict (e.g. name2phone) and one that's its
inverse (e.g. phone2name), yeah, I'd probably say you should be using
a relational DB for this. You could also use objects, but it sounds
like you really want to use SQL-like querying, which isn't well-suited
to plain objects (though it'd be fine with an ORM).

Cheers,
Chris

 

[MRAB]

Hi, this is a continuation of something that comes up now and again
about reverse lookups on dictionaries, as well as a follow-up to my
pursuit of a Relation class from earlier.

For a reverse lookup, you just need two lookups.
name= {}
phone= {}
name[ '555-963' ]= 'Joan'
phone[ 'Joan' ]= '555-963'

Though maybe the keys in 'name' should be names, instead of the
values in it. The variable name doesn't clarify that. (What is more
natural to you in reading code? Is one obviously wrong?)

phone[ '555-963' ]= 'Joan'
name[ 'Joan' ]= '555-963'

Consider "str(x)". It isn't saying "x is a string", it's saying "x as a
string". Similarly, "ord(x)" says "the ordinal value of x". So,
"phone[x]" means "the phone number of x".

[snip]

What's the best way to construct this class? Or, do you have an
argument that it could not be simpler than using a relational db?
Brainstorming, not flamestorming.

You could imagine an object where you provide a field name and a value
and it returns all those entries where that field contains that value.
That, basically, is a database.

 

[Aaron Brady]

Hi, this is a continuation of something that comes up now and again
about reverse lookups on dictionaries, as well as a follow-up to my
pursuit of a Relation class from earlier. snip
Or, and this is the interesting part, use the ('identificationally')
same tuples in both mappings, since the object is only mentioned, not
used.

phone[ '555-963' ]= [ ( 'Joan', '555-963', '9a-5p' ) ]
phone[ '555-964' ]= [ ( 'Joan', '555-964', '5p-11p' ) ]
name[ 'Joan' ]= [ ( 'Joan', '555-963', '9a-5p' ), ( 'Joan', '555-964',
'5p-11p' ) ]
hourstocall[ '9a-5p' ]= [ ( 'Joan', '555-963', '9a-5p' ) ]
hourstocall[ '5p-11p' ]= [ ( 'Joan', '555-964', '5p-11p' ) ]

What's the best way to construct this class?  Or, do you have an
argument that it could not be simpler than using a relational db?
Brainstorming, not flamestorming.

Once you get beyond a main dict (e.g. name2phone) and one that's its
inverse (e.g. phone2name), yeah, I'd probably say you should be using
a relational DB for this. You could also use objects, but it sounds
like you really want to use SQL-like querying, which isn't well-suited
to plain objects (though it'd be fine with an ORM).

I want the simplest data structure that can hold a relation. In this
case, I would declare a new record as:

PhoneInfo( 'Joan', '555-963', '9a-5p' )
PhoneInfo( 'Joan', '555-964', '5p-11p' )

However the syntax is flexible, such as in 'PhoneInfo.add' etc.

I can query the structure myself if I can access it as an iterable of
tuples. I think I want to use named tuples.

for rec in PhoneInfo.records:
if rec.name== 'Joan':
something

Or I can just use itertools.ifilter.

recset= ifilter( lambda rec: rec.name== 'Joan', PhoneInfo.records )
for rec in recset:
something

Using objects is one advantage, since they are "live" (unserialized)
and native, such as a relation of socket connections. (SQL would
require an additional mapping object and a key to accomplish it.)

 

[Aaron Brady]

Hi, this is a continuation of something that comes up now and again
about reverse lookups on dictionaries, as well as a follow-up to my
pursuit of a Relation class from earlier.

For a reverse lookup, you just need two lookups.
name= {}
phone= {}
name[ '555-963' ]= 'Joan'
phone[ 'Joan' ]= '555-963'

Though maybe the keys in 'name' should be names, instead of the
values in it.  The variable name doesn't clarify that.  (What is more
natural to you in reading code?  Is one obviously wrong?)

phone[ '555-963' ]= 'Joan'
name[ 'Joan' ]= '555-963'

Consider "str(x)". It isn't saying "x is a string", it's saying "x as a
string". Similarly, "ord(x)" says "the ordinal value of x". So,
"phone[x]" means "the phone number of x".

That's true. However, I want to map individual fields of records to
the tuples (named tuples) containing the records themselves (unless I
just need a set of tuples).

I think what you are talking about is accessing the 'phone' field,
which was not what I was thinking. (You see that in algorithm
pseudocode a bit.) For that, you could use 'name[ tuple1 ]' to obtain
the name. However, in relational data, there is no single key, of
which the rest of the fields are just accessories. (Does that make
sense?) I think I want to use the multiple mappings for different
ways to have access to the data.

[snip]> What's the best way to construct this class?  Or, do you have an

argument that it could not be simpler than using a relational db?
Brainstorming, not flamestorming.

You could imagine an object where you provide a field name and a value
and it returns all those entries where that field contains that value.
That, basically, is a database.

That's true. The mapping objects wouldn't be particularly helpful if
I had patterns to match instead of exact values... as now I'm thinking
you usually would. In other words, providing the mapping objects,
even grouped together in a provider object, would only handle a small
subset of possible queries, specifically exact equality. For example,
the 'hourstocall' object is basically useless as specified. Even
separating the fields wouldn't help in a hash. The separate fields
would need to be stored in sorted lists, using 'bisect' to test
inequality. (How does an SQL service implement inequality checks
anyway?)

However, it's interesting that my first thought was to start out with
a mapping object, instead of just a set of 'namedtuple's.

 

[Steven D'Aprano]

Hi, this is a continuation of something that comes up now and again
about reverse lookups on dictionaries, as well as a follow-up to my
pursuit of a Relation class from earlier.
[...]

What's the best way to construct this class? Or, do you have an
argument that it could not be simpler than using a relational db?
Brainstorming, not flamestorming.

Here's a lightweight solution that uses lazy calculation of the reverse
dict. It makes a number of assumptions:

- both keys and values will be hashable and unique;
- the dict won't be so large that calculating the reverse dictionary will
be time consuming;
- modifications to instance.reverse are undefined.


Usage:

d = ReverseDict(x=2, y=3, z=4)
d['x'] 2
d.reverse[2] 'x'
d['a'] = 0
d.reverse[0]

'a'





def make_dirty(func):
from functools import wraps
@wraps(func)
def f(self, *args, **kwargs):
self._dirty = True
return func(self, *args, **kwargs)
return f


# only tested a little bit
class ReverseDict(dict):
def __init__(self, *args, **kwargs):
super(ReverseDict, self).__init__(*args, **kwargs)
self._dirty = True
@make_dirty
def clear():
super(ReverseDict, self).clear()
@make_dirty
def __setitem__(self, key, value):
super(ReverseDict, self).__setitem__(key, value)
@make_dirty
def __delitem__(self, key):
super(ReverseDict, self).__delitem__()
@make_dirty
def pop(self, key, *arg):
return super(ReverseDict, self).pop(key, *arg)
@make_dirty
def popitem(self):
return super(ReverseDict, self).popitem()
@make_dirty
def setdefault(self, key, value=None):
return super(ReverseDict, self).setdefault(key, value)
@make_dirty
def update(self, other):
return super(ReverseDict, self).update(other)
@property
def reverse(self):
if self._dirty:
# Modify this to support repeated and non-hashable values.
self._reverse = dict((value, key) for
(key, value) in self.iteritems())
self._dirty = False
return self._reverse




An even more lightweight solution is to give up O(1) for the reverse
lookup:


# untested
class ReversableDict(dict):
def lookupvalue(self, value):
for k,v in self.iteritems():
if v == value: return k
raise ValueError('value not found')
def lookupallvalues(self, value):
results = []
for k,v in self.iteritems():
if v == value: results.append(k)
return results

 

[Aaron Brady]

Hi, this is a continuation of something that comes up now and again
about reverse lookups on dictionaries, as well as a follow-up to my
pursuit of a Relation class from earlier.
[...]

What's the best way to construct this class?  Or, do you have an
argument that it could not be simpler than using a relational db?
Brainstorming, not flamestorming.

Here's a lightweight solution that uses lazy calculation of the reverse
dict. It makes a number of assumptions:

- both keys and values will be hashable and unique;
- the dict won't be so large that calculating the reverse dictionary will
be time consuming;
- modifications to instance.reverse are undefined.

Usage:

d = ReverseDict(x=2, y=3, z=4)
d['x'] 2
d.reverse[2] 'x'
d['a'] = 0
d.reverse[0]

'a'

def make_dirty(func):
    from functools import wraps
    @wraps(func)
    def f(self, *args, **kwargs):
        self._dirty = True
        return func(self, *args, **kwargs)
    return f

# only tested a little bit
class ReverseDict(dict):
    def __init__(self, *args, **kwargs):
        super(ReverseDict, self).__init__(*args, **kwargs)
        self._dirty = True
    @make_dirty
    def clear():
        super(ReverseDict, self).clear() snip
    @property
    def reverse(self):
        if self._dirty:
            # Modify this to support repeated and non-hashable values.
            self._reverse = dict((value, key) for
            (key, value) in self.iteritems())
            self._dirty = False
        return self._reverse

An even more lightweight solution is to give up O(1) for the reverse
lookup:

# untested
class ReversableDict(dict):
    def lookupvalue(self, value):
        for k,v in self.iteritems():
            if v == value: return k
        raise ValueError('value not found')
    def lookupallvalues(self, value):
        results = []
        for k,v in self.iteritems():
            if v == value: results.append(k)
        return results

Can you make it work for a 3-way lookup?

 

[Steven D'Aprano]

Can you make it work for a 3-way lookup?

What do you mean "3-way lookup"?

I'm going to take a guess...

A maps to B, B maps to C, and C maps to A.


Is that what you mean?

 

[Aaron Brady]

What do you mean "3-way lookup"?

I'm going to take a guess...

A maps to B, B maps to C, and C maps to A.

Is that what you mean?

So long as you can get B and C from A, and C and A from B, and A and B
from C, it classifies as a "3-way lookup", or at least how I was using
the term. (In other words, yes.)

Yours does that, but it takes two steps from B to A. For example:

c2a[ b2c[ keyinB ] ] == keyinA

This goes from B to C, then from C to A. From what you said, you
would have no way to get from B directly to A. Is that correct? If
so, it's a little awkward, and the direct way would be nice too.