à partir d'une liste d'entiers, obtenir le nombre le plus proche d'une valeur donnée

Étant donné une liste d'entiers, je veux trouver quel nombre est le plus proche d'un nombre que je donne en entrée:

>>> myList = [4, 1, 88, 44, 3]
>>> myNumber = 5
>>> takeClosest(myList, myNumber)
...
4

Existe-t-il un moyen rapide de le faire?

Si nous ne sommes pas sûrs que la liste est triée, nous pourrions utiliser le haut- min()fonction , pour trouver l'élément qui a la distance minimale du nombre spécifié.

>>> min(myList, key=lambda x:abs(x-myNumber))
4

Notez que cela fonctionne également avec les dictionnaires avec des clés int, comme {1: "a", 2: "b"}. Cette méthode prend un temps O (n).

Si la liste est déjà triée, ou si vous pourriez payer le prix du tri du tableau une seule fois, utilisez la méthode de bissection illustrée dans la réponse de @ Lauritz qui ne prend que O (log n) temps (notez cependant que vérifier si une liste est déjà triée est O (n) et le tri est O (n log n).)

Je renommerai la fonction take_closestpour se conformer aux conventions de dénomination PEP8.

Si vous voulez dire rapide à exécuter par opposition à rapide à écrire, cela nemin devrait pas être votre arme de choix, sauf dans un cas d'utilisation très restreint. La minsolution doit examiner chaque nombre de la liste et effectuer un calcul pour chaque nombre. Utiliser à la bisect.bisect_leftplace est presque toujours plus rapide.

Le «presque» vient du fait que bisect_leftla liste doit être triée pour fonctionner. Espérons que votre cas d'utilisation est tel que vous pouvez trier la liste une fois, puis la laisser tranquille. Même si ce n'est pas le cas, tant que vous n'avez pas besoin de trier avant chaque appel take_closest, le bisectmodule sortira probablement en tête. En cas de doute, essayez les deux et regardez la différence dans le monde réel.

from bisect import bisect_left

def take_closest(myList, myNumber):
    """
    Assumes myList is sorted. Returns closest value to myNumber.

    If two numbers are equally close, return the smallest number.
    """
    pos = bisect_left(myList, myNumber)
    if pos == 0:
        return myList[0]
    if pos == len(myList):
        return myList[-1]
    before = myList[pos - 1]
    after = myList[pos]
    if after - myNumber < myNumber - before:
       return after
    else:
       return before

Bisect fonctionne en divisant à plusieurs reprises une liste et en trouvant la moitié myNumberen regardant la valeur moyenne. Cela signifie qu'il a un temps d'exécution de O (log n) par opposition au temps d'exécution O (n) de la réponse votée la plus élevée . Si nous comparons les deux méthodes et fournissons les deux avec un trié myList, voici les résultats:

$ python -m timeit -s "
depuis l'importation la plus proche take_closest
à partir de randint d'importation aléatoire
a = range (-1000, 1000, 10) "" take_closest (a, randint (-1100, 1100)) "

100000 boucles, meilleur de 3: 2,22 usec par boucle

$ python -m timeit -s "
depuis l'importation la plus proche avec_min
à partir de randint d'importation aléatoire
a = range (-1000, 1000, 10) "" with_min (a, randint (-1100, 1100)) "

10000 boucles, meilleur de 3: 43,9 usec par boucle

Donc, dans ce test particulier, bisectc'est presque 20 fois plus rapide. Pour les listes plus longues, la différence sera plus grande.

Et si nous uniformisons les règles du jeu en supprimant la condition préalable qui myListdoit être triée? Disons que nous trions une copie de la liste à chaque take_closest appel, tout en laissant la minsolution inchangée. En utilisant la liste de 200 éléments dans le test ci-dessus, la bisectsolution est toujours la plus rapide, mais seulement d'environ 30%.

C'est un résultat étrange, étant donné que l'étape de tri est O (n log (n)) ! La seule raison de minperdre est que le tri est effectué dans un code C hautement minoptimisé, tout en appelant une fonction lambda pour chaque élément. Au myListfur et à mesure que la taille augmente, la minsolution sera éventuellement plus rapide. Notez que nous avons dû tout mettre en sa faveur pour que la minsolution l'emporte.

>>> takeClosest = lambda num,collection:min(collection,key=lambda x:abs(x-num))
>>> takeClosest(5,[4,1,88,44,3])
4

Un lambda est une manière spéciale d'écrire une fonction "anonyme" (une fonction qui n'a pas de nom). Vous pouvez lui attribuer le nom de votre choix car un lambda est une expression.

La "longue" façon d'écrire ce qui précède serait:

def takeClosest(num,collection):
   return min(collection,key=lambda x:abs(x-num))

def closest(list, Number):
    aux = []
    for valor in list:
        aux.append(abs(Number-valor))

    return aux.index(min(aux))

Ce code vous donnera l'index du nombre le plus proche de Number dans la liste.

La solution donnée par KennyTM est la meilleure dans l'ensemble, mais dans les cas où vous ne pouvez pas l'utiliser (comme brython), cette fonction fera le travail

Parcourez la liste et comparez le nombre actuel le plus proche avec abs(currentNumber - myNumber):

def takeClosest(myList, myNumber):
    closest = myList[0]
    for i in range(1, len(myList)):
        if abs(i - myNumber) < closest:
            closest = i
    return closest

Il est important de noter que l'idée de suggestion de Lauritz d'utiliser la bissectrice ne trouve pas réellement la valeur la plus proche dans MyList de MyNumber. Au lieu de cela, bisect trouve la valeur suivante dans l' ordre après MyNumber dans MyList. Donc, dans le cas d'OP, vous obtiendrez en fait la position 44 retournée au lieu de la position 4.

>>> myList = [1, 3, 4, 44, 88] 
>>> myNumber = 5
>>> pos = (bisect_left(myList, myNumber))
>>> myList[pos]
...
44

Pour obtenir la valeur la plus proche de 5, vous pouvez essayer de convertir la liste en tableau et d'utiliser argmin de numpy comme ça.

>>> import numpy as np
>>> myNumber = 5   
>>> myList = [1, 3, 4, 44, 88] 
>>> myArray = np.array(myList)
>>> pos = (np.abs(myArray-myNumber)).argmin()
>>> myArray[pos]
...
4

Je ne sais pas à quelle vitesse ce serait cependant, je pense que "pas très".

Développant la réponse de Gustavo Lima. La même chose peut être faite sans créer une liste entièrement nouvelle. Les valeurs de la liste peuvent être remplacées par les différentiels au fur et à mesure de la FORprogression de la boucle.

def f_ClosestVal(v_List, v_Number):
"""Takes an unsorted LIST of INTs and RETURNS INDEX of value closest to an INT"""
for _index, i in enumerate(v_List):
    v_List[_index] = abs(v_Number - i)
return v_List.index(min(v_List))

myList = [1, 88, 44, 4, 4, -2, 3]
v_Num = 5
print(f_ClosestVal(myList, v_Num)) ## Gives "3," the index of the first "4" in the list.

Si je peux ajouter à la réponse de @ Lauritz

Afin de ne pas avoir d'erreur d'exécution, n'oubliez pas d'ajouter une condition avant la bisect_leftligne:

if (myNumber > myList[-1] or myNumber < myList[0]):
    return False

donc le code complet ressemblera à:

from bisect import bisect_left

def takeClosest(myList, myNumber):
    """
    Assumes myList is sorted. Returns closest value to myNumber.
    If two numbers are equally close, return the smallest number.
    If number is outside of min or max return False
    """
    if (myNumber > myList[-1] or myNumber < myList[0]):
        return False
    pos = bisect_left(myList, myNumber)
    if pos == 0:
            return myList[0]
    if pos == len(myList):
            return myList[-1]
    before = myList[pos - 1]
    after = myList[pos]
    if after - myNumber < myNumber - before:
       return after
    else:
       return before