n-мерные шаблоны вычисления евклидова пространства

Я работал с кодом C ++ 11, который использует std::vector[] для хранения координат. Чаще всего этот код использует 2D или 3D, но мне пришло в голову, что он может быть в целом полезен для n-мерных расчетов евклидова расстояния.

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

// euclid.h
#include <vector>
#include <algorithm>
#include <stdexcept>

template <typename T>
std::vector<T> operator+(const std::vector<T>& a, const std::vector<T>& b)
{
    if (a.size() != b.size())
        throw std::domain_error("vector addition must have equal length vectors");
    std::vector<T> result;
    result.reserve(a.size());  
    std::transform(a.begin(), a.end(), b.begin(), 
                   std::back_inserter(result), std::plus<T>());
    return result;
}

template <typename T>
std::vector<T> operator-(const std::vector<T>& a, const std::vector<T>& b)
{
    if (a.size() != b.size())
        throw std::domain_error("vector subtraction must have equal length vectors");
    std::vector<T> result;
    result.reserve(a.size());
    std::transform(a.begin(), a.end(), b.begin(), 
                   std::back_inserter(result), std::minus<T>());
    return result;
}

template <typename T>
T squared_distance(const std::vector<T>& a, const std::vector<T>& b)
{
    if (a.size() != b.size())
        throw std::domain_error("squared_distance requires equal length vectors");
    return std::inner_product(a.begin(), a.end(), b.begin(), T(0), 
        std::plus<T>(), [](T x,T y){return (y-x)*(y-x);});

}

Вот пример кода драйвера для демонстрации использования.

// points.cpp
#include <iostream>
#include <vector>
#include "euclid.h"

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T> &v)
{
    out << "{ ";
    for (auto p : v)
        out << p << ' ';
    return out << "}";
}

#define say(x) std::cout << "" #x " = " << (x) << std::endl
int main()
{
    std::vector<double> origin{0, 0, 0}, a{3, 4, 5}, b{-1, -2, -3},g{0,0,0,0};
    say(origin);
    say(a);
    say(b);
    say(a+b);
    say(a-b);
    say(b-a);
    say(squared_distance(origin,a));
    say(squared_distance(origin,b));
}

Результат программы выглядит следующим образом:

origin = { 0 0 0 }
a = { 3 4 5 }
b = { -1 -2 -3 }
a+b = { 2 2 2 }
a-b = { 4 6 8 }
b-a = { -4 -6 -8 }
squared_distance(origin,a) = 50
squared_distance(origin,b) = 14

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

  1. Может ли вычисление squared_distance быть более эффективным?
  2. есть хороший способ уменьшить дублирование кода в + и -?
  3. Я тестировал с помощью int, float, double и std::complex. Что еще может быть полезно?
  4. существует ли какая-либо точка для размещения типов unsigned?
  5. Должен ли я что-нибудь делать с возможным числовым переполнением или потоком?
  6. есть ли смысл иметь заголовок #ifndef в этом файле?
11 голосов | спросил Edward 6 AMpSun, 06 Apr 2014 00:21:36 +040021Sunday 2014, 00:21:36

5 ответов


8

Чтобы уменьшить избыточность, я бы, вероятно, переместил чек, чтобы входы были одного размера в шаблон функции, и просто вызываем это из других трех:

template <typename T>
void check_size(std::vector<T> const &a, std::vector<T> const &b) {
    if (a.size() != b.size())
        throw std::domain_error("vector addition must have equal length vectors");
}

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

template <typename T>
std::vector<T> operator+(std::vector<T> a, const std::vector<T>& b)
{
    check_size(a, b);
    std::transform(a.begin(), a.end(), 
                   b.begin(), 
                   a.begin(), 
                   std::plus<T>());
    return a;
}

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

Другая возможность рассмотреть будет использовать std::valarray. Это забытый шаг-ребенок (так сказать) стандарта C ++, но он был разработан специально для поддержки быстрых численных вычислений. Он уже определяет эквиваленты вашего кода + и -, а также sum и *, поэтому ваш код выйдет примерно так:

std::valarray<double> origin{ 0, 0, 0 }, a{ 3, 4, 5 }, b{ -1, -2, -3 }, g{ 0, 0, 0, 0 };
say(origin);
say(a);
say(b);
say(a + b);
say(a - b);
say(b - a);
say(((a - origin) * (a - origin)).sum());
say(((b - origin) * (b - origin)).sum());

