Stack Data Structure?
BlitzMax Forums/BlitzMax Programming/Stack Data Structure?
| ||
While investigating and evaluating different data structures for a larger project I've been working on, I keep coming back to the idea of a somewhat expanded stack. Arrays have problems: they aren't dynamic unless wrapped up in a system that's basically like a stack anyway. They are slow for insertions (but I don't foresee doing insertions anyway.) Lists have problems: they are not addressable by index, they have memory overhead and they cause GC issues that I don't want to deal with. The expanded stack I'm talking about maintains a map so that it can be shuffled around internally but still be addressable by index. It is comparatively quick to expand with the size doubling algorithm-- start it at a number slightly above what you think you will need, then if more are needed, double the size. Most likely you will only have to do that once or twice at the most and that would cause a total of two fairly negligible hitches. It's easy to push and pop on/off the end. Because of the map you can do very quick insertions-- move item N to the end of the list and insert the item you want to insert where N used to be. Stacks are also good for things that naturally fluctuate from zero up to some arbitrary number and then back down to zero again, like a particle system or a renderables list where every tick in the update loop you check to see if a given object is onscreen and then add it to renderables. When it comes time for the render loop, you can either just pop every item until the list is at zero, or you can run through and render everything and then manually set the top of the stack to zero which might be somewhat problematic in a memory management sense but if the stack contains only index ints it isn't too bad to just leave them out there, they will mostly get overwritten next tick anyway. Non-ordered array walks, eg. Foreach, can happen without having to go through the extra abstraction of the index map. Thoughts? Are there limitations of this approach that I'm not noticing? Someone, maybe Brucey, had mentioned using a TList full of arrays, which seems to me to be unnecessarily unwieldy, but are there advantages there? |
| ||
In case anyone reads this and wonders how to make a self-doubling stack, here it is. If you use this for any user-defined type make sure you initialize the empty locations on the array (using an init loop, eg "data[i]=new <whatever type>") or you may get an exception error or other bizarre behavior when you attempt to use it. See this if you feel the need to be even more confused. Again, the reason for size doubling is so that if you exceed the stack size, you can resize it in an optimal number of doubling operations. Type intstack Field data:Int[1] Field top:Int = 0 Field length = 1 Method push(num:Int) top= top+ 1 ' Check to see if we're exceeding the current size of the array If top > length ' if so, double the array size. The idea here is no matter how large the number of items we have to ' deal with is going to be, we can resize the stack to deal with that number and do so in a small ' number of doubling operations. Of course it's probably a good idea to set the initial array size ' to a reasonably large number, and the length field to that number. 'Print "stack exceeded length = length*2 data = data[..length] ' The .. is an array slice, up to the new doubled length, so the array size ' gets doubled. 'Print "expanded to "+length EndIf data[top]=num End Method Method pop:Int() ' Remove the top item from the stack If top = 0 Return Null a = data[top] top= top- 1 Return a End Method Method dump() Print "---------------" Print "Data Space:"+data.length Print "Items on Stack:"+top If top > 0 For i = 1 To top Print i+":"+data[i] Next EndIf Print "---------------" End Method Method peek(num:Int) ' returns the int at a specific array index Return data[num] End Method Method poke(addr:Int, num:Int) ' overrwrite the data at a specific array index with <num> If instack(addr) data[addr]=num EndIf End Method Method swap(addr1:Int, addr2:Int) ' Swap the values at two array indexes If instack(addr1) And instack(addr2) Local temp:Int = data[addr1] data[addr1]=data[addr2] data[addr2]=temp Return 1 Else Return 0 EndIf End Method Method instack(num:Int) ' Error checking function to make sure an index is in bounds If num > 0 And num < top+1 Return 1 Return 0 End Method Method End Type |
| ||
The stack ADT (Abstract Data Type) in computer science generally supports three operations: O(1) (constant time) push O(1) (constant time) pop O(1) (constant time) peek Stacks are usually implemented as either a adjustable array (as you have done) or using a linked list (adding / removing to the head of the list). Your push / pop are O(1) as you have implemented them. If you want to access specific elements, you'll probably want the array approach you specified. I don't know what your specific needs are, so I can't tell you what data structure would help best. But it sounds like you might already know? |
| ||
You can write methods that will allow your type to be called with EachIn. Information is in the Help section of the IDE under Collections. Here is a stack type that works with Object. Should be easily modified to work with primitive types. |
| ||
If you use this for any user-defined type make sure you initialize the empty locations on the array (using an init loop, eg "data[i]=new <whatever type>") or you may get an exception error or other bizarre behavior when you attempt to use it. Initializing the elements of the array is not necessary as you will only be passing already initialized objects to the stack methods.Local Array:TMyType[10] Array[0].MyInt = 0 <-Will not work, Array[0] not initialized Local Array:TMyType[10] Array[0] = New TMyType Array[0].MyInt = 0 <- Will work, Array[0] has been initialized Local Array:TMyType[10] Local MyType:TMyType = New TMyType Array[0] = MyType Array[0].MyInt = 0 <-will also work as an initialized object has been stored in Array[0] |
| ||
I may be able to get useful behavior out of a stack of index ints and a tlist, with the list.toarray() method. With 1000 on the list, I can do a listfromarray() something like 50,000 times per second. With 400 on the list, and that may be a more reasonable number, it's basically trivial. So maybe the right thing to do is to let the list exist as a list for part of the loop, then translate it to an array and do needed array operations there. Listtoarray is about 6 times faster than listfromarray so maybe I can get by without turning it back into a list. A lot of this can be amortized away and elided with trickery in various ways because I'm not going to do full updates on things that aren't on the screen. Tomtoad thanks for that object stack. |