Is there something faster than a min heap for my use case?

user_119258 0
Viewed 178

My use case is as follows:

  1. I need to get the minimum of a set of growing elements; I'll only need the minimum for any iteration
  2. I will update the minimum value after which it is guaranteed to no longer be the minimum but its new position in the order is not in general calculable directly.
  3. I push this new value back onto the collection and go to the next iteration where I look at the new min element.

Right now I'm using a std::vector and std::pop_heap std::push_heap in the following way. I call std::pop_heap on my vector which pushes the min element to the back of the vector, I get a reference to the last element and I update it, then I call std::push_heap which moves the last element to its new location. So I don't have to copy the struct out of the std::vector to update it currently. The struct in question is 16 bytes and trivially constructible, its pretty basic consisting entirely of integral types.

According to my profiler and across a range of problem sizes what I'm seeing is that I'm spending >75% of my cpu time in std::pop_heap and ~10% in std::push_heap. Now the logic being performed on each minimum element that gets checked is pretty trivial consisting mostly of additions and a few comparisons to a fixed input so I suppose that it is possible that this is as good as it gets. However if there is a different or random weird data structure that might be faster than the min_heap I'm currently using it would be fun to try out.

I've tried std::min_element, std::nth_element, std::sort each of which takes my current solution times of less than 1 second for a problem size of 1,000,000 or less and increases the run time by orders of magnitude (many 10's of seconds). Which I would expect given that they all have a worse complexity than std::push_heap and std::pop_heap.

I've also tried using tree structures like std::map and std::set but these also degrade performance (I don't have numbers handy right now).

So does anybody know of something better than a min_heap for this use case?

(Unfortunately I can't provide the source code but given that 85% of the cpu time is spent on pop_heap/push_heap I don't think it would be super useful anyways)

Edit: The comparison operator is a single comparison between two integral types. so its not like the comparison operator being used in the heap is doing a massive amount of work.

data-structures c++ performance
1 Answers

Rather than removing the minimum element and reinserting the updated value, you could change the value in-place and down-bubble from the root. Removing the minimum element often replaces it with one of the worst elements to replace the root with, typically costing a long down-bubble, and then reinserting a relatively small value costs a relatively long up-bubble as well. Changing the key in-place replaces both of those taken together with just one down-bubble, which is also typically shorter, as long as the new value stays relatively close to the root on average.

Sadly there is no function for this in <algorithm>, but it's not too difficult to roll your own. Write it in terms of moves into a "hole" left by making a temporary copy of the root, not as a series of std::swaps. Doing it with swaps works out to about double the number of loads and stores in total.

Using a heap of larger arity (probably 4, maybe 8) may help.

user_5550450
Related