Шаблон выражения для вычисления евклидова расстояния

Я снова писал код, связанный с геометрией, и более подробно рассмотрел мою функцию, предназначенную для вычисления евклидова расстояния между двумя точками (N-мерные точки, кстати, следовательно, N). Вот упрощенная версия:

template<std::size_t N, typename T>
auto distance(const Point<N, T>& lhs, const Point<N, T>& rhs)
    -> T
{
    T res{};
    for (std::size_t i = 0 ; i < N ; ++i)
    {
        auto tmp = std::abs(lhs[i] - rhs[i]);
        res += tmp * tmp;
    }
    return std::sqrt(res);
}

До сих пор так хорошо. Тем не менее, одна очень распространенная операция - сравнить расстояния. Вообще говоря, при сравнении расстояний оптимизируется sqrt, а сумма квадратов сравнивается вместо самого расстояния. Поэтому я попытался создать какой-то шаблон выражения для представления расстояния между двумя точками, так что пользователи получат выгоду от простоты использования и «избавятся от sqrt optimization "при сравнении расстояний. В принципе, вызов sqrt не выполняется, пока не потребуется точное значение расстояния. Вот класс:

template<typename T>
struct DistanceExpression
{
    explicit constexpr DistanceExpression(T data):
        _data(data)
    {}

    operator T() const
    {
        return std::sqrt(_data);
    }

    bool operator==(const DistanceExpression& other) const
    {
        return _data == other._data;
    }

    bool operator!=(const DistanceExpression& other) const
    {
        return !(*this == other);
    }

private:

    T _data;
};

Моя новая функция distance реализована как таковая:

template<std::size_t N, typename T>
auto distance(const Point<N, T>& lhs, const Point<N, T>& rhs)
    -> DistanceExpression<T>
{
    T res{};
    for (std::size_t i = 0 ; i < N ; ++i)
    {
        auto tmp = std::abs(lhs[i] - rhs[i]);
        res += tmp * tmp;
    }
    return DistanceExpression<T>{res};
}

Здесь - минимальный рабочий код в Coliru. Является ли такая конструкция разумной или она излишняя, чтобы изящно решить эту проблему?

12 голосов | спросил Morwenn 17 MarpmMon, 17 Mar 2014 20:28:23 +04002014-03-17T20:28:23+04:0008 2014, 20:28:23

3 ответа


5

Я нахожу все это излишним. Соглашаясь в целом с Майклом Урманом , программист /пользователь должен знать о таких вариантах. Здесь я могу видеть, по крайней мере, две разные функции:

template<std::size_t N, typename T>
T squared_distance(const Point<N, T>& lhs, const Point<N, T>& rhs)
{
    T res{};
    for (std::size_t i = 0 ; i < N ; ++i)
    {
        auto tmp = lhs[i] - rhs[i];
        res += tmp * tmp;
    }
    return res;
}

template<std::size_t N, typename T>
T distance(const Point<N, T>& lhs, const Point<N, T>& rhs)
{
    return std::sqrt(squared_distance(lhs, rhs));
}

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

Например, данный Point 'x, y, вычитание вектора

z = x - y

может быть шаблоном выражения, так что z[i] == x[i] - y[i] для каждого i. Квадратизация каждого элемента будет другим шаблоном выражения, так что

z = square(x - y)

имел бы z[i] == w * w для каждого i, где w = (x - y)[i]. Тогда,

squared_norm(x - y)

вычислил бы фактическое сокращение как

template<typename X>
T sum(const X& x) { return std::accumulate(x.begin(), x.end(), X{}); }

template<typename X>
T squared_norm(const X& x) { return sum(square(x)); }

Предполагая, что Point или более общий шаблон выражения, снабжены begin(), end() (что им нужно). Примечание. Я не использую std::inner_product, чтобы избежать дополнительной стоимости, когда x - это (ленивый) шаблон выражения. Тогда squared_distance будет тривиальным

