1

I have a game loop which draws a list of objects, the list called "mylist" and holds something like 1000 objects, objects(especially bullets which fly fast and hit things) needs to be added and removed from the list constantly, few objects every second.

If i understand correctly the insert in List is practically free if the list capacity large enough, the problem is with removal which is O(n) because first of all i need to find the item in the list , and second it creates a new list after the removal.

If i could aggregate all the removals and make them once per frame, it would be efficient because i would use mylist.Except(listToRemove) and this would be in O(n). but unfortunately i can't do it.

Linked list is also problematic because i need to find the Object in the list.

Any one has better suggestion ?

OopsUser
  • 4,642
  • 7
  • 46
  • 71
  • Is this all theoretical, or are actually experiencing problems? 1000 objects is not all that big, so I am surprised to hear about performance issues for that size. I mean, did you actually profile and find this to be the bottleneck? – Oded Mar 23 '13 at 14:27
  • @Oded processing 1000 objects quadratically is ~ 500k operations. This is no longer a trivial cost. – usr Mar 23 '13 at 14:29
  • It's theoretical, but it's more then that, it feels wrong to write a code that is so inefficient. – OopsUser Mar 23 '13 at 14:30

4 Answers4

3

What about a HashSet? It supports O(1) insert and removal. If you need ordering, use a tree data structure or a LinkedList plus a Dictionary that allows you to find nodes quickly.

The BCL has a SortedList and a SortedSet and a SortedDictionary. All but one were very slow but I can never remember which one was the "good" one. It is tree-based internally.

usr
  • 168,620
  • 35
  • 240
  • 369
0

If you are doing searching then your best bet is to use either a Dictionary that has average case of O(1) and worst case of O(n) (when you hash to the same bucket).

If you need to preserve order you can use any implentation of a balanced binary search tree and your performance will be O(logn).

In .NET this simply comes down to

Dictionary - Insertion/Removal O(1) (average case)

SortedDictionary - preserves order for ordered operations, insertion/removal O(logn)

Stan R.
  • 15,757
  • 4
  • 50
  • 58
0

So ideally you would want to use a data structure that has O(1) or O(log n) remove and insert. A dictionary-type data structure would probably be ideal due to their constant average-case insert and delete time complexity. I would recommend either a HashSet and then overriding GetHashCode() on your game object base class.

Here is more details on all the different dictionary/hash table data structures.

Time complexity

Here are all the 'dictionary-like' data structures and their time-complexities:

Type              Find by key  Remove      Add
HashSet           O(1)*        O(1)*     O(1)**
Dictionary        O(1)*        O(1)*     O(1)**
SortedList        O(log n)     O(n)      O(n)
SortedDictionary  O(log n)     O(log n)  O(log n)

* O(n) with collision
** O(n) with collision or when adding beyond the array's capacity.

HashSet vs Dictionary

The difference between a HashSet and a Dictionary is that a Dictionary works on a KeyValuePair whereas with a HashSet the key is the object itself (its GetHashCode() method).

SortedList vs SortedDictionary

You should only consider these if you need to maintain an order. The difference is that SortedDictionary uses a red-black tree and SortedList uses sorted arrays for its keys and values.

References

Community
  • 1
  • 1
Daniel Imms
  • 47,944
  • 19
  • 150
  • 166
0

Performance-wise, you'll probably see the best results by simply not inserting or removing anything from any kind of list. Allocate a sufficiently large array and tag all your objects with whether they should be rendered or not.

Given your requirements, however, this is all probably premature optimisation; you could very well re-create the entire list of 1000 elements 30 times per second and not see any performance drop.

I suggest reading the slides of this presentation given by Braid's creator, on using the right data structures in independent video games: http://the-witness.net/news/2011/06/how-to-program-independent-games/ (tl;dr just use arrays for everything).

Asik
  • 21,506
  • 6
  • 72
  • 131