Trouver l'indice d'un élément le plus proche de la valeur dans une liste qui n'est pas entièrement triée

Question

A titre d'exemple, ma liste est la suivante :

[25.75443, 26.7803, 25.79099, 24.17642, 24.3526, 22.79056, 20.84866,
 19.49222, 18.38086, 18.0358, 16.57819, 15.71255, 14.79059, 13.64154,
 13.09409, 12.18347, 11.33447, 10.32184, 9.544922, 8.813385, 8.181152,
 6.983734, 6.048035, 5.505096, 4.65799]

et je cherche l'indice de la valeur la plus proche de 11.5 . J'ai essayé d'autres méthodes, telles que la recherche binaire et la recherche d'informations. bisect_left mais ils ne fonctionnent pas.

Je ne peux pas trier ce tableau, car l'index de la valeur sera utilisé sur un tableau similaire pour récupérer la valeur à cet index.

Answer 1

N'oubliez pas que si l'espace n'est pas important, vous pouvez trier n'importe quelle liste sans déplacer son contenu en créant une liste secondaire des indices triés.

Gardez également à l'esprit que si vous effectuez cette recherche une seule fois, il vous suffira de parcourir chaque élément de la liste en O(n). (Si vous le faites plusieurs fois, vous voudrez probablement effectuer un tri pour augmenter l'efficacité par la suite).

Answer 2

Si vous recherchez une longue liste plusieurs fois, alors min balance très mauvaise (O(n^2), si vous ajoutez certaines de vos recherches à la liste de recherche, je pense).

Bisect est votre ami. Voici ma solution. Elle s'échelonne sur O(n*log(n)) :

class Closest:
    """Assumes *no* redundant entries - all inputs must be unique"""
    def __init__(self, numlist=None, firstdistance=0):
        if numlist == None:
            numlist=[]
        self.numindexes = dict((val, n) for n, val in enumerate(numlist))
        self.nums = sorted(self.numindexes)
        self.firstdistance = firstdistance

    def append(self, num):
        if num in self.numindexes:
            raise ValueError("Cannot append '%s' it is already used" % str(num))
        self.numindexes[num] = len(self.nums)
        bisect.insort(self.nums, num)

    def rank(self, target):
        rank = bisect.bisect(self.nums, target)
        if rank == 0:
            pass
        elif len(self.nums) == rank:
            rank -= 1
        else:
            dist1 = target - self.nums[rank - 1]
            dist2 = self.nums[rank] - target
            if dist1 < dist2:
                rank -= 1
        return rank

    def closest(self, target):
        try:
            return self.numindexes[self.nums[self.rank(target)]]
        except IndexError:
            return 0

    def distance(self, target):
        rank = self.rank(target)
        try:
            dist = abs(self.nums[rank] - target)
        except IndexError:
            dist = self.firstdistance
        return dist

Utilisez-le comme ça :

a = [25.75443, 26.7803, 25.79099, 24.17642, 24.3526, 22.79056, 20.84866,
     19.49222, 18.38086, 18.0358, 16.57819, 15.71255, 14.79059, 13.64154,
     13.09409, 12.18347, 1.33447, 10.32184, 9.544922, 8.813385, 8.181152,
     6.983734, 6.048035, 5.505096, 4.65799]
targets = [1.0, 100.0, 15.0, 15.6, 8.0]
cl = Closest(a)
for x in targets:
    rank = cl.rank(x)
    print("Closest to %5.1f : rank=%2i num=%8.5f index=%2i " % (x, rank,
        cl.nums[rank], cl.closest(x)))

La sortie est prévue :

Closest to   1.0 : rank= 0 num= 1.33447 index=16
Closest to 100.0 : rank=25 num=26.78030 index= 1
Closest to  15.0 : rank=12 num=14.79059 index=12
Closest to  15.6 : rank=13 num=15.71255 index=11
Closest to   8.0 : rank= 5 num= 8.18115 index=20

Et :

cl.append(99.9)
x = 100.0
rank = cl.rank(x)
print("Closest to %5.1f : rank=%2i num=%8.5f index=%2i " % (x, rank,
    cl.nums[rank], cl.closest(x)))

Sortie :

Closest to 100.0 : rank=25 num=99.90000 index=25