template<typename X, typename Y>
T squared_distance(const X& x, const Y& y) { return squared_norm(x - y); }

или вообще не требуется, а distance обобщен как

template<typename X, typename Y>
T distance(const X& x, const Y& y) { return std::sqrt(squared_distance(x, y)); }

Есть еще что-то, что нужно обобщать, рассматривая ссылки rvalue и, если это необходимо, заблаговременно, но я хотел сохранить это в чистоте.

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

  

В (1) измерения расстояния d1 и d2 в R индуцируются   на d, так что для всех a, b: d (a, b) = d1 (a1, b1) + d2 (a2, b2). Самый простой и самый важный случай - установить d, d1 и d2 в квадрат эвклидовых расстояний в соответствующих пространствах.

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

PS. Зачем вам нужно std::abs() вообще? И почему не просто std::array<T, N> вместо Point<N, T>

ответил iavr 20 MarpmThu, 20 Mar 2014 16:09:52 +04002014-03-20T16:09:52+04:0004 2014, 16:09:52
8

Теперь я беспокоюсь, что вы делаете несколько вызовов, чтобы получить фактическое расстояние.
Каждый раз, когда вы делаете это, вы берете на себя расходы на операцию sqrt().

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

Но это имеет побочный эффект добавления условной ветви в get, которая также может быть дорогостоящей при рассмотрении микрооптимизации.

ответил Martin York 17 MarpmMon, 17 Mar 2014 23:45:29 +04002014-03-17T23:45:29+04:0011 2014, 23:45:29
7

Я согласен, что необходимо больше контекста, чтобы знать, является ли это правильным подходом. Когда я работал с трассировкой лучей, вам чаще всего нужно было знать ближайший элемент или расстояние было выше или ниже некоторого порога, но не нужно было знать, что такое фактическое расстояние. В этих контекстах в то время я работал с необработанными числами, которые были явно квадратом расстояния, возвращенным из функции, называемой distance2; Я думаю, что предпочитаю этот подход.

Похоже, вы пытаетесь скрыть квадраты и квадратные корни. Абстракции, подобные этому, могут быть очень полезными, но приходят к цене. Без абстракции программист должен отслеживать сложность, а это означает, что в голове программиста одновременно будет вписываться меньшее количество других предметов. Однако, скрывая эту оптимизацию, вам нужно либо сделать другое время против компромиссного пространства (например, вы сначала сэкономите время, задерживая или избегая вызова sqrt, но затем должны выбрать, следует ли кэшировать результаты, кеширование экономит время но стоимость пространства). По сути, класс пытается угадать, что нужно программисту, и это часто происходит плохо.

Если использование памяти является проблемой, вы можете уменьшить дополнительные требования к кешу, добавив сложности. Опираясь на то, что никакие расстояния не являются отрицательными; используя отрицательное расстояние, можно отметить, является ли это расстоянием или его квадратом. Но, несмотря на сохранение дополнительного хранилища, эта сложность проявляется во всех операторах.

Как далеко должна пройти эта абстракция? Если вы указали операторы сравнения, такие как operator<? Если да, укажите их как для двух значений DistanceExpression<T>, так и для T и значение DistanceExpression<T>? Это может быть полезно, если вы хотите написать if (distance(p, q) < 10), не требуя вызова sqrt. Но опять же if (distance2(p, q) < 100) также понятен.

Рассмотрение вне вашего явного вопроса, хороший вызов по маркировке DistanceExpression<T> 's constructor explicit, хотя был удивлен, что вы инициализировали его элемент _data, используя скобки () вместо фигурных скобок {}. Старые привычки умирают с трудом! Я также предпочитаю избегать лидирующего подчеркивания имен участников, но кажется, что только когда следующая буква является капиталом, она категорически зарезервирована. Остерегайтесь тонкого льда.

ответил Michael Urman 19 MaramWed, 19 Mar 2014 06:20:58 +04002014-03-19T06:20:58+04:0006 2014, 06:20:58

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132