Associative array in python with keys as a fragment of array

Question

How to better implement such thing:

Loop over the numbers. Each number in diapason and belong to one part of associative array.

E.g.

 di = {}
 di[ xrange(0,10) ] = "A"
 di[ xrange(11,20) ] = "B"
 di[ xrange(21,30) ] = "C"

 direction = di[ 24 ]
 # direction should be "C"

 direction = di[ 6 ]
 # direction should be "A"

Edit: Populate whole di with discreet numbers is not my way, because I'm talking about IP addresses, really big data, such as netmasks 255.255.255.255. Such di will overflow my RAM.

Answer 1

I would create a custom dict that takes xranges as keys :

class DictRange(dict):
    def __getitem__(self, val):
        for key in self.keys():
            if val in key:
                return super(DictRange,self).__getitem__(key)

The drawback is that you have to go through all the keys to find your element. Use like that :

di = DictRange()
di[ xrange(0,10) ] = "A"
di[ xrange(11,20) ] = "B"
di[ xrange(21,30) ] = "C"

print di[24]
# C
print di[6]
# A

See http://repl.it/WAJ

Update

Using bisect and assuming that you can spare some time during initialization to speed up access, you can do something like:

import bisect
class DictRange(dict):

    def __setitem__(self, key, val):
        super(DictRange,self).__setitem__(key, val)
        self.ks = [key[0] for key in self.keys()]

    def __getitem__(self, val):
        return super(DictRange,self).__getitem__(self.keys()[bisect.bisect(self.ks, val) - 1])

the get will be O(logn) where n is the number of keys, but the set will become O(n). As for the next solution, it relies on the ranges being contiguous.

Other solution

An other solution, which could be faster, depending on your range sizes, would be to use as key the first item of the range, and a bisect to find the proper key:

import bisect
ranges = [0, 11, 21, 31]
di = {}
di[0] = 'A'
di[11] = 'B'
di[21] = 'C'
di[31] = 'unknown' # special value to indicate the end of the range

print di[ranges[bisect.bisect(ranges, 24) - 1]]
# C
print di[ranges[bisect.bisect(ranges, 6) - 1]]
# A
print di[ranges[bisect.bisect(ranges, 31) - 1]]
# Unknown

This will be much faster. bisect is O(logn) where n is the number of ranges, the rest is O(1)

Answer 2

di = dict.fromkeys(xrange(0, 10), 'A')
di.update(dict.fromkeys(xrange(10, 20), 'B'))
di.update(dict.fromkeys(xrange(20, 30), 'C'))
print(di)

yields

{0: 'A', 1: 'A', 2: 'A', 3: 'A', 4: 'A', 5: 'A', 6: 'A', 7: 'A', 8: 'A', 9: 'A', 10: 'B', 11: 'B', 12: 'B', 13: 'B', 14: 'B', 15: 'B', 16: 'B', 17: 'B', 18: 'B', 19: 'B', 20: 'C', 21: 'C', 22: 'C', 23: 'C', 24: 'C', 25: 'C', 26: 'C', 27: 'C', 28: 'C', 29: 'C'}

Note that xrange(N, M) generates ints starting at N and ending at M-1 (inclusive). So if you want to include 10, 20 in the keys, then the xranges should be xrange(10, 20) and xrange(20, 30).

Answer 3

You could use tuples instead of lists to solve the TypeError (which your code doesn't raise FWIW) but the lookup still wouldn't work. The simplest thing that could possibly work would be to populate you dict with every discrete key for a given value, ie:

map = (
   (0, 10, "A"),
   (11, 20, "B"),
   # etc
   )

d = {}
for start, stop, val in map:
   for k in xrange(start, stop):
       d[k] = val

Answer 4

If you don't want to populate a dictionary just use a function,

from __future__ import division
import string
def return_ltr(i):
    n = i//10 
    return string.ascii_uppercase[n]

Otherwise, if you want to populate a dictionary do the following. Your current code is generating xrange objects and using them as keys. However, that is not the same as using the numbers for keys. Try the following,

import string
d = {}
i = 0
for ltr in string.ascii_uppercase:
    for j in xrange(10):
        d[i] = ltr
        i += 1

If you only want a subset of the letters you can slice string.ascii_uppercase. For example using string.ascii_uppercase[0:3] will just give you A, B, and C.