Geek Answers Handbook

Integer Combination Speed ​​Dial

I need to make many unions of an ordered set of integers (I would like to avoid duplicates, but this is normal, if any).

This is the code with the best performance:

// some code added for better understanding std::vector< std::pair<std::string, std::vector<unsigned int> > vec_map; vec_map.push_back(std::make_pair("hi", std::vector<unsigned int>({1, 12, 1450}); vec_map.push_back(std::make_pair("stackoverflow", std::vector<unsigned int>({42, 1200, 14500}); std::vector<unsigned int> match(const std::string & token){ auto lower = std::lower_bound(vec_map.begin(), vec_map.end(), token, comp2()); auto upper = std::upper_bound(vec_map.begin(), vec_map.end(), token, comp()); std::vector<unsigned int> result; for(; lower != upper; ++lower){ std::vector<unsigned int> other = lower->second; result.insert(result.end(), other.begin(), other.end()); } std::sort(result.begin(), result.end()); // This function eats 99% of my running time return result; }

valgrind (using the callgrind tool) tells me that I spend 99% of the time doing sorting.

This is what I have tried so far:

  • Using std :: set (very poor performance)
  • Using std :: set_union (poor performance)
  • saving heap with std :: push_heap (50% slower)

Is there any hope of getting some kind of performance? I can change my containers and use boost and maybe some other libs (depending on its license).

EDIT integers can be like 10,000,000 EDIT 2 gave an example of how I use it, due to some confusion

+4
source share
5 answers

Custom merge sorting might give a little help.

 #include <string> #include <vector> #include <algorithm> #include <map> #include <iostream> #include <climits> typedef std::multimap<std::string, std::vector<unsigned int> > vec_map_type; vec_map_type vec_map; struct comp { bool operator()(const std::string& lhs, const std::pair<std::string, std::vector<unsigned int> >& rhs) const { return lhs < rhs.first; } bool operator()(const std::pair<std::string, std::vector<unsigned int> >& lhs, const std::string& rhs) const { return lhs.first < rhs; } }; typedef comp comp2; std::vector<unsigned int> match(const std::string & token){ auto lower = std::lower_bound(vec_map.begin(), vec_map.end(), token, comp2()); auto upper = std::upper_bound(vec_map.begin(), vec_map.end(), token, comp()); unsigned int num_vecs = std::distance(lower, upper); typedef std::vector<unsigned int>::const_iterator iter_type; std::vector<iter_type> curs; curs.reserve(num_vecs); std::vector<iter_type> ends; ends.reserve(num_vecs); std::vector<unsigned int> result; unsigned int result_count = 0; //keep track of current position and ends for(; lower != upper; ++lower){ const std::vector<unsigned int> &other = lower->second; curs.push_back(other.cbegin()); ends.push_back(other.cend()); result_count += other.size(); } result.reserve(result_count); //merge sort unsigned int last = UINT_MAX; if (result_count) { while(true) { //find which current position points to lowest number unsigned int least=0; for(unsigned int i=0; i< num_vecs; ++i ){ if (curs[i] != ends[i] && (curs[least]==ends[least] || *curs[i]<*curs[least])) least = i; } if (curs[least] == ends[least]) break; //push back lowest number and increase that vectors current position if( *curs[least] != last || result.size()==0) { last = *curs[least]; result.push_back(last); } ++curs[least]; } } return result; } int main() { vec_map.insert(vec_map_type::value_type("apple", std::vector<unsigned int>(10, 10))); std::vector<unsigned int> t; t.push_back(1); t.push_back(2); t.push_back(11); t.push_back(12); vec_map.insert(vec_map_type::value_type("apple", t)); vec_map.insert(vec_map_type::value_type("apple", std::vector<unsigned int>())); std::vector<unsigned int> res = match("apple"); for(unsigned int i=0; i<res.size(); ++i) std::cout << res[i] << ' '; return 0; }

http://ideone.com/1rYTi

+1
source

This is like an instance of multi-threaded merge . Depending on the input (profile and time!), The best algorithm may be that you have or something that creates the result step by step, by choosing the smallest integer from all the containers or something more complex.

+2
source

ALTERNATIVE DECISION :

