Jump to content
  • Advertisement
Sign in to follow this  
heron3d

what is the best data structure for this?

This topic is 2828 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'd like to sort my objects according to their value. What would be the best data structure for this. Speed is of the essence. For example, I have 300 spheres class objects that have differing mass and unique id numbers. I'd like to sort them heaviest first while retaining their other properties intact.

I've been looking at binary search trees but that data structure seems to be better suited for finding objects rather than arranging them.

Share this post


Link to post
Share on other sites
Advertisement
I don't think you even need a data structure. Assuming you're using C++, you can just write a custom greater than (or less than) function and call std::sort with a pointer to your function.

Share this post


Link to post
Share on other sites
You could just add them to an array or std::vector and sort them with qsort or std::sort with the appropriate comparison operator. Iterating through the array would be very fast since its elements are contiguous in memory. Sometimes the simplest things are the best. :)

Share this post


Link to post
Share on other sites
thanks for the reply guys. I will look into std::sort. Would it sort only my values or is there a way to sort the id numbers according to their mass values? I need to access the spheres by their id values in the order that the std::sort produces using the objects' mass value.

Share this post


Link to post
Share on other sites
If you overload operator >, you can set up the comparison to check like this:


if(id == rightoperand.id)
{
return mass > rightoperand.mass;
}
else
{
return id > rightoperand.id;
}


(i.e. sort by id first, then by mass if ids are equal)

Share this post


Link to post
Share on other sites
It sounds like you're trying to do two competing things almost -- at least if you want to do both fast lookup by ID as well as sorted values. Are the IDs fixed, or can you assign the ids such that the smallest ID corresponds to the object with the least mass? if so, that would help tremendously.

If you can't reassign IDs, then you probably will want to have a sorted array, as suggested earlier, along with a second array containing a structure of the ID plus a pointer/index into the first array. You sort this second array by ID instead of weight, so then you can do a binary search by ID on the second array, and use the pointer/index to jump into the first array. This will give you logarithmic (O log(n) lookup by ID number, rather than linear (O(n)) and still allows you to sort the first array based on mass. You could also use a hash-map -- its a bit more complicated to set up, but would give constant (O(1)) lookup times.

If you are free to assign the smallest ids to the least massive objects, then you can do so and get Olog(n) lookup by either mass or ID with a single array.

Also, are the 300 data points known up-front, or is this something you build up over time? Does you ever insert/delete these values? If so, then you probably do want a different data structure.

finally, the actual sorted order doesn't usually matter, because you can always walk the array backwards. As long as the list is sorted one way or another you can do a binary search on it with the appropriate comparison operator.

Share this post


Link to post
Share on other sites

It sounds like you're trying to do two competing things almost -- at least if you want to do both fast lookup by ID as well as sorted values. Are the IDs fixed, or can you assign the ids such that the smallest ID corresponds to the object with the least mass?

Thank you for the great response.
Spheres are created spontaneously at runtime and the ids are fixed and sequential in the order in which the sphere objects are created but the mass is assigned based on the conditions of the moment (infinitesimal chance of two spheres having same mass). Once a sphere is created it is not destroyed so there is no need to reassign ids.

What I would like to be able to do is choose any one of the spheres using the unique id number and know how it is graded according to mass relative to all the existing spheres. Once a new sphere is created I would need to update the sorted list.

Example:

sphere id 0 has Mass = 3.2
sphere id 1 has Mass = 20.2
sphere id 2 has Mass = 3.9
sphere id 3 has Mass = 1.1
sphere id 4 has Mass = 0.0000000001
sphere id 5 has Mass = 36848494.2
sphere id 6 has Mass = 5.4
sphere id 7 has Mass = 8.2

I would like to have an array containing the id numbers sorted according to their mass value.

[0] = id 4 because it is the lightest
[1] = id 3
[2] = id 0
[3] = id 2
[4] = id 6
[5] = id 7
[6] = id 1
[7] = id 5 because it is the heaviest


If you can't reassign IDs, then you probably will want to have a sorted array, as suggested earlier, along with a second array containing a structure of the ID plus a pointer/index into the first array.

that would be great



You sort this second array by ID instead of weight,

I get lost here. Is std::sort capable of this?



so then you can do a binary search by ID on the second array, and use the pointer/index to jump into the first array. This will give you logarithmic (O log(n) lookup by ID number, rather than linear (O(n)) and still allows you to sort the first array based on mass. You could also use a hash-map -- its a bit more complicated to set up, but would give constant (O(1)) lookup times.

Share this post


Link to post
Share on other sites
So, the sense I'm getting here is that the ids don't really matter until some point *after* the entire list of spheres is created, correct? For example, one sphere in the list doesn't refer to any other.

What I would do, then, is generate all the spheres without ids (or with a default id, if necessary) -- then sort the list by mass and assign the ids afterwards, sequentially through the list. Actually, it sounds like you might not even really need IDs if this is the case, because the index into the array could serve as the id. If there are persistance issues, then this may not be possible, but its sounding more and more like the IDs are a solution in search of a problem.

Share this post


Link to post
Share on other sites

So, the sense I'm getting here is that the ids don't really matter until some point *after* the entire list of spheres is created, correct? For example, one sphere in the list doesn't refer to any other.

What I would do, then, is generate all the spheres without ids (or with a default id, if necessary) -- then sort the list by mass and assign the ids afterwards, sequentially through the list. Actually, it sounds like you might not even really need IDs if this is the case, because the index into the array could serve as the id. If there are persistance issues, then this may not be possible, but its sounding more and more like the IDs are a solution in search of a problem.


the ids are inherent to the obj. When a sphere is created it is placed in an array. So the id is really the index. I could do a sort on all the mass values to get the heaviest and lightest and then do something like this:
sphere grade = mass/(heaviest mass - lightest mass). This would give me a grade relative to the other spheres but it would not tell me if there are 3, 4 or 346 spheres that are lighter or heavier than the sphere in question. Unfortunately for my puzzle, I need to know how many spheres are lighter and heavier.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!