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

Question

У меня много диапазонов в форме [(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: efficiently check if integer is within *many* ranges, но не имеют те же Джанго связанных с ограничениями и озабочен исключительно со скоростью)

Answer 1

вещей попробовать:

1. Предварительная обработка ваши диапазоны так, что они не перекрываются, и выразить их в виде полуоткрытых интервалов.
2. Используйте модуль bisect, чтобы выполнить поиск. Обратите внимание, что при предварительной обработке в 1 все, что вам нужно знать, - это то, является ли результат вызова bisect четным или нечетным.
3. Если пакетная обработка запросов является опцией, рассмотрите группировку ваших входов в массив и используя 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 массивы. Давайте preconvert оба списка в массивы и попробовать еще раз:

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 

Answer 2

Попробуйте использовать бинарный поиск вместо линейной. Он должен потратить «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 

Answer 3

Реализация комментария @ 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