Вопрос:
У меня есть вектор вектора без знака. Мне нужно найти пересечение всех этих векторов без знака для этого, я написал следующий код:
int func() { vector<vector<unsigned> > t; vector<unsigned> intersectedValues; bool firstIntersection=true; for(int i=0;i<(t).size();i++) { if(firstIntersection) { intersectedValues=t[0]; firstIntersection=false; }else{ vector<unsigned> tempIntersectedSubjects; set_intersection(t[i].begin(), t[i].end(), intersectedValues.begin(), intersectedValues.end(), std::inserter(tempIntersectedSubjects, tempIntersectedSubjects.begin())); intersectedValues=tempIntersectedSubjects; } if(intersectedValues.size()==0) break; } }
Каждый отдельный вектор имеет 9000 элементов, и таких “векторов” много. Когда я профилировал свой код, я обнаружил, что set_intersection занимает максимальное время и, следовательно, делает код медленным, когда есть много вызовов функции func(). Кто-нибудь может предложить, как сделать код более эффективным.
Я использую: gcc (GCC) 4.8.2 20140120 (Red Hat 4.8.2-15)
EDIT: отдельные векторы в векторе “t” сортируются.
Лучший ответ:
У меня нет рамки для профилирования операций, но я бы, конечно, изменил код, чтобы повторно использовать легко выделенный вектор. Кроме того, я бы поднял начальное пересечение из цикла. Кроме того, std::back_inserter() должен убедиться, что элементы добавлены в правильном месте, а не в начале:
int func() { vector<vector<unsigned> > t = some_initialization(); if (t.empty()) { return; } vector<unsigned> intersectedValues(t[0]); vector<unsigned> tempIntersectedSubjects; for (std::vector<std::vector<unsigned>>::size_type i(1u); i < t.size() && !intersectedValues.empty(); ++i) { std::set_intersection(t[i].begin(), t[i].end(), intersectedValues.begin(), intersectedValues.end(), std::back_inserter(tempIntersectedSubjects); std::swap(intersectedValues, tempIntersectedSubjects); tempIntersectedSubjects.clear(); } }
Я думаю, что у этого кода есть шанс стать быстрее. Также может быть разумным пересечь множество множеств: вместо того, чтобы держать один набор и пересекаться с ним, вы могли бы создать новое пересечение для пар соседних множеств, а затем пересечь первые множества с уважением соседних:
std::vector<std::vector<unsigned>> intersections( std::vector<std::vector<unsigned>> const& t) { std::vector<std::vector<unsigned>> r; std::vector<std::vector<unsignned>>::size_type i(0); for (; i + 1 < t.size(); i += 2) { r.push_back(intersect(t[i], t[i + 1])); } if (i < t.size()) { r.push_back(t[i]); } return r; } std::vector<unsigned> func(std::vector<std::vector<unsigned>> const& t) { if (t.empty()) { /* deal with t being empty… */ } std::vector<std::vector<unsigned>> r(intersections(t)) return r.size() == 1? r[0]: func(r); }
Конечно, вы бы не реализовали его так: вы бы использовали двоичный счетчик Степанова для хранения промежуточных наборов. Этот подход предполагает, что результат, скорее всего, не пуст. Если ожидание состоит в том, что результат будет пустым, это может быть не улучшением.
Ответ №1
Вы можете сделать std::set_intersection, а также множество других стандартных библиотечных алгоритмов, которые выполняются параллельно, определяя _GLIBCXX_PARALLEL во время компиляции. Вероятно, это лучший коэффициент работы. Для документации см. this.
Предупреждение об ошибке:
Обратите внимание, что определение _GLIBCXX_PARALLEL может изменять размеры и поведение стандартных шаблонов классов, таких как std::search, и поэтому можно связать только код, скомпилированный с параллельным режимом и кодом, скомпилированным без параллельного режима, если не создается экземпляр контейнера между двумя единицами перевода. Функциональность параллельного режима имеет четкую связь и не может смешиваться с символами нормального режима.
из здесь.
Еще одна простая, хотя и незначительно небольшая оптимизация – резервирование достаточного пространства перед заполнением ваших векторов.
Кроме того, попробуйте выяснить, помогает ли вставка значений на спине, а не на фронт, а затем – на обратный вектор. (Хотя я даже думаю, что ваш код неверен прямо сейчас, а ваш intersectedValues отсортирован неправильно. Если я не ошибаюсь, вы должны использовать std::back_inserter вместо std::inserter(…,begin), а затем не отменить). через память довольно быстро, а не переключение должно быть еще быстрее.
Ответ №2
Я не могу проверить это, но может быть, что-то вроде этого будет быстрее?
int func() { vector<vector<unsigned> > t; vector<unsigned> intersectedValues; // remove if() branching from loop if(t.empty()) return -1; intersectedValues = t[0]; // now start from 1 for(size_t i = 1; i < t.size(); ++i) { vector<unsigned> tempIntersectedSubjects; tempIntersectedSubjects.reserve(intersectedValues.size()); // pre-allocate // insert at end() not begin() set_intersection(t[i].begin(), t[i].end(), intersectedValues.begin(), intersectedValues.end(), std::inserter(tempIntersectedSubjects, tempIntersectedSubjects.end())); // as these are not used again you can move them rather than copy intersectedValues = std::move(tempIntersectedSubjects); if(intersectedValues.empty()) break; } return 0; }
Другая возможность:
Думая об этом с помощью swap(), можно оптимизировать обмен данными и удалить необходимость перераспределения. Кроме того, конструктор temp может быть перемещен из цикла.
int func() { vector<vector<unsigned> > t; vector<unsigned> intersectedValues; // remove if() branching from loop if(t.empty()) return -1; intersectedValues = t[0]; // no need to construct this every loop vector<unsigned> tempIntersectedSubjects; // now start from 1 for(size_t i = 1; i < t.size(); ++i) { // should already be the correct size from previous loop // but just in case this should be cheep // (profile removing this line) tempIntersectedSubjects.reserve(intersectedValues.size()); // insert at end() not begin() set_intersection(t[i].begin(), t[i].end(), intersectedValues.begin(), intersectedValues.end(), std::inserter(tempIntersectedSubjects, tempIntersectedSubjects.end())); // swap should leave tempIntersectedSubjects preallocated to the // correct size intersectedValues.swap(tempIntersectedSubjects); tempIntersectedSubjects.clear(); // will not deallocate if(intersectedValues.empty()) break; } return 0; } Ответ №3
Скопировать элементы из векторов из вектора для цикла с помощью emplace_back() может сэкономить ваше время. И нет необходимости в флаге, если вы измените индекс итератора for for. Таким образом, цикл может быть оптимизирован, и проверка состояния может быть удалена для каждой итерации.
void func() { vector<vector<unsigned > > t; vector<unsigned int > intersectedValues; for(unsigned int i=1;i<(t).size();i++) { intersectedValues=t[0]; vector<unsigned > tempIntersectedSubjects; set_intersection(t[i].begin(), t[i].end(), intersectedValues.begin(), intersectedValues.end(), std::back_inserter(tempIntersectedSubjects); for(auto &ele: tempIntersectedSubjects) intersectedValues.emplace_back(ele); if( intersectedValues.empty()) break; } } Ответ №4
set:: set_intersection может быть довольно медленным для больших векторов. Возможно использование создать аналогичную функцию, которая использует lower_bound. Что-то вроде этого:
template<typename Iterator1, typename Iterator2, typename Function> void lower_bound_intersection(Iterator1 begin_1, Iterator1 end_1, Iterator2 begin_2, Iterator2 end_2, Function func) { for (; begin_1 != end_1 && begin_2 != end_2;) { if (*begin_1 < *begin_2) { begin_1 = begin_1.lower_bound(*begin_2); //++begin_1; } else if (*begin_2 < *begin_1) { begin_2 = begin_2.lower_bound(*begin_1); //++begin_2; } else // equivalent { func(*begin_1); ++begin_1; ++begin_2; } } }
