Индекс ближайших точек между двумя массивами

Question

Учитывая два вектора foo и bar, я хочу вывести вектор длины foo.size(), содержащий индекс, к «ближайшему» элементу бара.Мне не нравится изобретать велосипед - есть ли алгоритмы STL или как-то иначе сделать это кратко?

#include <vector>
#include <cmath>
#include <float.h>

int main() {
    vector<double> foo;
    vector<double> bar;

    // example data setup
    double array_foo[] = {0.0, 1.0, 2.0, 3.0, 4.0,
                          5.0, 6.0, 7.0, 8.0, 9.0};
    double array_bar[] = {4.8, 1.5, 12.0};
    foo.assign(array_foo, array_foo + 10);
    bar.assign(array_bar, array_bar + 3);

    // output array
    vector<int> indices;
    indices.resize(foo.size());

    for(int i = 0; i < foo.size(); i++) {
        double dist = DBL_MAX;
        int idx = 0;
        // find index of closest element in foo
        for(int j = 0; j < bar.size(); j++) {
            if(abs(foo[i] - bar[j]) < dist) {
                dist = abs(foo[i] - bar[j]);
                idx = j;
            }
        }
        indices[i] = idx;
    }
    // expected result: indices = [1,1,1,1,0,0,0,0,0,2]
    return 0;
}

Answer 1

Я вижу 3 разных решения.Все они имеют одинаковую сложность O (N * logN).

1.

Сохранять элементы, если bar в двоичном дереве (std::map).Затем для каждого элемента в foo вам нужно найти до двух ограничивающих элементов и выбрать лучший из них.

Построение дерева - O (N * logN), второй проход - O (N* logN) * ​​1010 *

2.

То же, что и выше, за исключением того, что вместо использования двоичного дерева вы можете использовать отсортированный массив.Создайте массив, каждый элемент которого состоит из элемента bar и его индекса (в качестве альтернативы ваш массив должен содержать указатели на элементы bar).Затем вместо поиска по дереву вы будете выполнять поиск по массиву.

С точки зрения сложности это почти то же самое.Однако практически поиск в отсортированном массиве, вероятно, будет несколько быстрее.

3.

Сортировка foo и bar.(Тем не менее, вам снова нужно будет иметь оригинальный индекс в вашем отсортированном массиве или просто хранить указатели на исходные элементы.

Теперь для каждого элемента в отсортированном foo вам не нужно делатьполный поиск в bar. Вместо этого вы должны только проверить, должны ли вы оставаться в текущей позиции в отсортированном bar или двигаться вперед.

Answer 2

Точного алгоритма не существует, но вы можете реализовать его идиоматическим способом STL, используя std::min_element и пользовательский функтор:

template <typename T>
T norm(const T& a, const T& b)
{
    return abs(b - a);
}

template <typename T>
struct closer_compare
{
    closer_compare(const T& to) : to(to) {}
    bool operator()(const T& a, const T& b) const
    {
        return norm(a, to) < norm(b, to);
    }
    const T& to;
};

template <typename It1, typename It2, typename OutIt>
void find_nearest_indices(It1 in1_begin, It1 in1_end, It2 in2_begin, It2 in2_end, OutIt out)
{
    typedef typename std::iterator_traits<It1>::value_type value;
    for (It1 it = in1_begin; it != in1_end; ++it)
    {
        It2 closest = std::min_element(in2_begin, in2_end, closer_compare<value>(*it));
        *out++ = std::distance(in2_begin, closest);
    }
}

Ваш алгоритм будет заменен на:

find_nearest_indices(foo.begin(), foo.end(), bar.begin(), bar.end(), indices.begin());

Я проверил ваши данные и получил ожидаемые результаты.

Answer 3

Если вы знаете, что массивы отсортированы, или если вам разрешено сортировать массивы, вы можете использовать алгоритмы STL lower_bound или upper_bound, чтобы выполнить двоичный поиск, чтобы найти значение из второго массива в первый. Возвращенный итератор будет указывать на первый элемент, по крайней мере равный (или строго больший, чем в случае upper_bound) вашему элементу, ограничивая количество элементов в первом массиве, которое необходимо проверить, двумя. Это будет выполнено в O (m lg n), где m - количество элементов во втором массиве, а n - число в первом.