Эффективный питонический способ привязать значение к некоторой сетке

Question

У меня есть одномерная сетка, которая определяется как список отсортированных значений с плавающей запятой. Точки не равноудалены, но гарантируется, что пары конфликтующих точек нет (расстояние == 0).

Мне нужно найти наиболее эффективный способ привязки любого заданного значения к ближайшей точке сетки. Самый умный способ, которым я мог придумать, заключался в следующем (np - это numpy, а myGrid - это numpy array)

absDiff = np.abs(myGrid - myValue)
ix = np.argmax(absDiff)
snappedValue = myGrid[ix]

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

Answer 1

Я написал функцию для массивов numpy:

def ndsnap(points, grid):
    """
    Snap an 2D-array of points to values along an 2D-array grid.
    Each point will be snapped to the grid value with the smallest
    city-block distance.

    Parameters
    ---------
    points: 2D-array. Must have same number of columns as grid
    grid: 2D-array. Must have same number of columns as points

    Returns
    -------
    A 2D-array with one row per row of points. Each i-th row will
    correspond to row of grid to which the i-th row of points is closest.
    In case of ties, it will be snapped to the row of grid with the
    smaller index.
    """
    grid_3d = np.transpose(grid[:,:,np.newaxis], [2,1,0])
    diffs = np.sum(np.abs(grid_3d - points[:,:,np.newaxis]), axis=1)
    best = np.argmin(diffs, axis=1)
    return grid[best,:]

Answer 2

import bisect
def snap(myGrid, myValue):
    ix = bisect.bisect_right(myGrid, myValue)
    if ix == 0:
        return myGrid[0]
    elif ix == len(myGrid):
        return myGrid[-1]
    else:
        return min(myGrid[ix - 1], myGrid[ix], key=lambda gridValue: abs(gridValue - myValue))

Answer 3

Подробнее о ответе Нолана Конавея:

Поскольку метрика Манхэттена используется в любом случае для полных прямоугольных сеток, следующее будет быстрее, если сетка станет достаточно большой:

def ndsnap_regular(points, *grid_axes):         
     snapped = []                                         
     for i, ax in enumerate(grid_axes):                                   
         diff = ax[:, np.newaxis] - points[:, i]
         best = np.argmin(np.abs(diff), axis=0)                                                                                                  
         snapped.append(ax[best])                                                                                           
     return np.array(snapped).T

Здесь grid_axes просто содержит кортеж координат оси, который будет использоваться такими функциями, как numpy.meshgrid для создания сетки из.

например. для привязки 100 трехмерных точек к сетке 50x50x50:

>>> n_points = 100
>>> points = np.random.random((n_points, 3))
>>> grid = (np.linspace(0, 1), np.linspace(0, 1), np.linspace(0, 1))
>>> grid_expanded = cartesian_product(*grid)
>>> len(grid_expanded)
125000
>>> %timeit ndsnap(points, grid_expanded)
418 ms ± 3.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit ndsnap_regular(points, *grid)
86.5 µs ± 922 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> (ndsnap(points, grid_expanded) == ndsnap_regular(points, *grid)).all()
True

Answer 4

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

Теперь все, что осталось, - это правильно обрабатывать граничные случаи: когда точки падают до первого / после последнего и когда точка достигает существующей точки сетки.