Quote:
|
Originally Posted by Valtin
Regarding the original proposition of faster access to the EntityList - I've not looked at the code for too long but it seems there is a lot of commitment in terms of coding/time/learning invested in the existing structure, it would be painful to discard that.
|
I'm not convinved that there is a definite need to optimize yet (which explains why I haven't implemented/suggested code changes). OTOH, changing list<> to set<> wouldn't be so very difficult. The container is already built into the language, and the semantics are almost identical. The base entity would only need to implement some sort of arbitrary comparison operation.
Quote:
|
Short lists are as wasteful as long ones in time terms.
|
*brushes off his math books* Actually, for element searches like the ones Trump mentioned at the beginning of the thread, your statement is exactly opposite the truth. Searching unsorted linked-lists is an O(n) operation. That means that the cost goes up in step with the size of elements. Using an stl set (which is implemented w/ a red-black binary search tree) would reduce search time to O(logn). As you can see, the difference for small n is negligable. So, to make a long story short - short lists are not as wasteful as long ones.
Quote:
|
One way of handling even breaking up of long lists where you have a quickly accessible int based ID is just to use a hashtable structure over the linked lists.
|
I fully agree. Hashtables are sexy. An item search in a hash table drops down to O(1) time - it doesn't matter how many items you store. The bad news is that ANSI C++ doesn't yet include a hash-table container (although they are currently considering proposals). Most compilers still contain some form of hashmap, but I find them hard to recommend for cross-platform solutions.
Quote:
|
From your timings it doesn't look as though this aspect is *that* time critical though. Just offering this up as an idea for consideration in case you do need to address the list problem.
|
I agree. My time is better spent adding/improving functionality at this point.