Sorting units.

[krogothe]

Im having some trouble working this out:
I want to sort units based on a score assigned to them by a function. When a unit is created/destroyed, it is checked for some criteria to see if it is of the right type and then i want it to be added/delete from a list of all units of that type. When a unit is created, it is assigned this score, which never changes as long as the unit is alive.
I want to hold those units in a list, sorted by score, and then get its ID, perform an action to it and remove it from the list while it is doing that action (onto another sorted list of "active" units) and then put it back in the unused list once it done its job.
Since units will be added/removed quite frequently, it would be good if the operation was fast, and since the scores never change its a matter of adding a unit to the right place, kinda like an ordered tree, but to remove units that would be slow.



I could just do this:

Code: Select all

struct unitscore{
float score;
int id;
}
vector<unitscore> myunits;

then do a loop for all units, comparing values for adding and removing, but it seems excessively slow and innefiecient, all i want is a fast way to do that.


Any ideas? (if i sounded too confusing just ask for more detail)

[submarine]

you could use a stl::set

-> sorts its elements automatically which makes acces to a certain element pretty fast (but inserting/deleting slower)

[jcnossen]

or use your own data structure and call std::sort on it. This is quicksort which is fast enough for most things.

[Dragon45]

Hash tables have O(1) (constant) set, get, and remove time, meaning its damn. cheap. assuming you can code the hash function properly. But you couldnt sort as easily, meaning that depending on your particular implmentation, a tree-structure might actually be best as you mentioned O_o

Do not use:

1) Linked List <--- Bad for this case
2) Unwrapped Array <----Not dynamic, you'll have a limited size

I personally wouldn't use a Set [the structure submarine mentioned] because retrieval woudl be fairly slow o_O


Java has something called an ArrayList; not sure if there is a C++ analog to it, but its basically a structure that wraps an array and makes it *appear* dynamic. With an ArrayList you can say something like:

Object retObject = myArrayList.get(5);
retObject.performSomeOperation();
myArrayList.add(retObject);

and it'll get the object at the 6 position, perform an operation on it, then add it to the end of the list. It has O(1) insertion, retrieval, and setting. However, since its core is an array:

it starts off with an array of size N. Then you want to add another objec,t so it Creates a new tempArray with n*2 the storage of the first one, copies over al lthe values fro mthe first one, swaps them, then adds your own value in the new array. It keeps on doubling basically every time you exceed the current storage capacity.

It is very easy to sort stuff and swap stuff around (the operations themselves are transparent to the client program and access, etc.

However, I'm thinkign soem sort of funky cross between an ArrayList and a binary search tree might be best if you need fast searching and setting. Maybe, store the actual values in an ArrayList(), but acess them as if they were in a heap or search tree? ArrayList.position(0) Would be the root, .pos(1) would be the root's left, .pos(2) would be the root's right, etc etc.


Or you could take the easy way out and just use QuickSort like Zaphod mentioned... or MergeSort might be a better choice here since you're working with arrays anyway, and you have guarunteed O(nlogn) time- quicksort degrades to O(N^2) time in worst case.

So my reccomendation would be

1) Design or gank an ArrayList-type structure
2) Mergesort..

[ILMTitan]

Isn't the general equivalent to Java's ArrayList C++'s vector<>? ArrayList deprecated vector in Java itself.

To sort the vector, include <algorithm>.
then call sort(vector name.begin(),vector name.end());
Make sure you have operator<(unitscore lhs, unitscore rhs) defined.

That said, don't use vector<> because it is O(n) on insertion and deletion at places other than the end.

If you only want to get a unit with the highest available score, use stl::priority_queue<>. It has reasonably fast insertion and deletion [O(logn)?], and probably faster for what you want to do.

If you want to be able to get any unit in the structure, or to be able to iterate through the structure, use a set (or a multiset if your scores are not necessarily unique).

In either case, make sure you have < defined for unitscore.

[Tobi]

Code: Select all

struct unitscore{ 
  float score; 
  int id;
  bool operator<(const struct unitscore& other) const {
    return score < other.score;
  }
} 
vector<unitscore> myunits; 

Code: Select all

#include <algorithm>
...
std::sort(myunits.begin(), myunits.end());

[krogothe]

Okay guys, thanks for the info, ill try the different methods! One of the things about it is that 90% of the time only the highest scoring item will be added/removed (and items never get acessed), then put into another similar list of active units, with exactly the same specifications but the lowest score units are the ones removed. If a unit dies/is created, then it needs to be inserted somewhere in the middle, so a priority queue seems to be the way!

Ill give it a go!

[Dragon45]

If most of the time you're counting only on among the top few items being needed/accessed:


Here's another suggestion. Use Selection Sort / Bubble Sort. It's a bit of a shitty algorthim for most applications, but the one thing it does well is find the highest few values in a lsit very, very quickly. There's two FOP loops; if you want to get the 1st highest scoring item, sort it so that the outer FOR loop only goes throuhg 1 iteration, if top two items, then make the outer FOR loop only go through 2 iterations, etc.

Alternatively, you cuold pick / choose sorting/search algorthims based on what you want to acess. If you wat to pick out the highest three items or so, have it call BubbleSort. If you want it to access more than the top 6 or so items, have it call MergeSort or QuickSort.

[ILMTitan]

I have to disagree. To find the top element in an unsorted vector, bubble sort takes O(n) time, where as to find the top element in a priority queue takes O(log(n)) time maximum, which is probably amortized to O(1) time. Adding in the O(log(n)) time to add elements to the queue, vs O(1) time to add elements to a vector, the queue is still only O(log(n)) vs O(n) for the vector. Getting the first m elements, the queue is O(m*log(n)) vs O(m*n) for the vector.

In conclusion, to find the top element, or top m elements, bubble sort is not terrible, but priority queue is still better.

[krogothe]

You know, if we got each of the kickass programmers in the spring community to do just ONE HOUR a week on developing it supcom would seem like a petty spring clone after just a few weeks!

[jcnossen]

Somehow I doubt that

[krogothe]

a few hundred man hours, especially when focused could do shitloads of work. Completely finishing KAI is one of them, maybe the GUI or a couple of mods, plus im fairly confident supcom is just hype over an average game.

[Dragon45]

Meh, if I could be assed to devote an hour a day to make Spring better, I walready woudl have done it.


<---- Is a distracted fellow; lets his pet programming projects rot




*runs after female friend who just dumped her boyfriend*



Seeya in a few, ya'll