The std :: sort method (if it is based on quick sorting) is a very good sorting of unsorted vectors O (logN), even better with a sorted vector, but if your vector is inverted, then it has O (N ^ 2). It may happen that when you perform a join, you have many operands, the first of which contains more values ​​than the followers.

I would try the following (I assume that the elements from the input vectors are already sorted):

  • As suggested by other people, you should update the required size by the results vector before filling it out.

  • In the case of std :: distance (lower, upper) == 1 there is no reason to combine, just copy the contento of one operand.

  • Sorting the operands of your union, possibly by size (larger first), or if the ranges do not overlap or partially overlap only by the first value), so that you maximize the number of elements that are already sorted in the next step. Probably the best is a strategy that takes into account both SIZE and RANGE of each operand of your union. Much depends on real data.

  • If there are several operands with many elements each, add elements on the back of the result vector, but after adding each vector (from the second) you can try to combine (std :: inplace_merge) the old content with the addition, this also deduplicates the elements for you.

  • If the number of operands is large (compared to the total number of elements), you should stay with the same sorting strategy after that, but call std :: unique to deduplicate after sorting. In this case, you should sort by the range of elements contained.

+1
source

If the number of elements is a relatively large percentage of the range of possible int s, you can get decent performance from the fact that a "hash join" is essentially simplified (use database terminology).

(If there is a relatively small number of integers compared to the range of possible values, this is probably not the best approach.)

Essentially, we create a gigantic bitmap, then set the flags only by the indices corresponding to the int input, and finally restore the result based on these flags:

 #include <vector> #include <algorithm> #include <iostream> #include <time.h> template <typename ForwardIterator> std::vector<int> IntSetUnion( ForwardIterator begin1, ForwardIterator end1, ForwardIterator begin2, ForwardIterator end2 ) { int min = std::numeric_limits<int>::max(); int max = std::numeric_limits<int>::min(); for (auto i = begin1; i != end1; ++i) { min = std::min(*i, min); max = std::max(*i, max); } for (auto i = begin2; i != end2; ++i) { min = std::min(*i, min); max = std::max(*i, max); } if (min < std::numeric_limits<int>::max() && max > std::numeric_limits<int>::min()) { std::vector<int>::size_type result_size = 0; std::vector<bool> bitmap(max - min + 1, false); for (auto i = begin1; i != end1; ++i) { const std::vector<bool>::size_type index = *i - min; if (!bitmap[index]) { ++result_size; bitmap[index] = true; } } for (auto i = begin2; i != end2; ++i) { const std::vector<bool>::size_type index = *i - min; if (!bitmap[index]) { ++result_size; bitmap[index] = true; } } std::vector<int> result; result.reserve(result_size); for (std::vector<bool>::size_type index = 0; index != bitmap.size(); ++index) if (bitmap[index]) result.push_back(index + min); return result; } return std::vector<int>(); } void main() { // Basic sanity test... { std::vector<int> v1; v1.push_back(2); v1.push_back(2000); v1.push_back(229013); v1.push_back(-2243); v1.push_back(-530); std::vector<int> v2; v1.push_back(2); v2.push_back(243); v2.push_back(90120); v2.push_back(329013); v2.push_back(-530); auto result = IntSetUnion(v1.begin(), v1.end(), v2.begin(), v2.end()); for (auto i = result.begin(); i != result.end(); ++i) std::cout << *i << std::endl; } // Benchmark... { const auto count = 10000000; std::vector<int> v1(count); std::vector<int> v2(count); for (int i = 0; i != count; ++i) { v1[i] = i; v2[i] = i - count / 2; } std::random_shuffle(v1.begin(), v1.end()); std::random_shuffle(v2.begin(), v2.end()); auto start_time = clock(); auto result = IntSetUnion(v1.begin(), v1.end(), v2.begin(), v2.end()); auto end_time = clock(); std::cout << "Time: " << (((double)end_time - start_time) / CLOCKS_PER_SEC) << std::endl; std::cout << "Union element count: " << result.size() << std::endl; } }

Will print ...

 Time: 0.402

... in my car.

If you want to get your int input from something other than std::vector<int> , you can implement your own iterator and pass it to IntSetUnion .

0
source

You sort integers with a limited range, this is one of those rare cases where you can use radix sorting . Unfortunately, the only way to find out if this is superior to the generalized view is to try it.

0
source

More articles:


All Articles