List iteration in reverse order.

[Richard BetsonParticipant]

Hi,

I noticed that the Backwards() ( my_list.Backwards() ) property for lists is not in Monkey 2. Is there an alternative? I need to iterate though a list in reverse order.

Thanks.

Edit- I should have probably posted this in general programming discussion. Getting used to the new digs.

[Mark SiblyKeymaster]

Not yet, but will add it for V1.0.

 

[Richard BetsonParticipant]

Right on. I’ll use a workaround for now. Thanks.

[Mark SiblyKeymaster]

Actually, something like this should work for now:

1С (Запрос)

Local node:=list.Lastnode While node<>list.HeadNode Local value:=node.Value 'do something with value node=node.Pred Wend

1 2 3 4 5 6 7 8 9

Local node:=list.Lastnode While node<>list.HeadNode    Local value:=node.Value      'do something with value      node=node.Pred Wend

It’s a little nasty as it depends on how List is implemented…

Backwards() will still be happening though so you could just wait for that.

Also…don’t use lists if you can avoid it, as they’re much slower to iterate through than a stack.

 

[Richard BetsonParticipant]

I’ll see how the above works for my application. I’m iterating a GUI window list in reverse order.

“Also…don’t use lists if you can avoid it, as they’re much slower to iterate through than a stack.”

I typically use list in a limited fashion. For example in the mapping code (game map) I developed for my framework I use arrays (one dimensional and storing objects and other types). Are stack’s more efficient then arrays?

[Richard BetsonParticipant]

Also…don’t use lists if you can avoid it, as they’re much slower to iterate through than a stack.

Hi Mark,

I am going to change my code to support ‘Stack’s’ instead of ‘List’s’. Will stack’s have reverse iteration (ala. Backwards() ) and are they so much faster then list’s that it’s worth the trouble to convert to them? Specifically, are stacks quicker when adding objects to them as compared to a list?

 

[Mark SiblyKeymaster]

Stack.Backwards() is already in there.

Specifically, are stacks quicker when adding objects to them as compared to a list?

Generally much faster – adding to a List requires the extra allocation of an internal Node object.

A stack is basically just an array that grows as necessary, so unless the stack needs to grow adding to a stack is just blah[i]=obj;i+=1. When the stack grows, it grows by capacity*1.5 so eventually the stack capacity ‘settles’ to the max objects the stack can hold.

The downside of a stack is that to remove an object, all elements after the object must be shuffled up, like removing a value from an array.

But the overhead here is similar to List.Remove() which a lot of people seem to use, which does a linear search to find the node containing the object. The only time List is a win when removing is if you can use it.Erase() while manually iterating through values.

Even if you can do this, Stack is usually still a win as the reduced overhead of adding and iteration is worth it. To iterate through a list requires following ‘next’ pointers around, while iterating through a stack is just like iterating through an array, ie: very fast.

As for whether it’s worth it, as always ‘it depends’. If you’re not using large amounts of objects, or if the cost of iteration etc is ‘dwarfed’ by per-object processing cost, then probably not. It may not be worth it for your project, but I think it’s something to consider for future additions.

[Richard BetsonParticipant]

Thanks for the taking the time to explain that. I can see there are parts of the framework I am building where stacks will make better sense. Generally for a GUI there is ‘not’ a lot of deletion or removal of objects. So stacks should be a better option for the most part in that case.

In other parts of the my framework I will have to test it out to know I guess. For example I currently use a list for drawing images via a DrawList class (my framework) which holds a list of other class objects to be drawn, rendered and so forth. In that case deletion/removal is constantly occurring. It should be possible to use iterator.Erase() as I iterate through the DrawList() class list which might compete with stack performance.

All of this is interesting and looking at the IContainer examples looks easy to implement. I do appreciate the explanation and thanks for laying that out.

[Author]

Posts