Szybkie sprawdzanie zakresów w Pythonie

Question

Mam wiele zakresów w postaci [(1, 1000), (5000, 5678), ... ]. Próbuję znaleźć najszybszy sposób, aby sprawdzić, czy numer znajduje się w którymkolwiek z zakresów. Zakresy składają się z longs i są zbyt duże, aby po prostu zachować set wszystkich liczb.

Najprostszym rozwiązaniem jest to:

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 jest nieco szybciej:

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 

Chociaż istnieje tylko kilkadziesiąt zakresy istnieją miliony kontroli wobec tych zakresach. Jaki jest najszybszy sposób na przeprowadzenie tych kontroli?

(Uwaga: to pytanie jest podobna do Python: efficiently check if integer is within *many* ranges ale nie mają takie same ograniczenia związane z Django i dotyczy wyłącznie prędkości)

Answer 1

Rzeczy spróbować:

1. Wstępnie proces swoich zakresów tak, że są one nie pokrywają, i wyrazić je jako półotwartych odstępach czasu.
2. Użyj modułu bisect, aby wykonać wyszukiwanie. (Nie należy ręcznie przeprowadzać własnego wyszukiwania bisekcji!) Zauważ, że przy wstępnym przetwarzaniu w 1, wszystko, co musisz wiedzieć, to czy wynik połączenia bisect jest równy czy nieparzysty.
3. Jeśli opcja grupowania zapytań jest opcją, należy rozważyć pogrupowanie danych wejściowych w tablicę i użycie numpy.searchsorted.

Niektóre kody i taktowania. Najpierw setup (tutaj używając ipython 2.1 i 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 

taktowanie dla oryginalnego sposobu na moim komputerze (ale z wypowiedzi generatora zamiast listy zrozumieniem):

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 

Teraz przerobić zakresy jako listę punktów granicznych; każdy punkt graniczny na indeksie , nawet jest punktem wejścia do jednego z zakresów, podczas gdy każdy punkt graniczny na indeksie nieparzystym jest punktem wyjścia. Zwróć uwagę na konwersję na półotwarte interwały i umieściłem wszystkie liczby w jednej liście.

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

Dzięki temu łatwo jest używać bisect.bisect aby uzyskać takie same wyniki jak poprzednio, ale raczej szybciej.

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 

Wreszcie, w zależności od kontekstu, może być w stanie skorzystać z funkcji searchsorted od NumPy. Jest to podobne do bisect.bisect, ale działa na cały zbiór wartości naraz.Na przykład:

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

Na pierwszy rzut oka, %timeit wynika z tego są raczej rozczarowujące.

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

Jednak okazuje się, że znaczna część kosztów wykonania jest konwersja wejść do searchsorted z list Pythona do tablic numpy. Załóżmy preconvert obie listy do tablic i spróbuj jeszcze raz:

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 

Znacznie szybciej niż cokolwiek innego do tej pory. To jednak trochę oszukuje: z pewnością możemy wstępnie przetworzyć boundaries, aby zamienić go w tablicę, ale jeśli wartości, które chcesz przetestować, nie są naturalnie produkowane w formie tablicy, to trzeba wziąć pod uwagę koszt konwersji. Z drugiej strony pokazuje, że koszt samego wyszukiwania można zredukować do wystarczająco małej wartości, że nie będzie już dominującym czynnikiem w czasie pracy.

Oto kolejna opcja wzdłuż tych linii. Używa NumPy ponownie, ale robi bezpośrednie, nie leniwe liniowe wyszukiwanie według wartości. (Proszę wybaczyć out-of-order IPython komunikaty: I dodaje ten później :-)

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 

Dla tych konkretnych danych testowych, jest to szybsze niż searchsorted, ale czas będzie rosła liniowo w liczbie. zakresy, podczas gdy dla searchsorted powinien rosnąć zgodnie z rejestrem liczby zakresów. Zauważ, że używa również ilości pamięci proporcjonalnej do len(boundaries) * len(nums). Niekoniecznie jest to problem: jeśli wpadniesz na ograniczenia pamięci, prawdopodobnie możesz podzielić tablice na mniejsze rozmiary (powiedzmy 10000 elementów na raz) bez utraty zbyt dużej wydajności.

Przesunięcie skali, jeśli żaden z nich nie pasuje do rachunku, chciałbym następnie wypróbować Cython i NumPy, pisząc funkcję wyszukiwania (z wejściami zadeklarowanymi jako tablice int), która wykonuje proste wyszukiwanie liniowe w tablicy boundaries. Próbowałem tego, ale nie udało mi się uzyskać lepsze wyniki niż te oparte na bisect.bisect. Dla odniesienia, tutaj jest kod Cython próbowałem; może być w stanie zrobić lepiej:

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 

A czasy:

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

spróbuje użyć binarne wyszukiwania zamiast liniowego. Powinien wydać "Log (n)" w czasie. Zobacz poniżej:

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

Implementacja komentarza @ ArminRigo, który jest dość szybki. Taktowanie wynosi od CPython, nie 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