Python: эффективно проверяет, находится ли целое число в * многих * диапазонах

Ответ 1

Ваши тесты, похоже, включают настройку структуры данных с нуля для каждого вызова. Зачем? Вы рассматривали отображение кода почтового индекса в регион, загружаемое из файла ONCE во время импорта модуля? Они выглядят подозрительно, как австралийские почтовые индексы. Если это так, их очень мало.

Ответ 2

Вы можете перебросить диапазоны в кортежи и поместить кортежи в список. Затем используйте any(), чтобы узнать, находится ли ваше значение в этих диапазонах.

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

Ответ 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

Но он использует больше памяти таким образом, и для построения набора требуется время, поэтому лучше только, если вы создаете набор один раз, чтобы проверять многие почтовые индексы в цикле

EDIT: кажется, что разные диапазоны должны сопоставляться с разными буквами

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

Ответ 4

вам нужно решить только краевые случаи и одно число между краевыми случаями при выполнении неравенств.

например. если вы выполните следующие тесты в TEN:

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

Он даст True True True False

но обратите внимание, что самые близкие числа до 10 - 8 и 12

это означает, что 9,10,11 даст ответы, которые были сделаны десятью. Если у вас слишком много начальных номеров дальности, и они разрежены, то это поможет. В противном случае вам нужно будет проверить, являются ли ваши неравенства транзитивными и используют дерево диапазонов или что-то в этом роде.

Итак, что вы можете сделать, это сортировать все свои границы с интервалами. например если ваши неравенства имели числа 12, 50, 192,999

вы получите следующие интервалы, которые ВСЕ имеют один и тот же ответ: менее 12, 12, 13-49, 50, 51-191, 192, 193-998, 999, 999 +

как вы можете видеть из этих интервалов, нам нужно решить только 9 случаев, и мы можем быстро решить что угодно.

Вот пример того, как я мог бы выполнить его для решения для нового числа x, используя эти предварительно рассчитанные результаты:

a) является x границей? (это в наборе) если да, то верните ответ, который вы нашли для этой границы ранее. в противном случае используйте случай 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)]

Ответ 5

Вот быстрое и короткое решение, используя 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

Ответ 6

Недавно у меня было аналогичное требование, и я использовал манипуляции с битами, чтобы проверить, принадлежит ли целое число указанному диапазону. Это определенно быстрее, но я думаю, что не подходит, если ваши диапазоны содержат огромные числа. Я свободно скопировал примеры методов из здесь

Сначала мы создаем двоичное число, которое будет иметь все биты в диапазоне, установленном в 1.

#Sets the bits to one between lower and upper range 
def setRange(permitRange, lower, upper):
  # the range is inclusive of left & right edge. So add 1 upper limit
  bUpper = 1 << (upper + 1)
  bLower = 1 << lower
  mask = bUpper - bLower
  return (permitRange | mask)

#For my case the ranges also include single integers. So added method to set single bits
#Set individual bits  to 1
def setBit(permitRange, number):
  mask = 1 << vlan
  return (permitRange| mask)

Теперь время для разбора диапазона и заполнения нашей двоичной маски. Если наибольшее число в диапазоне равно n, мы будем создавать целое число больше 2 ^ n в двоичном

#Example range (10-20, 25, 30-50)
rangeList = "10-20, 25, 30-50"
maxRange = 100
permitRange = 1 << maxRange
for range in rangeList.split(","):
    if range.isdigit():
        permitRange = setBit(permitRange, int(range))
    else:
        lower, upper = range.split("-",1)
        permitRange = setRange(permitRange, int(lower), int(upper))
    return permitRange

Чтобы проверить, принадлежит ли число "n" к диапазону, просто проверьте бит в n-й позиции

#return a non-zero result, 2**offset, if the bit at 'offset' is one.
def testBit(permitRange, number):
    mask = 1 << number
    return (permitRange & mask)

if testBit(permitRange,10):
    do_something()

Ответ 7

Полных данных нет, но я предполагаю, что диапазоны не перекрываются, поэтому вы можете выразить свои диапазоны как один отсортированный набор диапазонов, а также их коды:

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%), коды намного приятнее поддерживать, и чем дольше этот список получает, тем больше он будет выполнять наивный метод с течением времени.

Ответ 8

Предупреждение. Вероятно, это преждевременная оптимизация. Для большого списка диапазонов это может стоить, но, вероятно, не в вашем случае. Кроме того, хотя словарные/установочные решения будут использовать больше памяти, они по-прежнему, вероятно, лучший выбор.

Вы можете выполнить двоичный поиск в конечных точках диапазона. Это было бы легко, если все диапазоны не перекрывались, но все же можно было бы сделать (с некоторыми изменениями) для перекрывающихся диапазонов.

Сделайте поиск с наивысшим совпадением без бинарного поиска. Это то же самое, что и двоичный поиск с помощью метода find-lower-match-more-than-or-equal (lower bound), за исключением того, что вы вычитаете один из результата.

Используйте полуоткрытые элементы в списке конечных точек - то есть, если ваш диапазон 1000..2429 включительно, используйте значения 1000 и 2430. Если вы получите конечную точку и начальную точку с одинаковым значением (два диапазона касаются, поэтому между ними нет промежутка) исключить конечную точку для нижнего диапазона из вашего списка.

Если вы найдете конечную точку начала диапазона, ваше целевое значение находится в пределах этого диапазона. Если вы находите конечную точку конца конца, ваше значение цели не находится в любом диапазоне.

Алгоритм бинарного поиска примерно (не ожидайте, что это будет выполняться без редактирования)...

while upperbound > lowerbound :
  testpos = lowerbound + ((upperbound-lowerbound) // 2)

  if item [testpos] > goal :
    #  new best-so-far
    upperbound = testpos
  else :
    lowerbound = testpos + 1

Примечание. Оператор деления "//" необходим для целочисленного деления в Python 3. В Python 2 нормальный "/" будет работать, но лучше всего быть готовым к Python 3.

В конце, как верхняя, так и нижняя точка указывают на найденный элемент, но для поиска по верхней границе. Вычитайте один, чтобы получить требуемый результат поиска. Если это дает -1, то не будет соответствующего диапазона.

Вероятно, в библиотеке существует процедура бинарного поиска, которая выполняет поиск по верхней границе, поэтому предпочитайте это, если это так. Чтобы лучше понять, как работает бинарный поиск, см. Как лучше понять бинарный поиск с одним сравнением за итерацию? - нет, я не над попрошайничеством за спинами; -)

Ответ 9

Python имеет функцию диапазона (a, b), которая означает диапазон от (и включая) a, до (но исключая) b. Вы можете составить список этих диапазонов и проверить, есть ли номер в любом из них. Возможно, более эффективно использовать xrange (a, b), который имеет тот же смысл, но фактически не делает список в памяти.

list_of_ranges = []
list_of_ranges.append(xrange(1000, 2430))
list_of_ranges.append(xrange(2545, 2576))
for x in [999, 1000, 2429, 2430, 2544, 2545]:
    result = False
    for r in list_of_ranges:
        if x in r:
            result = True
            break
    print x, result

Ответ 10

Вы действительно сделали тесты? Является ли производительность этого фрагмента кода влияющим на производительность всего приложения? Итак, первый тест!

Но вы также можете использовать dict, например. для хранения всех клавиш диапазонов "М":

mhash = {1000: true, 1001: true,..., 2429: true,...}

if postcode in mhash:
   print 'M'

Конечно: хешам требуется больше памяти, но время доступа - O (1).