поиск индекса элемента, ближайшего к значению в списке, который не полностью отсортирован

Question

В качестве примера мой список:

[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]

, и я ищу индекс значения, ближайшего к 11.5.Я пробовал другие методы, такие как двоичный поиск и bisect_left, но они не работают.

Я не могу отсортировать этот массив, потому что индекс значения будет использоваться в аналогичном массиве для извлечения значенияпо этому показателю.

Answer 1

Попробуйте следующее:

min(range(len(a)), key=lambda i: abs(a[i]-11.5))

Например:

>>> 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, 11.33447, 10.32184, 9.544922, 8.813385, 8.181152, 6.983734, 6.048035, 5.505096, 4.65799]
>>> min(range(len(a)), key=lambda i: abs(a[i]-11.5))
16

Или получить индекс и значение:

>>> min(enumerate(a), key=lambda x: abs(x[1]-11.5))
(16, 11.33447)

Answer 2

import numpy as np

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, 11.33447, 10.32184, 9.544922, 8.813385, 8.181152, 6.983734, 6.048035, 5.505096, 4.65799]

index = np.argmin(np.abs(np.array(a)-11.5))
a[index] # here is your result

Если a уже является массивом, соответствующее преобразование может быть опущено.

Answer 3

Прохождение всех предметов является только линейным.Если бы вы отсортировали массив, это было бы хуже.

Я не вижу проблемы с сохранением дополнительных deltax (минимальная разница пока что) и idx (индекс этого элемента) и просто циклаодин раз через список.

Answer 4

Если вы не можете отсортировать массив, то нет быстрого способа найти ближайший элемент - вам нужно перебрать все записи.

Обходной путь есть, но это совсем немного работы:Напишите алгоритм сортировки, который сортирует массив и (в то же время) обновляет второй массив, который сообщает вам, где была эта запись до сортировки массива.

Таким образом, вы можете использоватьдвоичный поиск, чтобы найти индекс ближайшей записи, а затем использовать этот индекс для поиска исходного индекса, используя «индексный массив».

[EDIT] Используя zip(), этодовольно просто достичь:

 array_to_sort = zip( original_array, range(len(original_array)) )
 array_to_sort.sort( key=i:i[0] )

Теперь вы можете искать значение в двоичном формате (используя item[0]).item[1] даст вам исходный индекс.

Answer 5

Как насчет: вы архивируете два списка, а затем сортируете результат?

Answer 6

Имейте в виду, что если пространство не имеет значения, вы можете отсортировать любой список, не перемещая его содержимое, создав вторичный список отсортированных индексов.

Также имейте в виду, что если вы делаете этот поиск только один раз, то вам просто нужно пройти через каждый элемент в списке O (n).(Если несколько раз, возможно, вы захотите отсортировать для повышения эффективности позже)

Answer 7

Если вы много раз выполняете поиск в длинном списке, то min очень плохо масштабируется (O (n ^ 2), если вы добавите некоторые из ваших запросов в список поиска, я думаю).

Бисект - твой друг.Вот мое решение.Он масштабируется O (n * log (n)):

class Closest:
    """Assumes *no* redundant entries - all inputs must be unique"""
    def __init__(self, numlist=[], firstdistance=0):
        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 '%i' it is already used" % 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

Используйте это так:

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, 11.33447, 10.32184, 9.544922, 8.813385, 8.181152, 6.983734, 6.048035, 5.505096, 4.65799]
cl = Closest(a)
for x in targets:
    rank = cl.rank(x)
    print("Closest number:", cl.nums[rank])
    print("Closest index:",  cl.numindexes[cl.nums[rank]])