wyszukiwanie wartości przed i po na liście posortowanej długo

Question

Jaki byłby najszybszy sposób wyszukiwania liczby (np. 12.31) na liście posortowanej na długo i otrzymanie wartości przed i po mojej wartości "wyszukiwania", gdy dokładna wartość nie znaleziono wartości (np. 11.12 i 12.03 na poniższej liście)?
Wielkie dzięki z góry.

long_list = [10.11, 11.12, 13.03, 14.2 .. 12345.67] 

Answer 1

najszybciej jest prawdopodobnie użyć wbudowane wsparcie w Pythonie. Tutaj myślę o module bisect. Poniżej używam słownika, aby szybko sprawdzić O (1), jeśli wartość jest na liście; jeśli nie, to do znalezienia wartości mniejszych i większych niż wartość poszukiwana jest używana wartość bisect.

#!/usr/bin/env python 

import bisect 

def find_lt(a, x): 
    'Find rightmost value less than x' 
    i = bisect.bisect_left(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError 

def find_gt(a, x): 
    'Find leftmost value greater than x' 
    i = bisect.bisect_right(a, x) 
    if i != len(a): 
     return a[i] 
    raise ValueError 

# First create a test-list (49996 items) 
i=1.0 
R=[1.0] 
D={} 
while i < 10000: 
    i+=0.2 
    i=round(i,2) 
    D[i]=True 
    R.append(i) 

# Locate a value, in this case 100.3 which is not in the list 
x=100.3 
if D.has_key(x): 
    print "found", x 
else: 
    print find_lt(R, x) 
    print find_gt(R, x) 

Wyjście x=100.3:

100.2 
100.4 

Answer 2

Jeśli twoja lista jest posortowana tak, jak w twoim przykładzie, przypuszczam, że wyszukiwanie binarne byłoby najszybsze.

Answer 3

Wyszukiwanie eksponencjalne (wyszukiwanie w galaktyce AKA) działałoby lepiej niż zwykłe wyszukiwanie binarne, jeśli lista jest bardzo długa. Chodzi o to, aby przesuwać się do przodu z pozycji 0 na coraz większej liczbie kroków, aż do momentu, w którym odpowiedź zostanie przekazana w tym momencie, można przeprowadzić wyszukiwanie binarne do zakresu utworzonego przez dwa ostatnie etapy. Jeśli element nie zostanie znaleziony, ostatnia próba wskaże najbliższe elementy.

Spójrz na Basic Techniques for information retrieval. Dostarczony jest algorytm pseudokodułu i omawiają jego złożoność względem wyszukiwania binarnego.

Answer 4

li = [10.11, 11.12, 13.03, 14.2, 15.6, 15.8, 17.9, 12345.67] 

def searsh(x,li): 
    itli = iter(li) 
    a = itli.next() 
    if a==x: 
     return a 
    else: 
     while True: 
      b = itli.next() 
      if b==x: 
       return b 
      elif a<x<b: 
       return (a,b) 
      a = itli.next() 
      if a==x: 
       return a 
      elif b<x<a: 
       return (b,a) 


print searsh(13.5,li) 
print searsh(10.11,li) 
print searsh(50.3,li) 
print searsh(12345.67,li) 

wynik

(13.03, 14.2) 
10.11 
(17.9, 12345.67) 
12345.67 

również:

def searsh(x,li): 
    a = li[0] 
    if a==x: 
     return a 
    else: 
     j = 0 
     while True: 
      j += 1 
      b = li[j] 
      if b==x: 
       return b 
      elif a<x<b: 
       return (a,b) 
      j += 1 
      a = li[j] 
      if a==x: 
       return a 
      elif b<x<a: 
       return (b,a)