Jump to content

  • Log In with Google      Sign In   
  • Create Account


Which is faster? std::priority_queue or std::multimap


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
18 replies to this topic

#1 MARS_999   Members   -  Reputation: 1240

Like
0Likes
Like

Posted 22 June 2012 - 12:18 AM

I am using a std::multimap to do my sorting of my objects that get picked... I was using std::priority_queue but seems like a waste when std::multimap already does a < comparison when inserting the objects... So would it be faster still to use std::priority_queue?

Thanks!

Sponsor:

#2 SiCrane   Moderators   -  Reputation: 9418

Like
4Likes
Like

Posted 22 June 2012 - 12:27 AM

Time it both ways and find out.

#3 Cornstalks   Crossbones+   -  Reputation: 6966

Like
4Likes
Like

Posted 22 June 2012 - 12:32 AM

mutlimap and priority_queue are totally different... one uses a mapped key and value, and the other uses a single value. Pick the one that fits most naturally with your problem. Don't abuse your toolbox.
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#4 MARS_999   Members   -  Reputation: 1240

Like
0Likes
Like

Posted 22 June 2012 - 12:32 AM

Time it both ways and find out.

Thanks for the reply, but I was more or less wondering if this was a common knowledge situation... Just seems logical that since it's already been done it would be a waste to run it again....

#5 SiCrane   Moderators   -  Reputation: 9418

Like
1Likes
Like

Posted 22 June 2012 - 12:35 AM

How would it be common knowledge when you don't bother to mention things like what kind of objects you're storing, what usage pattern you have, what the relative cost of comparisons and assignments are, and so on?

#6 MARS_999   Members   -  Reputation: 1240

Like
0Likes
Like

Posted 22 June 2012 - 12:52 AM

A pointer and a double... less than operator

#7 Cornstalks   Crossbones+   -  Reputation: 6966

Like
3Likes
Like

Posted 22 June 2012 - 01:00 AM

A pointer and a double... less than operator

I'll go ahead and reiterate what I said... You can't just swap priority_queue and multimap in and out for each other, as there are major design differences between the two. If you need a multimap, use a multimap. If you need a priority queue, use a priority_queue. If you're using a priority_queue when you need a multimap, or if you're using a multimap when all you need is a priority_queue, You're Doing It WrongTM.

It's like asking which is faster: an apple or an orange?

Now, if you gave some greater context as to what it is you're trying to accomplish, there just might be a definitive answer for you (that is best both design wise and speed wise).

Edited by Cornstalks, 22 June 2012 - 06:13 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#8 Zoomulator   Members   -  Reputation: 269

Like
1Likes
Like

Posted 22 June 2012 - 04:19 AM

A priority_queue is usually just a vector sorted as a heap1, according to cpluplus.com

The map is sorted with an RB tree, containing nodes swimming in memory.

I can't give you exact performance comparisons (you'd really have to do that yourself), but there's a few things to say about vector and map (or list).

A vector gives a consistent memory block, which helps a lot with the speed of fetching if it's used much. Maps and lists have an extra pointer, which means the node is anywhere in memory and most likely not already in cache unless its very recently used.

A priority queue got to maintain the heap however, but once sorted the first time, this is a fairly small operation. Usually faster than the cycles required to fetch a map node on a cache miss!

But as earlier posters say.. they are for different purposes and you should simply chose what's right for the job.

1heap in this case is not the 'free memory'. It's a form of sorting structure within an array.

Edited by Zoomulator, 22 June 2012 - 04:22 AM.


#9 saejox   Members   -  Reputation: 714

Like
4Likes
Like

Posted 22 June 2012 - 06:48 AM

i think oranges are faster than apples

#10 MARS_999   Members   -  Reputation: 1240

Like
-4Likes
Like

Posted 22 June 2012 - 08:33 AM

I honestly don't know what you are needing or looking for info on this, it's just a simple insert()...

pickedObjects.insert(double, Obj*); //Obj*just an address not new'd
//later on
pickedObjects.begin()->first to check the dist
pickedObjects.being()->second to assign that pointer to selected object....


