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.
what is the best data structure for this?
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.
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.
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.
If you overload operator >, you can set up the comparison to check like this:
(i.e. sort by id first, then by mass if ids are equal)
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)
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.
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.
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement