Performing intersection of vectors in C ++

Question

I have an unsigned vector vector. I need to find the intersection of all these unsigned vectors for this, I wrote the following code:

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; } } 

Each individual vector has 9000 elements, and there are many such "vectors". When I was profiling my code, I found that set_intersection takes maximum time and therefore makes the code slow when there are many calls to the func () function. Can anyone suggest how to make the code more efficient.

I use: gcc (GCC) 4.8.2 20140120 (Red Hat 4.8.2-15)

EDIT: The individual vectors in the "t" vector are sorted.

Answer 1

I don’t have a framework for profiling operations, but I would of course change the code to reuse an easily distinguished vector. In addition, I would raise the initial intersection from the loop. In addition, std::back_inserter() should make sure that the elements are added in the right place, and not at the beginning:

 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(); } } 

I think this code has a chance to become faster. It may also be wise to cross many sets: instead of holding one set and intersecting with it, you could create a new intersection for pairs of neighboring sets, and then cross the first sets with respect to the neighboring ones:

 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); } 

Of course, you would not implement it like this: you would use the Stepanov binary counter to store intermediate sets. This approach suggests that the result is most likely not empty. If the expectation is that the result will be empty, this may not be an improvement.

Answer 2

You can do std::set_intersection , as well as many other standard library algorithms that run in parallel by defining _GLIBCXX_PARALLEL at compile time. This is probably the best work rate. For documentation, see this .

Error warning:

Note that the definition of _GLIBCXX_PARALLEL can change the size and behavior of standard class templates, such as std::search , and therefore only code compiled with parallel mode and code compiled without parallel mode can be associated if a container instance is not created between two translation units . The functionality of the parallel mode has a clear connection and cannot be mixed with the symbols of the normal mode.

from here .

Another simple, albeit slightly minor optimization is to reserve enough space before filling your vectors.

Also, try to find out if inserting values ​​on the back, not on the front, and then on the inverse vector. (Although I even think that your code is incorrect right now, and your intersectedValues sorted incorrectly. If I am not mistaken, you should use std::back_inserter instead of std::inserter(...,begin) , and then not cancel). through memory rather quickly, and not switching should be even faster.

Answer 3

I can't verify this, but maybe something like this will be faster?

 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; } 

Another possibility:

By thinking about this with swap() , you can optimize data exchange and remove the need for redistribution. In addition, the temp constructor can be moved out of the loop.

 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; } 

Answer 4

Copying elements from vectors from vector to loop using emplace_back () can save you some time. And there is no need for a flag if you change the index of the for for iterator. In this way, the loop can be optimized, and the status check can be removed for each iteration.

 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; } } 

Answer 5

set :: set_intersection can be quite slow for large vectors. It is possible to use to create a similar function that uses lower_bound. Something like that:

 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; } } }