Так как std::valarray определяет все операторы, которые мы используем, нам нужен только следующий код: say и перегрузка operator<< (минимально измененная, чтобы взять std::valarray вместо std::vector).

Учитывая ваши более конкретные вопросы:

конкретные вопросы:

  
  • Может ли вычисление squared_distance быть более эффективным?
  •   

std::valarray и /или std::array может помочь, но при относительно небольшом числе измерений я не ожидал бы большой разницы.

  
  • Есть ли хороший способ уменьшить дублирование кода в операциях + и -?
  •   

В приведенном выше коде попытка ответить на это, по крайней мере, в некоторой степени.

  
  • Я тестировал с int, float, double и std :: complex. Что еще может быть полезно?
  •   
  • Есть ли смысл размещать неподписанные типы?
  •   

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

  
  • Должен ли я что-нибудь делать с возможным числовым переполнением или потоком?
  •   

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

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

  
  • Есть ли смысл иметь заголовок заголовка #ifndef в этом файле?
  •   

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

Я собирался упомянуть std::array, но пока я писал это, я вижу, что @Morwenn написал об этом уже .

ответил Jerry Coffin 6 AMpSun, 06 Apr 2014 04:38:21 +040038Sunday 2014, 04:38:21
6

Что касается дублирования, у вас может быть одна функция для применения функции elementwize:

template< typename T, typename U, typename BinaryFunc >
auto elementwise_apply(const vector<T> &x, const vector<U> &y, BinaryFunc func)
     -> vector<decltype(func(x[0], y[0]))>
{
    // apply `func` to all arguments and return a vector
}

, а затем объявить ваши другие двоичные операции в терминах

template< typename T>
vector<T> operator+(const vector<T> &x, const vector<T> &y)
{
    return elementwise_apply(x, y, plus<T>());
}

и т. д.

Я также согласен с тем, что вы можете использовать array, а не vector - тем больше, что вы можете совершить во время компиляции, а не времени выполнения, тем лучше. Точно так же меньшее количество динамических распределений и меньшее количество неинтенсивных функций обычно приведет к более эффективному коду.

Я также предлагаю вам создать структуру point, которая имеет array (или vector), вместо использования открытого array, так что все ваши функции будут применимы только к объектам, предназначенным для фактического обращения к точкам.

ответил Hurkyl 6 AMpSun, 06 Apr 2014 05:24:38 +040024Sunday 2014, 05:24:38
6

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

Обобщения

Прежде чем приступить к вашему вопросу, давайте рассмотрим пару ограничений в текущем подходе

operator+(const std::vector<T>& a, const std::vector<T>& b)

(A) Почему векторы имеют одинаковый тип значений? Лучше, почему в первую очередь есть те же самые контейнеры?

(B) Зачем ограничивать операцию двумя аргументами? там есть унарные операторы, а также есть n-арные функции.

Проблема (A) может быть решена несколькими функциями типа:

template <typename C, typename T>
struct subs_type;

template <template <typename...> class C, typename T, typename... A, typename S>
struct subs_type<C<T, A...>, S> { using type = C<S, A...>; };

template <typename... A>
using container_common_type = std::common_type<typename A::value_type...>;

template <typename A, typename... B>
using container_result =
    subs_type<A, typename container_common_type<A, B...>::type>;

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

Проблема (B) может быть решена довольно универсальным функциональным объектом apply:

template <typename F>
struct apply : F
{
    using F::operator();

    template <typename A, typename... B>
    typename container_result<A, B...>::type
    operator()(const A& a, const B&... b) const
    {
        using R = typename container_result<A, B...>::type;

        if (_or()(a.size() != b.size()...))
            throw std::domain_error("vector operation must have equal length vectors");

        R result;
        result.reserve(a.size());
        auto r = std::back_inserter(result);
        transform(*this, r, a.begin(), a.end(), b.begin()...);
        return result;
    }
};

В словах apply применяется объект функции типа F для ввода аргументов типов A, B.... Здесь есть несколько интересных обобщений:

  • Для этого требуется не менее один входной аргумент A, но в противном случае полное вариационное определение допускает унарные, двоичные или произвольные n-арные функции.

  • Он выводит функциональный объект F, перегрузки его ---- +: = 10 =: + ---- и использует сам как функцию при вводе operator(). Это позволяет использовать рекурсивное приложение, чтобы тот же объект мог применяться к скалярам, ​​а также к любому контейнеру. Ниже вы найдете пример под вашим вопросом 3.

Однако он сохраняет ту же логику сохранения результата, используя transform и reserve. Я обсуждаю альтернативы позже.

Ниже описаны операции, требуемые back_inserter:

apply

Функциональный объект struct _or { constexpr bool operator()() const { return false; } template <typename A, typename... B> constexpr bool operator()(A&& a, B&&... b) const { return std::forward<A>(a) || operator()(std::forward<B>(b)...); } }; struct _do { template <typename... A> _do(A&&...) { } }; template <typename F, typename R, typename I, typename E, typename... J> void transform(const F& f, R r, I i, E e, J... j) { for (; i != e; _do{++r, ++i, ++j...}) *r = f(*i, *j...); } в значительной степени самоочевиден: это n-ary обобщение _or

Функция operator||, возможно, самая странная из всех. Это более или менее n-арное обобщение transform. std::transform - это итератор вывода, r текущий итератор и i,e соответственно первого контейнера, а end - итераторы оставшихся итераторов. Функциональный объект и выходной итератор выводятся первыми, чтобы в дальнейшем использовать итераторы с вариационным входом. Все итераторы передаются по значению.

В словах, j... имеет выход и количество итераторов ввода. Все итераторы параллельны параллельно . На каждой итерации функциональный объект transform применяется к разыменованным значениям всех итераторов ввода f, и результат сохраняется на значение выходного итератора *i, *j....

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

Дублирование кода

  

(2) есть ли хороший способ уменьшить дублирование кода в операциях + и -?

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

Do

Эти макросы определены, а затем используются только один раз для генерации кода для требуемых операторов. Затем вы можете определить их, чтобы избежать загрязнения. Будьте осторожны, чтобы использовать префикс в имени макросов, чтобы избежать столкновений. Я предположил, что вы создаете библиотеку под названием MYLIB_OP_UNARY(plus, +) MYLIB_OP_UNARY(minus, -) MYLIB_OP_BINARY(add, +) MYLIB_OP_BINARY(sub, -) MYLIB_OP_BINARY(mul, *) MYLIB_OP_BINARY(div, /) MYLIB_OP_BINARY(mod, %) MYLIB_OP_BINARY(eq, ==) MYLIB_OP_BINARY(neq, !=) MYLIB_OP_BINARY(gt, >) MYLIB_OP_BINARY(lt, <) MYLIB_OP_BINARY(ge, >=) MYLIB_OP_BINARY(le, <=) MYLIB_OP_UNARY(_not, !) MYLIB_OP_BINARY(_and, &&) MYLIB_OP_BINARY(_or, ||) MYLIB_OP_UNARY(bit_not, ~) MYLIB_OP_BINARY(bit_and, &) MYLIB_OP_BINARY(bit_or, |) MYLIB_OP_BINARY(bit_xor, ^) .

Макросы необходимы, потому что каждый расширяет примерно до 20 строк кода (что является минимальным возможным, несмотря на абстракции), и я не хотел бы копировать этот код 20 раз и более. И если вы считаете, что mylib является излишним, кто-то другой не будет.

Теперь вот как определяется operator== (MYLIB_OP_BINARY похож):

MYLIB_OP_UNARY

Во-первых, внутри отдельного пространства имен #define MYLIB_OP_BINARY(NAME, OP) \ \ namespace operators { \ struct NAME \ { \ template <typename A, typename B> \ constexpr auto \ operator()(A&& a, B&& b) const \ -> decltype(std::forward<A>(a) OP std::forward<B>(b)) \ { return std::forward<A>(a) OP std::forward<B>(b); } \ }; \ } \ \ template <typename A, typename B> \ typename container_result<A, B>::type \ operator OP(const A& a, const B& b) \ { \ return apply<operators::NAME>()(a, b); \ } \ мы фиксируем значение каждого оператора C ++ в объект функции. Это похоже на operators и т. Д., Но

  • применяется к любому оператору C ++
  • не является шаблоном, что позволяет проще использовать

Затем для каждого оператора мы определяем соответствующий «векторный» оператор для контейнеров и , просто позвонив std::plus

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

apply

действует только в том случае, если typename container_result<A, B>::type являются экземплярами шаблонов классов, определяющими их собственный A,B (так, обычно контейнеры). В противном случае учитываются только другие перегрузки. Поэтому нам не нужен value_type; enable_if достаточно для смены замены.

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

В моей работе я отдельно фиксирую все операторы C ++ здесь , а затем определите« векторизованные »копии здесь .

Пространство имен

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

Эффективность (накопление)

  

(1) можно сделать расчет mylib?

Я не хочу слишком много описывать здесь. Простое изменение будет хорошим:

squared_distance

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

Эффективность (по элементарным операциям)

Я оставил проблему хранения результата внутри return std::inner_product(a.begin(), a.end(), b.begin(), T(0), std::plus<T>(), [](T x,T y){T z = y-x; return z*z;}); . Использование apply вместе с std::vector::reserve() означает, что

  • Мы ограничены контейнерами, имеющимиstd::back_inserter, следовательно, скорее всего, reserve().
  • Мы изменяем размер контейнера на каждой итерации. Даже если мы не перераспределяем, нам нужно хотя бы обновить размер вектора.

Здесь есть множество опций, но в большинстве случаев можно было бы перейти на более низкий уровень реализации или использовать другой вид контейнера.

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

Но тогда почему std::vector определяет, какой тип возвращаемого контейнера и как его следует инициализировать, изменить размер или скопировать? Для меня конечным решением является задержка оценки результата с помощью шаблоны выражений . Затем выражение apply возвращает только временный объект, содержащий ссылки на a - b и зная тип функции (например, std :: минус), а a, b выполняет фактическую работу, инициализируя в соответствии с ---- +: = 58 =: + ----.

Как я уже сказал, я работаю над этой темой. Здесь представление последовательности (объект ведет себя как контейнер), соответствующий c = a - b, как указано выше, и здесь является его итератором. Я боюсь, что этот код будет, вероятно, нечитаемым, потому что он использует гораздо больше объектов, определенных в другом месте, и потому, что он сделал еще много шагов абстракции и обобщения, чем показано здесь. Библиотеки, такие как boost :: multi_array , boost :: ublas или Eigen аналогичны в этом отношении (фактически, используя шаблоны выражений и , будучи нечитабельно внутренне )

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

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

Другие типы

  

(3) Я тестировал с int, float, double и std :: complex. Что еще может быть полезно?

     

(4) есть ли какая-либо точка для размещения неподписанных типов?

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

Другие типы? Что-нибудь! Например, почему не другие контейнеры? Рассмотрим:

std::common_type

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

Один «сбой» состоит в том, что разделение между векторами и скалярами выполняется путем проверки для типа члена std::complex, как я сказал выше. К сожалению, это невполне уместно, поскольку, например, std::vector<std::vector<double> > u{{0, 0, 0}, {3, 4, 5}}, v{{-1, -2, -3}, {5, 6, 7}}; say(u); say(v); say(-u); say(+v); say(u+v); say(u-v); say(v-u); имеет этот тип, но не является контейнером. У меня есть простой способ обхода в моем живом примере, также требуя ::value_type, но все такие проблемы будут разрешены понятия C ++ .

Вскоре приходит понимание, что добавление скаляра в вектор также будет удобным. Это приводит к четырем комбинациям операций. Тогда как насчет n-арной функции? Это приведет к комбинациям std::complex. У меня есть общее решение, и здесь является тестом образец моего кода, показывающий только некоторые из вещей, которые могут быть сделаны. Но это слишком далеко.

Другая проблема заключается в том, что мы в основном игнорировали move semantics здесь. Если бы мы писали этот код наиболее общим образом, мы должны использовать ссылки rvalue и переадресовывать везде. Это не так сложно сделать, но я пропустил его и использовал параметры ::size_type почти везде.

Стимулирование типа

  

(5) должен ли я что-нибудь сделать с возможным числовым переполнением или потоком?

Для элементарных операций ничего.

Для операций накопления, таких как 2^n, может быть, да. Например, добавление значений const& типа squared_distance может вставляться только в 1000 и int значения типа long могут помещаться только в 1000. Было бы удобно, чтобы рекламные акции типа автоматически выполнялись где-то, но для того, чтобы точно определить, когда требуется продвижение, требуется информация о времени выполнения, иначе мы можем продвигать «на всякий случай», что противоречит принципу C ++.

  

не платите за то, что вы не используете

Я считаю, что пользователь должен знать о таких проблемах. Ленивая оценка может снова прийти на помощь: в выражении float, если double является лишь временным промежуточным объектом, тогда фактическая работа выполняется только тогда, когда известен тип c = f(a, b) , Именно поэтому f(a, b) и c другой аргумент для вывода. У меня также есть общее решение здесь, но опять это заходит слишком далеко.

