Самый быстрый способ найти ближайший элемент в массиве действительных чисел

Question

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

Например:

Исходный массив:

[0.1, 0.7, 0.8, 0.85, 0.9, 1.5, 1.7]

Массив результатов:

[0,   0,   1,   2,    3,   0,   1]

Каковы алгоритмы и подходы для решения этой проблемы?

Важно, чтобы окрестностииз точек выбирается только в отрицательном направлении, что делает невозможным использование Kdtree или Balltree алгоритмов.

Вся моя проблема здесь с моей попыткой кодаэто.

Answer 1

Хотя метод ниже использует простую логику и прост в написании, он медленный.Мы можем ускорить его, используя украшенную Numba функцию.Это ускорит выполнение простых задач зацикливания до скоростей, близких к языку ассемблера.

Установите Numba с pip install numba.

from numba import jit
import numpy as np

# Create a numpy array of length 10000 with float values between 0 and 10
random_values = np.random.uniform(0.0,10.0,size=(100*100,))

@jit(nopython=True, nogil=True)
def find_nearest(input):
  result = []
  for e in input:
    counter = 0
    for j in input:
      if j >= (e-0.5) and j < e:
        counter += 1
    result.append(counter)
  return result

result = find_nearest(random_values)

Обратите внимание, что ожидаемый результат возвращается для теста:

test = [0.1, 0.7, 0.8, 0.85, 0.9, 1.5, 1.7]
result = find_nearest(test)
print result

Возвращает:

[0, 0, 1, 2, 3, 0, 1]

Answer 2

Эту проблему довольно легко решить для упорядоченных массивов.Вы должны просто искать в обратном направлении и считать все числа, которые больше, чем фактический радиус числа.Если это условие больше не выполняется, вы можете выйти из внутреннего цикла (что экономит много времени).

Пример

import numpy as np
from scipy import spatial
import numba as nb

@nb.njit(parallel=True)
def get_counts_2(Points_sorted,ind,r):
  counts=np.zeros(Points_sorted.shape[0],dtype=np.int64)
  for i in nb.prange(0,Points_sorted.shape[0]):
    count=0
    for j in range(i-1,0,-1):
      if (Points_sorted[i]-r<Points_sorted[j]):
        count+=1
      else:
        break
    counts[ind[i]]=count
  return counts

Сроки

r=0.001
Points=np.random.rand(1_000_000)

t1=time.time()
ind=np.argsort(Points)
Points_sorted=Points[ind]
counts=get_counts_2(Points_sorted,ind,r)
print(time.time()-t1)
#0.29s

Answer 3

Это решит вашу конкретную задачу.

def find_nearest_element(original_array):
    result_array = []
    for e in original_array:
        result_array.append(len(original_array[(e-0.5 < original_array) & (e > original_array)]))
    return result_array

original_array = np.array([0.1, 0.7, 0.8, 0.85, 0.9, 1.5, 1.7])
print(find_nearest_element(original_array))

Вывод:

[0, 0, 1, 2, 3, 0, 1]

РЕДАКТИРОВАТЬ: Использование маски значительно быстрее, чем версия с использованием Numba для меньших массивов (ок. Len 10000).Для больших массивов версия использования Numba быстрее.Так что это зависит от того, какой размер массивов вы хотите обработать.

Сравнение во время выполнения (в секундах):

For smaller arrays(size=250):
Using Numba 0.2569999694824219
Using mask 0.0350041389465332
For bigger arrays(size=40000):
Using Numba 1.4619991779327393
Using mask 4.280000686645508

Точка безубыточности на моем устройстве составляет около 10000 (обеоколо 0,33 секунды).