Оптимизация простой функции C ++ для минимизации копирования

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

  1. Определите неидиоматические конструкции.

  2. Объясните, где я делаю ненужное копирование объектов

  3. Любые другие упрощающие комментарии.

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
vector<vector<T>> powerset(vector<T> s)
{
  // Return the powerset containing the empty set
  if(s.size() == 0) {
    vector<int> dummy;
    return vector<vector<T>> { dummy };
  }

  T v = s.back();
  s.pop_back();

  // Recursively generate powerset for s setminus v
  vector<vector<T>> pss = powerset<T>(s);
  // This is the basis for the current powerset set
  vector<vector<T>> ps = pss;

  for(auto&& i : pss) {
    // Add a set with v added for each set
    i.push_back(v);
    ps.push_back(i);
  }

  return ps;
}

int main(void)
{
  vector<int> v = {1,2,3,4};

  vector<vector<int>> ps = powerset<int>(v);

  cout << "Powerset contains the following elements:" << endl;
  for(auto&& i : ps) {
    for(auto&& j : i) {
      cout << j << " ";
    }
    cout << endl;
  }

  return 0;
}
11 голосов | спросил JT1 17 WedEurope/Moscow2014-12-17T12:04:55+03:00Europe/Moscow12bEurope/MoscowWed, 17 Dec 2014 12:04:55 +0300 2014, 12:04:55

2 ответа


12

Немного о вашем коде, который вы могли бы улучшить:

  • В powerset есть ошибка: пока он отлично работает с вашим тестовым случаем, вы специально пытаетесь вернуть ---- +: = 1 =: + ----, когда std::vector<int> есть size, пока вы должны возвращать 0.

  • Вам даже не нужен вектор std::vector<T>. Вы можете использовать равномерную инициализацию инициализации и скобки в операторе dummy, чтобы просто написать это:

    return
  • Использование return { {} }; в состоянии нормально, но идиоматический способ сделать это - использовать s.size() == 0. Хотя это не имеет большого значения для s.empty(), некоторые реализации std::vector все еще реализует a \ $ O (n) \ $ std::list, а size всегда будет \ $ O (1) \ $ (для C ++ 11 требуется empty to be \ $ O (1) \ $, но не все версии являются актуальными). Использование std::list::size будет лучше, если вам когда-либо понадобится изменить тип используемой вами коллекции.

  • Так как empty не будет использоваться после последнего pss цикла for, вы можете смело перемещать элементы из него, а не копировать их:

    powerset

    Векторы в for(auto&& i : pss) { // Add a set with v added for each set i.push_back(v); ps.push_back(std::move(i)); } будут перенесены в pss, но остается в допустимом состоянии, поэтому вам не нужно бояться ошибок или неопределенного поведения.

  • Каждый раз, когда вы вызываете ps, вы копируете полный powerset, пока вам нужно только прочитать элементы. Вместо вектора вы можете передавать итераторы, чтобы вам не пришлось бесконечно копировать векторы, которые вам нужно только прочитать:

    std::vector

    Это не самый красивый в мире, но он работает, и вы даже сможете обобщать агорифм, чтобы он выполнял любые template<typename T> vector<vector<T>> powerset(typename vector<T>::iterator first, typename vector<T>::iterator last) { // Return the powerset containing the empty set if(std::distance(first, last) == 0) { return { {} }; } --last; T v = *last; // Recursively generate powerset for s setminus v vector<vector<T>> pss = powerset<T>(first, last); // This is the basis for the current powerset set vector<vector<T>> ps = pss; for(auto&& i : pss) { // Add a set with v added for each set i.push_back(v); ps.push_back(std::move(i)); } return ps; } вместо простого BidirectionalIterator.

ответил Morwenn 17 WedEurope/Moscow2014-12-17T13:18:16+03:00Europe/Moscow12bEurope/MoscowWed, 17 Dec 2014 13:18:16 +0300 2014, 13:18:16
6

vector<vector<T>> довольно специфичен для набора параметров и громоздкий для записи. Вместо этого вы можете использовать typedef и более конкретное имя функции.

template<typename T>
using powerset = vector<vector<T>>;

template<typename T>
powerset<T> createPowerset(vector<T> s)
{
  if(s.size() == 0) {
    vector<int> dummy;
    return powerset<T> { dummy };
  }

  T v = s.back();
  s.pop_back();

  // no explicit template parameter on createPowerset. 
  // Type deduction is used here
  powerset<T> pss = createPowerset(s);
  powerset<T> ps = pss;

  for(auto&& i : pss) {
    i.push_back(v);
    ps.push_back(i);
  }
  return ps;
}
ответил flakes 17 WedEurope/Moscow2014-12-17T16:04:20+03:00Europe/Moscow12bEurope/MoscowWed, 17 Dec 2014 16:04:20 +0300 2014, 16:04:20

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

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

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