Not sure what else I can say nothing complex here people....

#11 phantom   Moderators   -  Reputation: 6804

Like
1Likes
Like

Posted 22 June 2012 - 09:21 AM

It's not just the insert which matters, it is the whole scope of how you plan to use this data structure as different structures have different charactristics depending on what you are going to do.

If you are looking up lists of data based on a common key then multimap might give you the best performance as it is designed for fast lookups.

On the other hand if you just want a list of data you can iterate over from first to last then something which allocates contiguous memory as a backing store will be faster (think std::vector)

It all comes down to usage pattern, without knowing that you can't make an informed choice as to what container you should use.

#12 SHilbert   Members   -  Reputation: 647

Like
2Likes
Like

Posted 22 June 2012 - 04:01 PM

I honestly don't know what you are needing or looking for info on this, it's just a simple insert()...

pickedObjects.insert(double, Obj*); //Obj*just an address not new'd
//later on
pickedObjects.begin()->first to check the dist
pickedObjects.being()->second to assign that pointer to selected object....


Not sure what else I can say nothing complex here people....


I might be misinterpreting what you are talking about here, but if you are doing this for object picking, like having the user click in a window to select an object, and you only ever need to know the single object with the smallest distance, you don't need a priority_queue or a multimap. You just need to remember the currently closest object and its distance, and update those values if you find an even closer one.

Again, not sure if that is your use case, though.

#13 Slavik81   Members   -  Reputation: 360

Like
0Likes
Like

Posted 22 June 2012 - 06:44 PM

mutlimap and priority_queue are totally different... one uses a mapped key and value, and the other uses a single value. Pick the one that fits most naturally with your problem. Don't abuse your toolbox.

That's not really all that fundamentally different. The difference between sorting by key and sorting by value is simply that in the latter case, your key is a part of your value. The former is a more general case of the latter.

Hence why you see things like QSet (value only) being implemented using a QHash (key value pair). The source is literally:

template <class T>
class QSet
{
	typedef QHash<T, QHashDummyValue> Hash;
///...
private:
	Hash q_hash;
};

QHash then relies on some specializations in choosing the node type to save memory, but even if it didn't the worst that could happen is that you'd use a little more memory to store each object. If that saved the developer the time of building and maintaining a completely new data structure with the desired performance characteristics, and if you had memory to spare, then nothing of value was lost.

There are other differences between multimap and priority_queue, but the fact that one is key/value and the other is value-only is not enough to say that one would be a natural fit and that the other would not. I think the expected read and write patterns are far more important.

Edited by Slavik81, 22 June 2012 - 06:45 PM.


#14 MARS_999   Members   -  Reputation: 1240

Like
0Likes
Like

Posted 22 June 2012 - 08:33 PM

Well so far from what I can determine, the std::multimap is faster when I start adding lots of objects. If one a few about the same.

Say player clicks on object and camera is at an angle where their could be 10 objects in a line one behind each other when doing the ray test, this shouldn't happen very often but seeing what I see so far, I am switching to the multimap version.

#15 Cornstalks   Crossbones+   -  Reputation: 6966

Like
3Likes
Like

Posted 23 June 2012 - 10:03 AM

Say player clicks on object and camera is at an angle where their could be 10 objects in a line one behind each other when doing the ray test, this shouldn't happen very often but seeing what I see so far, I am switching to the multimap version.

You mean something like:
bool compare(const std::pair<double, Obj*>& left, const std::pair<double, Obj*>& right)
{
    return left.first < right.first;
}

// Assuming you have an unsorted container of std::pair<double, Obj*> objects (like a std::vector)
std::vector<std::pair<double, Obj*> >::iterator min = std::min_element(myList.begin(), myList.end(), compare);

This code is O(n), even if you completely clear your vector every update. Using multimap or priority_queue is O(nlogn), assuming you clear them every update. However, taking SHilbert's advice into account, you can do the min tracking yourself (which is still O(n), but should require one or two less iterations over the container and book keeping required by the container, and thus potentially slightly more efficient than the above code).

