à partir de la liste des entiers, obtenir le numéro le plus proche d'une valeur donnée

Question

É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
 

Y at-il un moyen rapide de faire cela?

Answer 1

Nous pourrions utiliser la fonction intégrée min() pour trouver l'élément qui possède la distance minimale par rapport au nombre spécifié.

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

Notez que cela fonctionne aussi avec les dict avec les touches int, comme {1: "a", 2: "b"}

Answer 2

Si vous voulez dire rapide à exécuter plutôt rapide à écrire, min doit pas être l'arme de votre choix, sauf dans un très étroit cas d'utilisation. L' min solution doit examiner chaque numéro dans la liste et faire un calcul pour chaque numéro. À l'aide de bisect.bisect_left , au contraire, est presque toujours plus rapide.

Le "presque" vient du fait qu' bisect_left exige que la liste soit triée pour le travail. J'espère que votre cas d'utilisation est telle que vous pouvez trier la liste en une seule fois et ensuite le laisser seul. Même si, comme longtemps que vous n'avez pas besoin de les trier avant chaque fois que vous appelez takeClosest, bisect module sera probablement sortir sur le dessus. Si vous êtes dans le doute, essayez les deux et regarder le monde réel différence.

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.
    """
    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

Traversent les œuvres à plusieurs reprises par la réduction de moitié de la liste et de savoir quelles demi - myNumber doit être en regardant la valeur du milieu. Cela signifie qu'il a un temps d'exécution de O(log n) par opposition à l' O(n) temps d'exécution de la plus haute voté réponse. Si nous comparons les deux méthodes et de l'approvisionnement à la fois avec une triés myList, ce sont les résultats:

$ python -m timeit -s "
à partir de la plus proche à l'importation takeClosest
de random import randint
un = range(-1000, 1000, 10)" "takeClosest(a, randint(-1100, 1100))"

100000 boucles, best of 3: 2.22 usec par boucle

$ python -m timeit -s "
à partir de la plus proche à l'importation with_min
de random import randint
un = range(-1000, 1000, 10)" "with_min(a, randint(-1100, 1100))"

10000 boucles, best of 3: 43.9 usec par boucle

Donc dans ce test en particulier, bisect est près de 20 fois plus rapide. Pour plus de listes, la différence sera plus grande.

Que faire si nous avons niveau du terrain de jeu, en supprimant la condition qu' myList doivent être triés? Disons que nous avons en quelque sorte une copie de la liste à chaque fois takeClosest est appelé, tout en laissant l' min solution inchangée. À l'aide de l'200 éléments de la liste dans le test ci-dessus, l' bisect solution est toujours le plus rapide, mais seulement d'environ 30%.

C'est un résultat étrange, considérant que le tri étape est O(n log(n))! La seule raison min est encore en train de perdre, c'est que le tri est fait dans de très optimalized le code en c, tout en min a travaillé le long de l'appel d'une fonction lambda pour chaque élément. En tant que myList augmente la taille de l' min solution finira par être plus rapide. Notez que nous avons eu de la pile tout en sa faveur pour l' min solution pour gagner.

Answer 3

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

Answer 4

 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 Nombre dans la liste.

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

Answer 5

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