How to save ranges using python?

Question

I have to store ranges (at different intervals) and corresponding values, as shown below:

• 0..5000: 1234
• 5001..10000: 1231
• 10001.20000: 3242
• ...
• 50001..100000: 3543
• 100001..200000: 2303
• ...

How to save it? How dict like {'0': 1234, '5001': 1231, '10001': 3242, ...}?

After saving, I will need to find the appropriate value, but it should look for a range - for example, it 6000should return 1231. If I save it as a dict, how do I search?

Upd. There are no spaces in the intervals, and the number of ranges is rather small (~ 50).

Answer 1

Python 3.4 . 2.7, . , , .

d = {
  range(0, 5000): 1234,
  range(5001, 10000): 1231,
  range(10001, 20000): 3242
}

x = 6000
r = [i[1] for i in d.items() if x in i[0]][0]
# r == 1231

, , x .

Answer 2

, :

Explicit is better than implicit.

>>> rang = [{'start': 0, 'end': 5000, 'id': 1234}, {'start': 5000, 'end': 10000, 'id': 1231}, {'start': 10001, 'end': 20000, 'id': 342}]
>>> num = 10
>>> for r in rang:
...   if r['start'] < num < r['end']:
...     print r['id']
... 
1234
>>> num = 10500
>>> for r in rang:
...   if r['start'] < num < r['end']:
...     print r['id']
... 
342
>>> 

Answer 3

dict, :

d = {"0:5000": {"range": [0, 5000],
                "value": 1234},
     "5001:10000":{"range":[5001, 10000],
                   "value": 1432}}

,

class MyRange(object):

    def __init__(self, start, end, value):
        self.start = start
        self.end = end
        self.value = value

    def has_in_range(self, num):
        return self.start <= num <= self.end

MyRange

l = [MyRange(0, 5000, 1234), MyRange(5001, 10000, 3124)]

, ,

def search(num):
    for element in l:
        if element.has_in_range(num):
            return element.value
    return -1    

:

>>> search(10)
1234
>>> search(6000)
3124

Answer 4

( ) - bisect ( , ).

import bisect

ranges = (
    (0, 1234),
    (5001, 1231),
    (10001, 3242),
    (50001, 3543),
    (100001, 2303),
)

def find_range(value):
    min_ = ranges[0][0]
    if min_ > value:
        raise ValueError('Values smaller than %d are not supported' % min_)

    # Search for the insert point using bisect but add 1 so we handle
    # corner cases correctly
    key = value + 1, 0

    # Use bisect to find the index
    index = bisect.bisect(ranges, key)

    # Return the 2nd item from the tuple since that contains the ID
    start_index, id_ = ranges[index - 1]
    return id_

print 'Testing standard ranges'
for i in range(15):
    i = 2 ** i
    print 'Looking for %d, got: %d' % (i, find_range(i))

print
print 'Testing corner cases:'
for start, id_ in ranges:
    for i in range(start - 1, start + 2):
        try:
            value = find_range(i)
        except ValueError, value:
            pass

        print 'Looking for %d, got: %s' % (i, value)

:

Testing standard ranges
Looking for 1, got: 1234
Looking for 2, got: 1234
Looking for 4, got: 1234
Looking for 8, got: 1234
Looking for 16, got: 1234
Looking for 32, got: 1234
Looking for 64, got: 1234
Looking for 128, got: 1234
Looking for 256, got: 1234
Looking for 512, got: 1234
Looking for 1024, got: 1234
Looking for 2048, got: 1234
Looking for 4096, got: 1234
Looking for 8192, got: 1231
Looking for 16384, got: 3242

Testing corner cases:
Looking for -1, got: Values smaller than 0 are not supported
Looking for 0, got: 1234
Looking for 1, got: 1234
Looking for 5000, got: 1234
Looking for 5001, got: 1231
Looking for 5002, got: 1231
Looking for 10000, got: 1231
Looking for 10001, got: 3242
Looking for 10002, got: 3242
Looking for 50000, got: 3242
Looking for 50001, got: 3543
Looking for 50002, got: 3543
Looking for 100000, got: 3543
Looking for 100001, got: 2303
Looking for 100002, got: 2303

Answer 5

, ?

:

• dict (range_start → value) ,
• to get the value for key K:
  • do a binary search on dict keys to find the largest key less than or equal to K (O (logN))
  • return the value for this key (O (1)).

Answer 6

This is a competing answer to Wolph's, using its code, but changed:

import bisect

range_stops = [0, 4, 8]
range_ids   = [0, 1, 2]

def find_range(value):
    # Need to limit to `0` because there is no -1th index
    index = max(0, bisect.bisect_right(range_stops, value)-1)

    return range_ids[index]

for i in range(-2, 10):
    print("{:2} → {}".format(i, find_range(i)))

#>>> -2 → 0
#>>> -1 → 0
#>>>  0 → 0
#>>>  1 → 0
#>>>  2 → 0
#>>>  3 → 0
#>>>  4 → 1
#>>>  5 → 1
#>>>  6 → 1
#>>>  7 → 1
#>>>  8 → 2
#>>>  9 → 2

This is a bit simpler, but requires two data structures instead of one. On the plus side, it’s much easier to do the job. It will also support ranges and floating point indices.