如何在Python中保持范围？

Question

我需要保存一些范围（间隔不同）和对应的数值，像下面这样：

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

我应该怎么存储这些数据呢？是用字典，比如 {'0': 1234, '5001': 1231, '10001': 3242, ...} 吗？

存好之后，我需要根据范围来查找对应的值，比如说，输入 6000 应该返回 1231。如果我用字典存储，这样查找该怎么做呢？

更新一下：这些范围之间没有空隙，范围的数量也不多，大约有50个。

Answer 1

我可以假设存储的范围之间没有空隙吗？

我的做法是：

• 把映射关系存成一个字典（范围起始 -> 值），就像你之前做的那样。
• 要获取键K的值：
  • 在字典的键上进行二分查找，找到小于或等于K的最大键（这个过程的时间复杂度是O(logN)）。
  • 返回这个键对应的值（这个过程的时间复杂度是O(1)）。

Answer 2

还有一种完全不同但速度很快的方法，就是使用 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 3

我建议你把它存储为一个字典的列表，因为：

明确比隐含要好。

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

你可以像下面这样定义一个字典：

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 5

在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不在任何范围内的情况。