*snip*

Yes, there are major differences between multimap and priority_queue in addition to the key/value thing. However, in that post I wasn't pointing out how different they are to implement, I was pointing out how different they are to use. Idiomatic uses of key/value maps or just value containers are quite different. And yes, you could abuse your toolbox and use them in a fairly similar manner (though not totally the same) with a couple unwieldy tricks, but I specifically advised against that. Proper use of these containers is quite different, because you use them in quite different situations.

Edited by Cornstalks, 23 June 2012 - 10:20 AM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#16 MARS_999   Members   -  Reputation: 1240

Like
0Likes
Like

Posted 23 June 2012 - 03:01 PM

struct GreaterSecond : std::binary_function<T, T, bool>
{
    inline bool operator()(const T& lhs, const T& rhs)
    {
        return lhs.second > rhs.second;
    }
};

typedef std::pair<NX::Object*, double> data_t;
typedef std::priority_queue<data_t, std::deque<data_t>, NX::Utility::GreaterSecond<data_t>> queue_t;
queue_t q(pickObjects.begin(), pickObjects.end());
 

Is what I was using when I did the priority_queue....

#17 SHilbert   Members   -  Reputation: 647

Like
0Likes
Like

Posted 23 June 2012 - 03:05 PM

Well so far from what I can determine, the std::multimap is faster when I start adding lots of objects. If one a few about the same.

Say player clicks on object and camera is at an angle where their could be 10 objects in a line one behind each other when doing the ray test, this shouldn't happen very often but seeing what I see so far, I am switching to the multimap version.

If your worst case is literally finding the closest of a list of 10 objects once per frame, you could do anything and it would be fast. :)

On the other hand, if you can rule out raycasts before even doing them, that is definitely worth doing. Like, if you know that your closest object had a distance of 6 meters, and you get to an object where the distance from the camera to the surface of its bounding sphere is 7 meters, you don't have to do any ray casts vs. its geometry at all, you can just throw it out.

#18 MARS_999   Members   -  Reputation: 1240

Like
0Likes
Like

Posted 23 June 2012 - 03:24 PM

Thanks Cornstalks that worked great! I am now using the vector version you suggested.

#19 Cornstalks   Crossbones+   -  Reputation: 6966

Like
2Likes
Like

Posted 23 June 2012 - 03:25 PM

struct GreaterSecond : std::binary_function<T, T, bool>
{
	inline bool operator()(const T& lhs, const T& rhs)
	{
		return lhs.second > rhs.second;
	}
};

typedef std::pair<NX::Object*, double> data_t;
typedef std::priority_queue<data_t, std::deque<data_t>, NX::Utility::GreaterSecond<data_t>> queue_t;
queue_t q(pickObjects.begin(), pickObjects.end());


Is what I was using when I did the priority_queue....

Which isn't just a simple insert... (because it's not an insert at all)

Really though, it would be very helpful if you were very clear on exactly what it is you're trying to do, and how you've tried to do it so far. You can't expect anyone to give you any meaningful help if you ask a question without much detail, then say it's X (just a simple insert), and then show us you've been doing Y (that's not an insert).

Optimizations aren't general. They're specific.* The fact that you're using the constructor to insert a range of things and not inserting them one by one makes a huge difference (by the way, the code you posted is O(n), with at most 3n comparisons being done, which isn't too bad). It shows that you a) already have the objects in an accessible, iteratable (is that a word?) data structure, b) either you only care about the top element, c) or maybe you just care about iterating through them in specific order. Your optimal solution depends on how many objects you're picking, how many objects you're picking from, what data structure these objects are stored in, how their distance is calculated, whether or not results can be reused, and even more details. None of which you've answered. Details are vital here, and so far all of your posts have been <= 3 sentences long.

If you're only picking one object, std::min_element will be up to ~3 times faster than your priority queue. If you're only picking from a few objects, you're probably optimizing the wrong thing.

*generally speaking

[edit]

Glad to hear it worked well for you Posted Image

Edited by Cornstalks, 23 June 2012 - 03:30 PM.

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS