7
\$\begingroup\$

I am trying to write an algorithm that can find user-specified nearest neighbors. By user-specified, I mean that the user can specify whether it's a general nearest neighbor, a forward-nearest neighbor, or a backward-nearest neighbor.

The idea for this code was inspired from this SO post. While it isn't ideal to search the entire array (perhaps use searchsorted as an alternative), I want to find all occurrences of the user-specified nearest value in the given data array. While there are other techniques that can be used to achieve the same goal (such as using the cumulative sum of differences of argsorted values), I feel the code below is easier to read/understand and is likely quicker since it performs less operations that require traversing the entire data array. That said, I would like to know if there are better approaches (in terms of speed) to achieve the same output, as this code will be applied to a dataset of at least ~70,000 data points. More than the value itself, I am concerned with the indices at which the values occur.

import numpy as np

Sample Data

sample = np.array([300, 800, 200, 500, 600, 750, 700, 450, 400, 550, 350, 900])
# sample = np.array([300, 800, 200, 500, 600, 750, 700, 450, 400, 550, 350, 900] * 2)

Main algorithm

def search_nearest(data, search_value, direction=None):
    """ 
    This function can find the nearest, forward-nearest, or 
    backward-nearest value in data relative to the given search value.
    """

    if not isinstance(data, np.ndarray):
        data = np.array(data)

    print("\n>>     DATA\n{}\n".format(data))
    print(">>     SEARCH VALUE\n{}\n".format(search_value))

    if direction is None:
        delta = np.abs(data - search_value)
        res = np.where(delta == np.min(delta))[0]

    elif direction == 'forward':
        delta = data - search_value
        try:
            res = np.where(delta == np.min(delta[delta >= 0]))[0]
        except:
            raise ValueError("no forward nearest match exists")

    elif direction == 'backward':
        delta = search_value - data
        try:
            res = np.where(delta == np.min(delta[delta >= 0]))[0]
        except:
            raise ValueError("no backward nearest match exists")

    print(" .. INDEX OF NEAREST NUMBER\n{}\n".format(res))
    print(" .. NUMBER AT THAT INDEX\n{}\n".format(data[res]))
    print("--------------------")

Call the main function

# crd = None
crd = 'forward'
# crd = 'backward'

for val in (799, 301, 800, 250, 8, 901):
    search_nearest(sample, search_value=val, direction=crd)
\$\endgroup\$
0

2 Answers 2

Reset to default
3
\$\begingroup\$

code

Some of your program is copy-n-pasted code; there is an opportunity to refactor.

Your docstring offers little guidance on valid direction values. Consider using enum.Enum. If None becomes 0, then 1 and -1 could represent the directions, with delta multiplied by the sign, killing two cases with one stone.

The identifier res for result is pretty OK, but consider using an abbreviation like idx for index, clarifying that it is not the "value" that the docstring said would be computed. Better yet, turn it into a function that is documented to return an index, and push the print statements into a calling function.

crd = 'forward'

I'm willing to believe that "d" denotes "direction", but the "cr" part of that identifier is obscure.

algorithm

if there are better approaches (in terms of speed) to achieve the same output

Your main function suggests that you will repeatedly interrogate a large (70k) sample with diverse search values. In which case your data structure is not well suited to your task.

You are forcing pandas to read all N values on each query. Don't do that.

Build a two-column copy of the input that stores (index, value). Sort it by value. So far the cost is N log N.

Now for each query, binary search for search_value to land on result_index, at cost of log N. The desired answer is at result_index, or the entry before it, or the entry after it. Then use the stored index to report the corresponding index in the original input data.

\$\endgroup\$
2
\$\begingroup\$

In addition to the recommendations by @J_H, you can simplify the function somewhat. Since I only want the indexes, my function returns the index number, or -1 if there is no nearest value in a given direction.

# Find nearest number in array and return index
def find_nearest(array, number, direction=None):
    idx = -1
    if array.empty:
        return idx
    if direction is None:
        idx = (np.abs(array - number)).idxmin()
    elif direction == 'backward':
        _delta = number - array
        _delta_positive = _delta[_delta > 0]
        if not _delta_positive.empty:
            idx = _delta_positive.idxmin()
    elif direction == 'forward':
        _delta = array - number
        _delta_positive = _delta[_delta > 0]
        if not _delta_positive.empty:
            idx = _delta_positive.idxmin()
    return idx
\$\endgroup\$

You must log in to answer this question.