Une façon élégante de trouver la valeur la plus proche dans une liste ordonnée circulaire

Question

donné une classés liste comme [1.1, 2.2, 3.3] et une valeur de sélection tel que math.pi*2, retourner la valeur la plus proche pour toute valeur donnée de [0 - math.pi*2)

la fonction doit retourne l'index de la valeur, de sorte que les rendements f(1.2)0 en f(2.1) retours 1 et f(6.0) devrait envelopper autour de math.pi*2 et retour 0, étant plus proche de 1,1 que de 3,3 étant donné la valeur de sélection. Juste pour être entièrement explicite, cette fonction devrait également être appliquée à l'extrémité inférieure, de sorte que f(1.0, [5.0, 6.0], bound = math.pi*2) renvoie 1.

Le cas d'utilisation est de mapper un angle arbitraire en radians à l'angle valide existant le plus proche dans la liste. J'ai écrit ce genre de fonction quelques fois en python avec bisect, mais le code finit toujours par offenser mes sens esthétiques. La complexité élevée et le nombre de cas de bords semblent hors de proportion avec la simplicité intuitive de la fonction. Donc, je demande si quelqu'un peut trouver une mise en œuvre agréable, à la fois en termes d'efficacité et d'élégance.

Answer 1

Utilisez le bisect module comme base:

from bisect import bisect_left 
import math 

def f(value, sorted_list, bound=math.pi * 2): 
    value %= bound 
    index = bisect_left(sorted_list, value) 
    if index == 0 or index == len(sorted_list): 
     return min((abs(bound + sorted_list[0] - value), 0), (abs(sorted_list[-1] - value), len(sorted_list) - 1))[1] 
    return min((index - 1, index), 
     key=lambda i: abs(sorted_list[i] - value) if i >= 0 else float('inf')) 

Démo:

>>> sorted_list = [1.1, 2.2, 3.3] 
>>> f(1.2, sorted_list) 
0 
>>> f(2.1, sorted_list) 
1 
>>> f(6.0, sorted_list) 
0 
>>> f(5.0, sorted_list) 
2 

Answer 2

La façon la plus simple serait juste utiliser min:

def angular_distance(theta_1, theta_2, mod=2*math.pi): 
    difference = abs(theta_1 % mod - theta_2 % mod) 
    return min(difference, mod - difference) 

def nearest_angle(L, theta): 
    return min(L, key=lambda theta_1: angular_distance(theta, theta_2)) 

In [11]: min(L, key=lambda theta: angular_distance(theta, 1)) 
Out[11]: 1.1 

Faisant usage de la sorted- Dans la liste, vous pouvez utiliser le module bisect:

from bisect import bisect_left 

def nearest_angle_b(theta, sorted_list, mod=2*math.pi): 
    i1 = bisect_left(sorted_list, theta % mod) 
    if i1 == 0: 
     i1, i2 = len(sorted_list) - 1, 0 
    elif i1 == len(sorted_list): 
     i1, i2 = i1 - 1, 0 
    else: 
     i2 = (i1 + 1) % len(sorted_list) 
    return min((angular_distance(theta, L[i], mod), i, L[i]) 
       for i in [i1, i2]) 

Renvoie la distance, l'index et l'angle de la liste à laquelle elle est la plus proche.

Answer 3

Voici une approche plus élégante. Éliminer les cas de pointe en enveloppant la ligne de nombre autour de:

from bisect import bisect_right 

def circular_search(points, bound, value): 
    ## 
    ## normalize/sort input points to [0, bound) 
    points = sorted(list(set([i % bound for i in points]))) 
    ## 
    ## normalize search value to [0, bound) 
    value %= bound 
    ## 
    ## wrap the circle left and right 
    ext_points = [i-bound for i in points] + points + [i+bound for i in points] 
    ## 
    ## identify the "nearest not less than" point; no 
    ## edge cases since points always exist above & below 
    index = bisect_right(ext_points, value) 
    ## 
    ## choose the nearest point; will always be either the 
    ## index found by bisection, or the next-lower index 
    if abs(ext_points[index]-value) >= abs(ext_points[index-1]-value): 
     index -= 1 
    ## 
    ## map index to [0, npoints) 
    index %= len(points) 
    ## 
    ## done 
    return points[index] 

Comme écrit, fonctionne à moins que les entrées sont bancal comme pas de points, ou liés == 0.