Quote:Original post by ToohrVyk

Quote:Original post by Woodchuck
damn i really don't remember it, but this is well known your respect apart. A computer can't say : this function will loop infinitly. It can only say, this function stop on input n ^^ (since it don't loop infinitly for saying it)

It is known, but as a matter of fact my question was a rhetorical one.

I suspected it =)

EDIT : ok i understand what you want to show me ^^

[Edited by - Woodchuck on March 9, 2006 12:34:16 PM]

Quote:Original post by CGameProgrammer
Um, the obvious solution is a linked list, not an array. Look up "linked list". A better solution is a linked list of arrays, since that's faster. You know, something like....

This combines the advantages of a linked list (infinite size) with the advantages of an array (speed).

As was mentioned before, linked lists are not infinite. This is a silly notion when talking about a computer data structure. But I know what you meant :).

Also, with a linked list you cannot access by index which means that the time to access a particular unit grows linearly as the number of units grows rather than staying constant. Since this is a discussion about designing a game with large unit counts, this property is bad. If you had a list of 44000 units and you wanted to carry out some operation on the last one, you could directly access it if it were stored in an array, whereas with a linked list you would have to search through every element of the list until you found the unit you were looking for. So, in the average case (using the term "average" somewhat loosely) you would have an overhead of searching through 20,000 (n/2) list elements before you could carry out your operation (whereas with an array you could do it without this overhead).

So, it is not obvious that the solution is a linked list (or even a deque for that matter) - in fact I think that's a terrible idea. If you want to be fast and you want a high unit count, just allocate a large enough chunk of memory for your array that it will easily hold the maximum number of units that the other pieces of your engine can handle. If, as you said, memory is not the issue, why make it any more complex than it needs to be by using a list or a deque? Both will increase your access time as the number of units increases, and they're both less efficient in terms of memory usage, and with good planning and design you could still use an array and get the same benefits that the list/deque would have afforded you without taking the hits.

One must be careful when he tosses around a word like "faster" with regard to data structures.