Быстрая проверка диапазонов в Python

У меня много диапазонов в форме [(1, 1000), (5000, 5678), ... ]. Я пытаюсь выяснить самый быстрый способ проверить, находится ли число в пределах любого диапазона. Диапазоны состоят из longs и слишком велики, чтобы просто сохранить set всех чисел.

Простейшим решением является следующее:

ranges = [(1,5), (10,20), (40,50)]  # The real code has a few dozen ranges
nums = range(1000000)  
%timeit [n for n in nums if any([r[0] <= n <= r[1] for r in ranges])]
# 1 loops, best of 3: 5.31 s per loop

Banyan немного быстрее:

import banyan
banyan_ranges = banyan.SortedSet(updator=banyan.OverlappingIntervalsUpdator)
for r in ranges:
    banyan_ranges.add(r)
%timeit [n for n in nums if len(banyan_ranges.overlap_point(n))>0]
# 1 loops, best of 3: 452 ms per loop

Хотя есть только несколько десятков диапазонов, есть миллионы проверок против этих диапазонов. Какой самый быстрый способ выполнить эти проверки?

(Примечание. Этот вопрос похож на Python: эффективно проверяет, является ли целое число внутри * многих * диапазонов, но не имеет одинаковых ограничений, связанных с Django, и является исключительным связанные со скоростью)

Ответ 1

Что нужно попробовать:

Предварительно обработайте диапазоны, чтобы они не перекрывались, и выражали их как полуоткрытые интервалы.
Используйте bisect для выполнения поиска. Обратите внимание, что при предварительной обработке в 1 все, что вам нужно знать, - это то, является ли результат вызова bisect четным или нечетным.
Если пакетная обработка запросов является опцией, рассмотрите группировку ваших входов в массив и используя numpy.searchsorted.

Некоторые коды и тайминги. Сначала настройте (здесь используйте IPython 2.1 и Python 3.4):

In [1]: ranges = [(1, 5), (10, 20), (40, 50)]

In [2]: nums = list(range(1000000))  # force a list to remove generator overhead

Сроки для исходного метода на моей машине (но с выражением генератора вместо понимания списка):

In [3]: %timeit [n for n in nums if any(r[0] <= n <= r[1] for r in ranges)]
1 loops, best of 3: 922 ms per loop

Теперь мы перерабатываем диапазоны как список граничных точек; каждая граничная точка с четным индексом является точкой входа в один из диапазонов, а каждая граничная точка с нечетным индексом является точкой выхода. Обратите внимание на преобразование в полуоткрытые интервалы и что я поместил все числа в один список.

In [4]: boundaries = [1, 6, 10, 21, 40, 51]

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

In [5]: from bisect import bisect

In [6]: %timeit [n for n in nums if bisect(boundaries, n) % 2]
1 loops, best of 3: 298 ms per loop

Наконец, в зависимости от контекста вы можете использовать функцию searchsorted из NumPy. Это похоже на bisect.bisect, но работает сразу с целыми наборами значений. Например:

In [7]: import numpy

In [8]: numpy.where(numpy.searchsorted(boundaries, nums, side="right") % 2)[0]
Out[8]: 
array([ 1,  2,  3,  4,  5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 40,
       41, 42, 43, 44, 45, 46, 47, 48, 49, 50])

На первый взгляд, результаты %timeit весьма разочаровывают.

In [9]: %timeit numpy.where(numpy.searchsorted(boundaries, nums, side="right") % 2)[0]
10 loops, best of 3: 159 ms per loop

Однако оказывается, что большая часть затрат на производительность заключается в преобразовании входов в searchsorted из списков Python в массивы NumPy. Пусть предварительно преобразует оба списка в массивы и повторите попытку:

In [10]: boundaries = numpy.array(boundaries)

In [11]: nums = numpy.array(nums)

In [12]: %timeit numpy.where(numpy.searchsorted(boundaries, nums, side="right") % 2)[0]
10 loops, best of 3: 24.6 ms per loop

Гораздо быстрее, чем что-либо еще. Однако это немного изменяет: мы можем, конечно, препроцессить boundaries, чтобы превратить его в массив, но если значения, которые вы хотите протестировать, естественно не создаются в форме массива, тогда необходимо будет учитывать стоимость конверсии, С другой стороны, это показывает, что стоимость самого поиска может быть уменьшена до достаточно малого значения, которое больше не будет доминирующим фактором в течение времени выполнения.

Вот еще один вариант в этих строках. Он снова использует NumPy, но делает прямой нелинейный линейный поиск за значение. (Пожалуйста, простите приглашения IPython не по порядку: я добавил это позже.: -)

In [29]: numpy.where(numpy.logical_xor.reduce(numpy.greater_equal.outer(boundaries, nums), axis=0))
Out[29]: 
(array([ 2,  3,  4,  5,  6, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 41,
        42, 43, 44, 45, 46, 47, 48, 49, 50, 51]),)

In [30]: %timeit numpy.where(numpy.logical_xor.reduce(numpy.greater_equal.outer(boundaries, nums), axis=0))
10 loops, best of 3: 16.7 ms per loop

Для этих конкретных тестовых данных это быстрее, чем searchsorted, но время будет расти линейно в количестве диапазонов, тогда как для searchsorted оно должно расти в соответствии с журналом количества диапазонов. Обратите внимание, что он также использует объем памяти, пропорциональный len(boundaries) * len(nums). Это не обязательно проблема: если вы обнаруживаете, что сталкиваетесь с ограничениями памяти, вы, вероятно, можете объединить массивы в меньшие размеры (например, 10000 элементов за раз), не теряя при этом слишком большой производительности.

Перемещение масштаба, если ни один из них не соответствует купюре, я бы попробовал Cython и NumPy, записывая функцию поиска (с входами, объявленными как массивы int), которые выполняют простой линейный поиск в массиве boundaries. Я попробовал это, но не смог получить результаты лучше, чем те, которые основаны на bisect.bisect. Для справки, здесь код Cython, который я пробовал; вы можете сделать лучше:

cimport cython

cimport numpy as np

@cython.boundscheck(False)
@cython.wraparound(False)
def search(np.ndarray[long, ndim=1] boundaries, long val):
    cdef long j, k, n=len(boundaries)
    for j in range(n):
        if boundaries[j] > val:
           return j & 1
    return 0

И тайминги:

In [13]: from my_cython_extension import search

In [14]: %timeit [n for n in nums if search(boundaries, n)]
1 loops, best of 3: 793 ms per loop

Ответ 2

Реализация комментария @ArminRigo, которая довольно быстро. Время от CPython, а не PyPy:

exec_code = "def in_range(x):\n"
first_if = True
for r in ranges:
   if first_if:
      exec_code += "    if "
      first_if = False
   else:
      exec_code += "    elif "
   exec_code += "%d <= x <= %d: return True\n" % (r[0], r[1])
exec_code += "    return False"
exec(exec_code)

%timeit [n for n in nums if in_range(n)]
# 10 loops, best of 3: 173 ms per loop

Ответ 3

Попробуйте использовать бинарный поиск вместо линейного. Он должен потратить "Log (n)" во времени. См. Ниже:

list = []
for num in nums:
    start = 0
    end = len(ranges)-1
    if ranges[start][0] <= num <= ranges[start][1]:
        list.append(num)
    elif ranges[end][0] <= num <= ranges[end][1]:
        list.append(num):
    else:
        while end-start>1:
            mid = int(end+start/2)
            if ranges[mid][0] <= num <= ranges[mid][1]:
                list.append(num)
                break
            elif num < ranges[mid][0]:
                end = mid
            else:
                start = mid