Python:有效地检查整数是否在*many*范围内

Question

我正在开发一个邮资申请,需要根据多个邮政编码范围检查整数邮政编码,并根据邮政编码匹配的范围返回不同的代码.

每个代码都有多个邮政编码范围.例如,如果邮政编码在1000-2429,2545-2575,2640-2686范围内或等于2890,则应返回M代码.

我可以这样写:

if 1000 <= postcode <= 2429 or 2545 <= postcode <= 2575 or 2640 <= postcode <= 2686 or postcode == 2890:
    return 'M'

但这似乎是很多代码行,因为有27个可返回代码和77个总范围要检查.是否有更高效(并且最好更简洁)的方法使用Python将整数与所有这些范围匹配？

---

编辑:有很多优秀的解决方案,所以我已经实现了所有可能的解决方案,并对其性能进行了基准测试.

该程序的环境是一个Web服务(实际上是Django),它需要在运行中逐个检查邮政编码区域代码.那么,我的首选实现是可以快速用于每个请求的实现,并且不需要将任何进程保存在内存中,或者需要批量处理许多邮政编码.

我timeit.Timer使用随机生成的邮政编码每次使用默认的1000000次重复测试以下解决方案.

IF解决方案(我的原创)

if 1000 <= postcode <= 2249 or 2555 <= postcode <= 2574 or ...:
    return 'M'
if 2250 <= postcode <= 2265 or ...:
    return 'N'
...

1m代表的时间:5.11秒.

元组中的范围(Jeff Mercado)

我脑子里更优雅,更容易进入和阅读范围.如果它们随时间变化特别好,这是可能的.但它的实施速度确实慢了四倍.

if any(lower <= postcode <= upper for (lower, upper) in [(1000, 2249), (2555, 2574), ...]):
    return 'M'
if any(lower <= postcode <= upper for (lower, upper) in [(2250, 2265), ...]):
    return 'N'
...

1m代表的时间:19.61秒.

设置会员资格(gnibbler)

正如作者所说,"只有在构建集合一次以检查循环中的许多邮政编码时才会更好".但我还以为无论如何都要测试它.

if postcode in set(chain(*(xrange(start, end+1) for start, end in ((1000, 2249), (2555, 2574), ...)))):
    return 'M'
if postcode in set(chain(*(xrange(start, end+1) for start, end in ((2250, 2265), ...)))):
    return 'N'
...

1米重复的时间:339.35秒.

Bisect(罗伯特国王)

这个可能比我的智力水平高一点.我学到了很多关于该bisect模块的知识,但是无法确定哪些参数可find_ge()用于进行可运行的测试.我希望通过许多邮政编码循环会非常快,但如果每次都必须进行设置,那就不行了.所以,用填充100万次重复numbers,edgepairs,edgeanswers等的只是一个邮政区码(在中号与四个范围的代码),但不实际运行fast_solver:

1m代表的时间:105.61秒.

Dict(哨兵)

使用每个邮政区域代码预先生成一个代码,cPickled在源文件(106 KB)中,并为每次运行加载.我期待这种方法有更好的性能,但至少在我的系统上,IO真的破坏了它.该服务器是一款不那么令人眼花缭乱的快速顶级Mac Mini.

1m代表的时间:5895.18秒(从10,000次运行中推断).

摘要

嗯,我期待有人给出一个我没有考虑过的简单的"呃"答案,但事实证明这更复杂(甚至有点争议).

如果在这种情况下计算每纳秒的效率,我可能会保持一个单独的进程运行,它实现了二进制搜索或dict解决方案之一,并将结果保存在内存中以实现极快的查找.但是,由于IF树只需要五秒钟才能运行一百万次,这对于我的小型企业而言足够快,这就是我最终在我的应用程序中使用的内容.

感谢大家的贡献!

Answer 1

您可以将范围抛出到元组中,并将元组放在列表中.然后any()用来帮助您查找您的值是否在这些范围内.

ranges = [(1000,2429), (2545,2575), (2640,2686), (2890, 2890)]
if any(lower <= postcode <= upper for (lower, upper) in ranges):
    print('M')

Answer 2

这是一个使用 numpy 的快速而简短的解决方案：

import numpy as np
lows = np.array([1, 10, 100]) # the lower bounds
ups = np.array([3, 15, 130]) # the upper bounds

def in_range(x):
    return np.any((lows <= x) & (x <= ups))

现在举例来说

in_range(2) # True
in_range(23) # False

Answer 3

可能最快的是检查一组的成员资格

>>> from itertools import chain
>>> ranges = ((1000, 2429), (2545, 2575), (2640, 2686), (2890, 2890))
>>> postcodes = set(chain(*(xrange(start, end+1) for start, end in ranges)))
>>> 1000 in postcodes
True
>>> 2500 in postcodes
False

但它确实以这种方式使用更多内存,并且构建集合需要时间,因此只有在构建集合一次以检查循环中的许多邮政编码时才会更好

编辑:似乎不同的范围需要映射到不同的字母

>>> from itertools import chain
>>> ranges = {'M':((1000,2429), (2545,2575), (2640,2686), (2890, 2890)),
              # more ranges
              }
>>> postcodemap = dict((k,v) for v in ranges for k in chain(*imap(xrange, *zip(*ranges[v]))))    
>>> print postcodemap.get(1000)
M
>>> print postcodemap.get(2500)
None

Answer 4

在进行不等式时,你只需要解决边缘情况和边缘情况之间的一个数.

例如,如果您在TEN上进行以下测试:

10 <20,10 <15,10> 8,10> 12

它会给出True True True False

但请注意,最接近10的数字是8和12

这意味着9,10,11将给出10个答案.如果你没有太多的初始范围数并且它们很稀疏那么这很有帮助.否则,您需要查看您的不等式是否具有传递性并使用范围树或其他东西.

所以你能做的就是把你所有的界限分成几个区间.例如,如果你的不等式有数字12,50,192,999

你得到以下间隔,所有人都有相同的答案:少于12,12,13-49,50,51-191,192,193-998,999,999+

从这些区间可以看出,我们只需要解决9个案例,然后我们就可以快速解决任何问题.

下面是一个示例,说明如何使用这些预先计算的结果来解决新的数字x:

a)是xa边界？(是否在集合中)如果是,则返回您之前为该边界找到的答案.否则使用案例b)

b)找到小于x的最大边界数,称之为maxS 找到大于x 的最小边界数称为minL.现在只返回之前找到的maxS和minL之间的解决方案.

请参阅Python二进制搜索类函数,以查找排序列表中的第一个数字,该数字大于 查找最接近数字的特定值.bisect模块将帮助(在您的代码中导入它)这将有助于查找maxS和minL

您可以使用bisect和我在示例代码中包含的函数:

def find_ge(a, key):
    '''Find smallest item greater-than or equal to key.
    Raise ValueError if no such item exists.
    If multiple keys are equal, return the leftmost.

    '''
    i = bisect_left(a, key)
    if i == len(a):
        raise ValueError('No item found with key at or above: %r' % (key,))
    return a[i]




ranges=[(1000,2429), (2545,2575), (2640,2686), (2890, 2890)]
numbers=[]
for pair in ranges:
        numbers+=list(pair)

numbers+=[-999999,999999] #ensure nothing goes outside the range
numbers.sort()
edges=set(numbers)

edgepairs={}

for i in range(len(numbers)-1):
        edgepairs[(numbers[i],numbers[i+1])]=(numbers[i+1]-numbers[i])//2



def slow_solver(x):
        return #your answer for postcode x


listedges=list(edges)
edgeanswers=dict(zip(listedges,map(solver,listedges)))
edgepairsanswers=dict(zip(edgepairs.keys(),map(solver,edgepairs.values())))

#now we are ready for fast solving:
def fast_solver(x):
        if x in edges:
                return edgeanswers[x]
        else:
                #find minL and maxS using find_ge and your own similar find_le
                return edgepairsanswers[(minL,maxS)]

Answer 5

完整的数据不存在，但我假设范围不重叠，因此您可以将范围表示为单个排序的范围元组及其代码：

ranges = (
    (1000, 2249, 'M'), 
    (2250, 2265, 'N'), 
    (2555, 2574, 'M'),
    # ...
)

这意味着我们可以一次性对它们进行二分搜索。这应该是O(log(N))时间，这应该会在非常大的集合上产生相当不错的性能。

def code_lookup(value, ranges):
    left, right = 0, len(ranges)

    while left != right - 1:
        mid = left + (right - left) // 2

        if value <= ranges[mid - 1][1]:  # Check left split max
            right = mid
        elif value >= ranges[mid][0]:    # Check right split min
            left = mid
        else:                            # We are in a gap
            return None

    if ranges[left][0] <= value <= ranges[left][1]:
        # Return the code
        return ranges[left][2]

我没有你的确切值，但为了进行比较，我针对一些生成的范围（具有各种代码的 77 个范围）运行了它，并将其与简单的方法进行了比较：

def get_code_naive(value):
    if 1000 < value < 2249:
        return 'M'
    if 2250 < value < 2265:
        return 'N'
    # ...

1,000,000 的结果是，朴素版本运行了大约 5 秒，二分搜索版本运行了 4 秒。所以它更快一点（20%），代码更容易维护，列表越长，随着时间的推移，它的性能就越优于简单的方法。