Stack - Removing an entry fast?
Monkey Forums/Monkey Programming/Stack - Removing an entry fast?
| ||
| Hi folks, I am trying to speed up my engine a little. So far I am using Lists because they are easy to maintain and the buildin sorting feature is just priceless. Plus removing an entry via its node is also very very fast. But iterating through a list is slower than a stack. But there is no sorting and removing is only possible via its index, push or RemoveEach. As the content of the stack is dynamic, and the stack index of an object WILL change during its lifetime, I see only using RemoveEach to remove it. Or did I miss something? Some people say "use arrays". But there are only quicl to iterate. Removeing an entry inbetween or sorting doesn't play well when you have a load of objects that are dynamically created and removed. So, I see only stacks here. Or? |
| ||
| You are right. Stack operations are only fast O(1) for the last added element. Removing a deeper element results in copying the other elements. You could use maps where the key is the index. They are pretty fast. |
| ||
| Mmmh, my tests show that iterating through a map and removing an item from a map is actually slower than from a list. Iterating through a stack is as fast as an array. But removing is damn slow. I wish it had some kind of node to it. Will try my own linked object list. |
| ||
| You pays your money and you takes your choice. The reason all these collection classes exist is that no type is good for everything. One option is to use an array or stack, but instead of removing items, just mark them dead. You can re-use the dead ones (if order doesn't matter) or else just reallocate everything when it grows too large. In a lot of cases (where objects last a long time and are not frequently added) this can be an effective solution. If you intend the stack index of an object to change during its lifetime, you are probably using the wrong type of collection, and a list would be better. |
| ||
| I agree with you but.... the problem is, the order matters. It is either lists or running something on my own. |
| ||
| Iterating through a stack is as fast as an array. But removing is damn slow. i wonder if you could write a 'stack garbage collector' for the stack. In other words, leave holes in the stack as Null "stack.Set(i,null)", then at the end of a render cycle, go through the stack and add any non-nulls to a new stack. Make sure to use a 'something was removed' flag to prevent iteration each cycle. You could even set a threshold for say, if more than 10 objects were removed. |
| ||
| Not sure if that would help the GC problem on android when you iterate through a collection (list), or? |
| ||
well, don't know if iteration creates a lot of GC overhead since Enumerator creates no new objects, but if you want, you could get a little primitive and use nodes to cycle through a list yourself.Local node:Node<MyClass> = list.FirstNode() While node ''do stuff node = node.NextNode() Wend |
| ||
| @AdamRedwoods: i wonder if you could write a 'stack garbage collector' for the stack. In other words, leave holes in the stack as Null "stack.Set(i,null)", then at the end of a render cycle, go through the stack and add any non-nulls to a new stack. Diddy's ArrayPool class already does something similar to this, swapping elements around to fill the holes. Unfortunately this makes it unordered. https://code.google.com/p/diddy/source/browse/src/diddy/collections.monkey |
   |