Czy istnieje sposób na uniknięcie wyszukiwania liniowego?

Question

Mam dużą pulę obiektów z numerem początkowym i końcowym. Na przykład:

(999, 2333, data) 
(0, 128, data) 
(235, 865, data) 
... 

Zakładając, że odstępy nie zachodzą na siebie. Piszę funkcję, która pobiera liczbę i znajduje obiekt, który zawiera (niski, wysoki). Powiedzmy, biorąc pod uwagę 333, chcę 3. obiektów na liście.

Czy jest jakikolwiek sposób, aby zrobić to tak skutecznie, jak to możliwe, bez wyszukiwania liniowego? Myślałem o wyszukiwaniu binarnym, ale z pewnymi trudnościami w radzeniu sobie z kontrolą zasięgu.

Answer 1

Po pierwsze, nie jest wcale jasne, że gwarancja binarna jest tu gwarantowana . Możliwe, że wyszukiwanie liniowe jest szybsze, gdy liczba interwałów jest mała.

Jeżeli obawiasz się o wydajność, rozważne rzeczą do zrobienia jest do profilowania kodu, a może obie metody porównawcze na typowy wejść.

Zastrzeżenia bok, przeszukiwanie binarne mogą być realizowane przez sortowanie interwały raz, a potem wielokrotnie za pomocą modułu bisect zrobić wyszukiwania:

import bisect 

intervals = [(999, 2333, 'int1'), (0, 128, 'int2'), (235, 865, 'int3')] 
intervals.sort() 

def find_int(intervals, val): 
    pos = bisect.bisect_left([interval[1] for interval in intervals], val) 
    if pos < len(intervals) and val >= intervals[pos][0]: 
     return intervals[pos] 
    else: 
     return None 

print(find_int(intervals, 0)) 
print(find_int(intervals, 1)) 
print(find_int(intervals, 200)) 
print(find_int(intervals, 998)) 
print(find_int(intervals, 999)) 
print(find_int(intervals, 1000)) 
print(find_int(intervals, 2333)) 
print(find_int(intervals, 2334)) 

W powyższym sądzę, że przedziały są bez nakładania , a interwał obejmuje zarówno punkt początkowy, jak i końcowy.

Wreszcie, aby zwiększyć wydajność, można by rozważyć faktoring [interval[1] for interval in intervals] z funkcji i robi to tylko raz na początku.

Answer 2

Pomyśl, czy warto posortować dane.
Jeśli chcesz przeszukać tylko kilka razy, to nie - i nie można uniknąć wyszukiwania liniowego. całkowita złożoność wyszukiwań będzie O(n*k), gdzie n jest liczba elementów i k jest liczba wyszukiwań.

Jeśli chcesz wyszukać wiele razy, to należy najpierw posortować, a następnie wyszukiwać za pomocą wyszukiwania binarnego. Będzie to O(nlogn) do sortowania i O(klogn) do wyszukiwania k razy, więc otrzymasz w sumie O((n+k)logn).

Zatem, sortowania, a następnie poszukiwań powinny być wykonywane tylko wtedy, gdy k>=logn

PS: Możesz użyć innego podejścia do sortowania i wyszukiwania, jak proponowano w innych odpowiedziach, pod każdym względem, konkluzja pozostaje: zrób to tylko, jeśli k>=logn

Answer 3

można użyć modułu przepoławiać: http://docs.python.org/library/bisect.html

trzeba sortować dane raz, a następnie użyć Przepoławiana:

import bisect 
data=None 
tuples=[(0, 128, None), (235, 865, None), (999, 2333, None)] 
tuples.sort() 
print tuples 
print bisect.bisect(tuples, (-1,)) # 0 
print bisect.bisect(tuples, (1,)) # 1 
print bisect.bisect(tuples, (333,)) # 2 
print bisect.bisect(tuples, (3333,)) # 3 

Answer 4

Jeśli szybkość wyszukiwania jest sprawą najwyższej wagi, a następnie można utworzyć patrzenia do góry (jak już skomentował S.Lott).Pozwoli to wziąć O (R) pamięci (gdzie R ma wielkość w zakresie) O (R) Czas wstępnego przetwarzania i O (1) Czas wyszukiwania. Utwórz tablicę rozmiaru zakresu i zapełnij każdy element wskaźnikiem danych lub wartością pustą.

lookup = {} 
for low, high, data in source_ranges: 
    for i in range(low,high): # or maybe high+1 if the ranges are inclusive 
     lookup[i] = data 

Teraz wyszukiwanie jest banalne.