• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
MARS_999

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

18 posts in this topic

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!
0

Share this post


Link to post
Share on other sites
[quote name='SiCrane' timestamp='1340346436' post='4951623']
Time it both ways and find out.
[/quote]
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....
0

Share this post


Link to post
Share on other sites
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?
1

Share this post


Link to post
Share on other sites
A priority_queue is usually just a vector sorted as a heap[sup]1[/sup], [url="http://cplusplus.com/reference/stl/priority_queue/"]according to cpluplus.com[/url]

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.

[sup]1[/sup]heap in this case is not the 'free memory'. It's a form of sorting structure within an array. Edited by Zoomulator
1

Share this post


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

[code]
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....

[/code]

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

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites
[quote name='MARS_999' timestamp='1340375592' post='4951744']
I honestly don't know what you are needing or looking for info on this, it's just a simple insert()...

[code]
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....

[/code]

Not sure what else I can say nothing complex here people....
[/quote]

I might be misinterpreting what you are talking about here, but if you are doing this for [i]object picking[/i], 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 [i]or[/i] 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.
2

Share this post


Link to post
Share on other sites
[quote name='Cornstalks' timestamp='1340346736' post='4951627']
mutlimap and priority_queue are totally different... one uses a mapped [i]key[/i] and [i]value[/i], and the other uses a single [i]value[/i]. Pick the one that fits most naturally with your problem. Don't abuse your toolbox.
[/quote]
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 [url="http://doc.qt.nokia.com/latest/qset.html"]QSet[/url] (value only) being implemented using a [url="http://doc.qt.nokia.com/latest/qhash.html"]QHash[/url] (key value pair). The source is literally:

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

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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
[code]
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());

[/code]

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

Share this post


Link to post
Share on other sites
[quote name='MARS_999' timestamp='1340418789' post='4951899']
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.
[/quote]
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.
0

Share this post


Link to post
Share on other sites
Thanks Cornstalks that worked great! I am now using the vector version you suggested.
0

Share this post


Link to post
Share on other sites
[quote name='MARS_999' timestamp='1340485267' post='4952104']
[code]
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());

[/code]

Is what I was using when I did the priority_queue....
[/quote]
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 [u][i]very clear[/i][/u] 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, [font=courier new,courier,monospace]std::min_element[/font] 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.

[size=1]*generally speaking[/size]

[edit]

Glad to hear it worked well for you [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Edited by Cornstalks
2

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0