В настоящее время я предлагаю использовать правильные типы для входных векторов (например, std::accumulate), когда ожидается, что операция переполнение результата. Это, возможно, слишком большая нагрузка для пользователя, но мы не живем в идеальном мире.

ОБНОВЛЕНИЕ: Исправления

Теперь я понимаю, что использование std::inner_product не подходит для поиска возвращаемого типа. Он работает для операторов типа double, но не, например. для булевых операторов, где результат всегда common_type. Более того, +,* не будет работать с вложенными контейнерами с разными типами значений; он просто не определен для таких случаев.

Не слишком сложно заставить тип возвращаемого значения зависеть от операции bool, используя ---- +: = 86 =: + ----, как в объектах функции «захват», или common_type

decltype

, поэтому нужно заменить std::result_of для нового типа, например std::vector<T>, в и контейнер и распределитель, чтобы получить

std::vector<T, std::allocator<T> >

Предполагая, что контейнеры следуют этой структуре (в частности, все они имеютраспределители), я обновил предыдущий код соответствующим образом, но я здесь даю ссылку на новый живой пример , чтобы избежать этого ответа еще дольше. Для чего-то более общего без слишком большого шаблона, контейнеры должны обеспечивать такую ​​замену типа сами ; но, насколько мне известно, к сожалению, это не относится к STL.

Теперь мы можем применять бинарные операторы между контейнерами с такими же разнообразными типами значений, как

T

, как показано в живом примере, а также некоторые интересные случаи, такие как S.

Хорошо, вот и все, надеюсь, больше не буду писать!

ответил iavr 6 PMpSun, 06 Apr 2014 18:35:27 +040035Sunday 2014, 18:35:27
4

Я знаю, что это не ответит ни на один из ваших вопросов, но вместо использования std::vector<T> вам следует рассмотреть возможность использования std::array<T, N> для представления ваших данных. Вот почему этот дизайн может быть более интересным:

  • std::array<T, N> использует память стека, а std::vector<T> использует кучу Память. Бьюсь об заклад, что выделенный стеками массив будет немного более эффективным, чем выделенный выделенный кучей вектор.
  • Математически говоря, нет смысла менять размер вектора. Поэтому контейнер с фиксированным размером также гарантирует, что размер не изменится.
  • Вам больше не придется беспокоиться reserve.
  • В ваших функциях вы убедитесь, что вектор, который вы добавляете или вычитаете, имеет тот же размер. Если вы используете std::array<T, N> для хранения ваших данных, вы получите неявную проверку времени компиляции вместо явного времени выполнения:

    template <typename T, size_t N>
    std::array<T, N> operator+(const std::array<T, N>& a, const std::array<T, N>& b)
    {
        std::array<T, N> result;
        for (size_t i = 0 ; i < N ; ++i)
        {
            result[i] = a[i] + b[i];
        }
        return result;
    }
    

    Кроме того, поскольку ваш цикл имеет статическое условие, он может быть разворачиван компилятором во время компиляции.

ответил Morwenn 6 AMpSun, 06 Apr 2014 03:48:54 +040048Sunday 2014, 03:48:54
3

Результаты

Основываясь на полученной обратной связи (спасибо вам всем за то, что вы нашли время!) Я написал три разные версии, используя std::vector, std::array и std::valarray. Затем я модифицировал свой тестовый код, чтобы создать вектор из миллиона случайно созданных трехмерных точек (используя double), а затем вызвал squared_distance, чтобы заполнить второй массив результатов квадратным расстоянием между фиксированной случайной точкой и каждым из миллионов других точек. Затем я использовал команду time под Linux для записи времени пользователя для каждого из трех вариантов. Для каждого из них было проведено десять испытаний, а краткое изложение времени показано ниже.

          valarray  array   vector
average     0.976   0.904   1.730
variance    0.000   0.002   0.020

Как видно из результатов, оба std::valarray и std::array почти в два раза быстрее, чем исходная версия std::vector с std::array является самым быстрым. Эта версия кода показана ниже:

template <typename T, size_t N>
T squared_distance(const std::array<T,N>& a, const std::array<T,N>& b)
{
    T accum(0);
    for (int i=0; i<N; ++i)
    {
        T delta = b[i]-a[i];
        accum += delta*delta;
    }
    return accum;
}
ответил Edward 5 Maypm15 2015, 13:29:02

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

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

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