reverse dict lookup & Relation class

Discussion in 'Python' started by Aaron Brady, Jan 15, 2009.

  1. Aaron Brady

    Aaron Brady Guest

    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.
     
    Aaron Brady, Jan 15, 2009
    #1
    1. Advertising

  2. Aaron Brady

    Chris Rebert Guest

    On Wed, Jan 14, 2009 at 4:30 PM, Aaron Brady <> wrote:
    > 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
    --
    Follow the path of the Iguana...
    http://rebertia.com
     
    Chris Rebert, Jan 15, 2009
    #2
    1. Advertising

  3. Aaron Brady

    MRAB Guest

    Aaron Brady wrote:
    > 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.
     
    MRAB, Jan 15, 2009
    #3
  4. Aaron Brady

    Aaron Brady Guest

    On Jan 14, 7:04 pm, Chris Rebert <> wrote:
    > On Wed, Jan 14, 2009 at 4:30 PM, Aaron Brady <> wrote:
    > > 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, Jan 16, 2009
    #4
  5. Aaron Brady

    Aaron Brady Guest

    On Jan 14, 7:54 pm, MRAB <> wrote:
    > Aaron Brady wrote:
    > > 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.
     
    Aaron Brady, Jan 16, 2009
    #5
  6. On Wed, 14 Jan 2009 16:30:36 -0800, Aaron Brady wrote:

    > 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




    --
    Steven
     
    Steven D'Aprano, Jan 16, 2009
    #6
  7. Aaron Brady

    Aaron Brady Guest

    On Jan 16, 5:03 am, Steven D'Aprano <st...@REMOVE-THIS-
    cybersource.com.au> wrote:
    > On Wed, 14 Jan 2009 16:30:36 -0800, Aaron Brady wrote:
    > > 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
    >
    > --
    > Steven


    Can you make it work for a 3-way lookup?
     
    Aaron Brady, Jan 17, 2009
    #7
  8. On Sat, 17 Jan 2009 00:24:21 -0800, Aaron Brady wrote:

    > 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?


    --
    Steven
     
    Steven D'Aprano, Jan 17, 2009
    #8
  9. Aaron Brady

    Aaron Brady Guest

    On Jan 17, 10:45 am, Steven D'Aprano <st...@REMOVE-THIS-
    cybersource.com.au> wrote:
    > On Sat, 17 Jan 2009 00:24:21 -0800, Aaron Brady wrote:
    > > 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?


    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.
     
    Aaron Brady, Jan 18, 2009
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. =?Utf-8?B?RGFuIE5hc2g=?=

    reverse DNS lookup

    =?Utf-8?B?RGFuIE5hc2g=?=, Oct 14, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    465
    =?Utf-8?B?RGFuIE5hc2g=?=
    Oct 14, 2004
  2. Madhur Ahuja
    Replies:
    1
    Views:
    751
    Paul Lutus
    Aug 29, 2004
  3. Replies:
    5
    Views:
    403
    Keith Jones
    Jul 28, 2003
  4. rh0dium
    Replies:
    10
    Views:
    858
    bruno at modulix
    Mar 10, 2006
  5. Scott McFadden

    Reverse lookup question (IP to Country)

    Scott McFadden, Oct 25, 2007, in forum: ASP .Net
    Replies:
    1
    Views:
    342
    Juan T. Llibre
    Oct 25, 2007
Loading...

Share This Page