Копирование из одномерного векторного вектора <int>начинается с первого элемента двухмерного векторного вектора пары > матрица - PullRequest
Новая
       83

Копирование из одномерного векторного вектора <int>начинается с первого элемента двухмерного векторного вектора пары > матрица

1 голос
/ 27 марта 2020

У меня есть несколько 3 одномерных векторов (vector<int> starts, vector<int> ends, vector<int> points). Каждый из которых имеет указанное c количество элементов.

Я хочу создать двумерный вектор vector<pair<int,int>>matrix в такой последовательности:

  1. от начала matrix до размера start first элемент matrix это элементы vector<int> starts и секунда элемент равен "-1"
  2. Теперь добавьте элементы от vector<int> ends до matrix так, чтобы first элемент matrix это элементы vector<int> ends и секунда элемент равен "-2"

  3. Добавьте теперь элементы от vector<int> points к matrix так, чтобы первый элемент matrix является элементами vector<int> points, а второй элемент является индексом точек.

    Визуальное представление: -

    Ввод:

    начинается: {1, 2, 3} заканчивается: {4, 5, 6} указывает: (7, 8, 9}

    Выход:

    матрица: { {1, -1}, {2, -1}, {3, -1}, {4, -2}, {5, -2}, {6, -2}, {7, 0}, {8, 1}, {9, 2} }

В настоящее время я использую push_back с функцией for-l oop, которая прекрасно работает, но когда размер ввода большой, код очень медленный.

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

vector<pair<int,int>> fast_count_segments(
    vector<int> starts, 
    vector<int> ends, 
    vector<int> points) 
{
   int i = 0;
   vector<pair<int,int>>matrix;

   for(i; i<starts.size(); i++) {
       matrix.push_back(make_pair(starts[i],-1));
   }
   for(i; i<starts.size()+ends.size(); i++) {
       matrix.push_back(make_pair(ends[i-starts.size()],-2));
   }
   for(i; i<starts.size()+ends.size()+points.size(); i++) {
        matrix.push_back(make_pair(
            points[i-starts.size()-ends.size()],
            i-(starts.size()+ends.size())
        ));
   }
   return matrix;
}

Подскажите, пожалуйста, как быстро заполнить двумерный вектор этими требованиями, не повторяя каждый элемент. Я использую C ++ 11. Заранее спасибо !!

Ответы [ 2 ]

1 голос
/ 27 марта 2020

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

Несмотря на это, вот несколько идей по улучшению скорости:

  1. Не принимайте входные векторы по значению! Это бесполезное копирование ... возьмите их .data(), или их .cbegin() итератор, или возьмите параметр span<int>.
  2. Используйте reserve() метод целевого вектора, чтобы избежать многократного перераспределения.
  3. Используйте .emplace_back() вместо .push_back() для построения точек на месте, а не для построения, а затем перемещения каждой точки. Хотя, если честно, компилятор, вероятно, все равно оптимизирует эти конструкции.
  4. Поместите значения .size() входных векторов в локальные переменные. Это поможет, только если по какой-то причине компилятор подозревает, что размер не будет постоянным на протяжении всего выполнения функции.
  5. Убедитесь, что вы передаете переключатели оптимизации компилятору (например, -O2 или -O3 до G CC и лязг). Это может показаться вам очевидным, но иногда это так очевидно, что вы забыли проверить, действительно ли это сделано.

Некоторые комментарии эстетики c:

  1. Нет необходимости использовать один и тот же счетчик для всех векторов. for(int i = 0; i < whatever; i++) можно использовать несколько раз.
  2. Нет необходимости в raw для циклов, вы можете использовать for(const auto& my_element : my_vector) для первых двух циклов. Третий l oop хитрее, так как вы хотите индекс. Вы можете использовать std::difference(), работая с итераторами, или go с перечислением стиля Python, описанным здесь .
  3. Вы можете рассмотреть возможность использования std::transform() с back_emplacer выходными итераторами вместо всех трех петель. Код No-l oop! Это означало бы использование std::difference() в лямбда-преобразователе вместо третьего l oop.
0 голосов
/ 28 марта 2020

Сюда входят предложения из ответа @ einpoklum , но также очищается код. 

std::vector<std::pair<int,int>> fast_count_segments(
    std::vector<int> const & starts, 
    std::vector<int> const & ends, 
    std::vector<int> const & points) 
{
   std::vector<std::pair<int,int>> matrix(starts.size() + ends.size() + points.size());

   auto out = std::transform(starts.cbegin(), starts.cend(),
                             matrix.begin(), 
                             [](int i) { return std::pair<int,int>{i, -1}; });

   out = std::transform(ends.cbegin(), ends.cend(),
                        out, 
                        [](int i) { return std::pair<int,int>{i, -2}; });

   int c = 0;
   std::transform(points.cbegin(), points.cend(),
                  out,
                  [&c](int i) { return std::pair<int,int>{i, c++}; });

   return matrix;
}

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


std::vector<std::pair<int,int>> fast_count_segments(
    std::vector<int> const & starts, 
    std::vector<int> const & ends, 
    std::vector<int> const & points) 
{
   std::vector<std::pair<int,int>> matrix(starts.size() + ends.size() + points.size());
   int c = 0;

   std::transform(points.cbegin(), points.cend(),
        std::transform(ends.cbegin(), ends.cend(),
            std::transform(starts.cbegin(), starts.cend(),
                matrix.begin(), 
            [](int i) { return std::pair<int,int>{i, -1}; }),
        [](int i) { return std::pair<int,int>{i, -2}; }),
    [&c](int i) { return std::pair<int,int>{i, c++}; });

   return matrix;
}
...