"Multi-key" dictionary

Question

I was making a relatively large-scale project in Python as a learning experiment, and in the process I found that it would be useful to have a map (or, in Python, I guess they're called dictionaries) where a value could have multiple keys. I couldn't find much support for this out there, so this is the implementation I ended up going with:

def range_dict(*args):
    return_val = {}
    for k,v in args:
        for i in k:
            return_val[i] = v
    return return_val

COINS = range_dict((range(1,15), None),
                     (range(15,30), "1d6x1000 cp"),
                     (range(30,53), "1d8x100 sp"),
                     (range(53,96), "2d8x10 gp"),
                     (range(96,101), "1d4x10 pp"))

I was told that this wasn't really a good way to achieve what I wanted to do, but I don't really understand why. It works perfectly in my application. What's wrong with this? Is there a better, more Pythonic way to do this?

Answer 1

1. Comments on your code

1. No docstrings! What does your code do and how am I supposed to use it?

2. No test cases. This ought to be a good opportunity to use doctests.

3. Given that your purpose here is to implement RPG lookup tables, your design seems a bit hard to use. The printed RPG table probably says something like this:

   1-8     giant spider
   9-12    skeleton
   13-18   brass dragon
   ...
   

   but you have to input it like this (adding one to the limit of each range):

   range_dict((range(1, 9), "giant spider"),
              (range(9, 13), "skeleton"),
              (range(13, 18), "brass dragon"),
              ...)
   

   which would be easy to get wrong.

4. The design also seems fragile, because it doesn't ensure that the ranges are contiguous. If you made a data entry mistake:

   d = range_dict((range(1, 8), "giant spider"),
                  (range(9, 13), "skeleton"),
                  (range(13, 18), "brass dragon"),
                  ...)
   

   then the missing key would later result in an error:

   >>> d[8]
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   KeyError: 8
   

2. An alternative approach

Here's how I'd implement this lookup table:

from bisect import bisect_left
from collections.abc import Mapping

class LookupTable(Mapping):
    """A lookup table with contiguous ranges of small positive integers as
    keys. Initialize a table by passing pairs (max, value) as
    arguments. The first range starts at 1, and second and subsequent
    ranges start at the end of the previous range.

    >>> t = LookupTable((10, '1-10'), (35, '11-35'), (100, '36-100'))
    >>> t[10], t[11], t[100]
    ('1-10', '11-35', '36-100')
    >>> t[0]
    Traceback (most recent call last):
      ...
    KeyError: 0
    >>> next(iter(t.items()))
    (1, '1-10')

    """
    def __init__(self, *table):
        self.table = sorted(table)
        self.max = self.table[-1][0]

    def __getitem__(self, key):
        key = int(key)
        if not 1 <= key <= self.max:
            raise KeyError(key)
        return self.table[bisect_left(self.table, (key,))][1]

    def __iter__(self):
        return iter(range(1, self.max + 1))

    def __len__(self):
        return self.max

Notes on this implementation:

1. The constructor takes the maximum for each range (not the maximum plus one), making data entry less error-prone.

2. The minimum of each range is taken from the end of the previous range, thus ensuring that there are no gaps between ranges.

3. The collections.abc.Mapping abstract base class provides much of the functionality of a read-only dictionary. The idea is that you supply the __getitem__, __iter__ and __len__ methods, and the Mapping class supplies implementations of __contains__, keys, items, values, get, __eq__, and __ne__ methods for you. (Which you can override if you need to, but that's not necessary here.)

4. I've used bisect.bisect_left to efficiently look up keys in the sorted table.

Answer 2

So, I came across this issue earlier today. Wasn't real thrilled with most of the solutions here, mostly because I wanted to be able to set normal keys, but also set a range of keys all at once when needed, so I came up with this:

class RangedDict(dict):
    """
    A dictionary that supports setting items en masse by ranges, but also supports normal keys.

    The core difference between this and any other dict is that by passing a tuple of 2 to 3 numeric values, an
    inclusive range of keys will be set to that value. An example usage is:

    >>> d = RangedDict({
    ...   (1, 5): "foo"
    ... })
    >>> print d[1]  # prints "foo"
    >>> print d[4]  # also prints "foo"
    >>> print d[5]  # still prints "foo" because ranges are inclusive by default
    >>> d['bar'] = 'baz'
    >>> print d['bar']  # prints 'baz' because this also works like a normal dict

    Do note, ranges are inclusive by default, so 5 is also set. You can control
    inclusivity via the `exclusive` kwarg.

    The third, optional, parameter that can be given to a range tuple is a step parameter (analogous to the step
    parameter in xrange), like so: `(1, 5, 2)`, which would set keys 1, 3, and 5 only. For example:

    >>> d[(11, 15, 2)] = "bar"
    >>> print d[13]  # prints "bar"
    >>> print d[14]  # raises KeyError because of step parameter

    NOTE: ALL tuples are strictly interpreted as attempts to set a range tuple. This means that any tuple that does NOT
    conform to the range tuple definition above (e.g., `("foo",)`) will raise a ValueError.
    """
    def __init__(self, data=None, exclusive=False):
        # we add data as a param so you can just wrap a dict literal in the class constructor and it works, instead of
        # having to use kwargs
        self._stop_offset = 0 if exclusive else 1
        if data is None:
            data = {}

        for k, v in data.items():
            if isinstance(k, tuple):
                self._store_tuple(k, v)
            else:
                self[k] = v

    def __setitem__(self, key, value):
        if isinstance(key, tuple):
            self._store_tuple(key, value)
        else:
            # let's go ahead and prevent that infinite recursion, mmmmmkay
            dict.__setitem__(self, key, value)

    def _store_tuple(self, _tuple, value):
        if len(_tuple) > 3 or len(_tuple) < 2:
            # eventually, it would be nice to allow people to store tuples as keys too. Make a new class like: RangeKey
            # to do this
            raise ValueError("Key: {} is invalid! Ranges are described like: (start, stop[, step])")

        step = _tuple[2] if len(_tuple) == 3 else 1
        start = _tuple[0]
        stop = _tuple[1]

        # +1 for inclusivity
        for idx in xrange(start, stop + self._stop_offset, step):
            dict.__setitem__(self, idx, value)

It uses tuples to describe ranges, which looks rather elegant, if I do say so myself. So, some sample usage is:

d = RangedDict()
d[(1, 15)] = None
d[(15, 25)] = "1d6x1000 cp"

Now you can easily use d[4] and get what you want.

The astute reader will however notice that this implementation does not allow you to use tuples as keys at all in your dict. I don't see that as a common use case, or something elegant to do, in general, so I felt it was worth the tradeoff. However, a new class could be made named along the lines of RangeKey(1, 5, step=2) that could be used to key ranges, thus letting you key tuples as well.

I hope a future reader enjoys my code!

Answer 3

The main drawback to this arrangement is that it's wasteful. For a small case it's not a big deal but for a large range of values you're going to need an equally large range of keys, which will mean both a lot of searching for the right key and also expending memory to store all the keys.

For the specific application the python bisect module is handy. It's great for fast searching through sorted data, so its fast for this kind of lookup table:

import bisect

# Set up the data. Don't do it inside the function, you don't
# want to do it over and over in the function!
xp_table = [(0, 0), (15, "1d6x1000 cp"), (30, "1d8x100 sp"), (53, "2d8x10 gp"), (96 ,"1d4x10 pp")]
xp_table.sort() 
keys = [k[0] for k in xp_table]

def get_reward(val):
    idx = bisect.bisect_right(keys, val)
        return xp_table[idx][1]

A dictionary based solution will still be better for data that doesn't sort, or does not fall into neat ranges.

Answer 4

My attempt, keep in my mind that I'm not close to any of pro's around here.

for i in range(1, 101):
    if i < 15:
        my_coins[i] = None
    if 15 <= i < 30:
        my_coins[i] = '1d6x1000 cp'
    if 30 <= i < 53:
        my_coins[i] = '1d8x100 sp'
    if 53 <= i < 96:
        my_coins[i] = '2d8x10 gp'
    if i >= 96:
        my_coins[i] = '1d4x10 pp'

Put it in a function and return my_coins.

Answer 5

If everything wanted with the datasctructure is to be able to generate random coin, it's much easier to do directly by generating random integer number from [1, 100] and then use if-statements to go through choices (ranges).

Another possibility is to have all the values in a list as many times as their range length and use random.choice() function to fetch one.

Also, I do not find the original code particularly bad. Write tests, experiment, and you are there.

Answer 6

To answer the original question: One drawback of a multi-key map is that more memory is used to store the second key.

However. here is a way to get your desired functionality:

d = { # key is max value
    5: 'one',
    10: 'two',
    15: 'three',
    20: 'four',
    25: 'five',
    30: 'six'}

MINIMUM = 1

for i in range(10):
    d[[key for key in sorted(d) if key >=random.randint(MINIMUM, max(d))][0]]

'two'
'four'
'two'
'five'
'three'
'three'
'five'
'four'
'three'
'four'

You could replace the part sorted(d) with one_off_pre_sorted_keys:

one_off_pre_sorted_keys = sorted(d)